想查看其他题的真题及题解的同学可以前往查看:CCF-CSP真题附题解大全
试题编号: | 202303-4 | ||||||||||||||||||||||||||||||||
试题名称: | 星际网络II | ||||||||||||||||||||||||||||||||
时间限制: | 2.0s | ||||||||||||||||||||||||||||||||
内存限制: | 1.0GB | ||||||||||||||||||||||||||||||||
问题描述: | 问题描述随着星际网络的进一步建设和规模的增大,一个新的问题出现在网络工程师面前——地址空间不够用了!原来,星际网络采用了传统的IPv6协议,虽然有 2128 级别的可用地址数量,但面对广袤无垠的宇宙和爆炸式增长的网络用户数,如此庞大的地址空间也面临了用尽的那一天。 新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。最终,经过2333年的不懈努力,西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”,又称IPxxaf。 在IPxxaf协议中,一个地址由 n 位二进制位组成,其中 n 是 16 的倍数。日常表示一个地址时,采用类似IPv6协议的十六进制表示法,每 4 位用 为方便起见,记 num(s) 为地址 西西艾弗星的网络管理员负责地址的分配与管理。最开始,整个地址空间都是未分配的。用户可以随时向管理员申请一些地址:
在地址申请操作中,管理员需要先检查地址是否可用。如果用户申请的地址全部未被分配,则检查通过;若地址中存在已经分配给其他用户的地址,则检查失败。 但有一种特殊情况:申请的地址中没有已经分配给其他用户的地址,但含有一些先前已分配给该用户本人的地址。此时可以认为检查通过,但若申请的地址先前已全部分配给该用户则检查失败。 如果上述检查通过,则管理员向用户返回 网络管理员要定期检查地址的分配情况,具体而言有如下两种操作:
在整个网络的运行过程中,共出现了 q 次申请地址和检查地址分配的操作。作为西西艾弗星的一名重要的网络技术顾问,你要帮网络管理员依次处理每个操作,并回答相应的结果。 输入格式从标准输入读入数据。 第一行,2 个正整数 n,q。 接下来 q 行,每行一个操作,格式如上所述,其中的 id 为正整数,l,r,s 均为IPxxaf地址串,其中十六进制均用数字和小写字母表示。 输出格式输出到标准输出。 输出 q 行,每行一个非负整数或字符串,表示此次操作的结果。 其中,对于操作 1 ,输出 样例输入1
样例输出1
样例解释第 4 个操作时,由于用户 2 申请的部分地址已被分配给用户 1,因此申请不通过; 第 6 个操作时,由于用户 1 申请的全部地址已被分配给用户 1,因此申请不通过; 第 11 个操作时,用户 1 申请的部分地址已被分配给用户 1,其余地址尚未被分配,申请通过; 数据范围对于所有数据,n≤512, q≤5×104,n 为 16 的倍数,id≤q,对于操作 1,3 保证 num(l)≤num(r)。
|
真题来源:星际网络II
感兴趣的同学可以如此编码进去进行练习提交
思路讲解:
这道题属于线段树(离散化、单点询问、区间求和、区间最值)的经典题。线段树维护区间和,用于记录对应区间几个值被用过,且线段树维护最大最小值,用于记录被哪个用户id用过,当最小值=最大值时,表示恰被一个用户用过。首先,将最大32维的数转10进制,压成长为32的array,离散化去重后,找到每个ip地址对应下标映射。
操作1:若[l,r]是否没被用户用过,或[l,r]仅被当前用户用过且没占满,则可行,否则不可行;线段树先查一下这段区间和,等于0表示没被用过,则可行;否则,判一下当前区间最大最小值,若最大最小值相等且区间和小于区间长度,则可行。
操作2:单点询问,查单点最大/最小值即可知道被哪个用户用过,或没用过;
操作3:区间询问,若[l,r]仅被一个用户全用过,则区间和为区间长度,区间最大最小值相等,注意离散化时,需要给右端点+1的值也离散化进去,并考虑+1带来的进位问题,否则,可能会出现[1,2][4,5]在离散化前不相邻,离散化后变为[1,2][3,4]相邻的情形;
c++满分题解:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15e4+10,M=5e4+10,K=170,B=32,INF=0x3f3f3f3f;
struct segtree{
int n;
struct node{int l,r,v,c,mn,mx;}e[N<<2];
#define l(p) e[p].l
#define r(p) e[p].r
#define v(p) e[p].v
#define c(p) e[p].c
#define mn(p) e[p].mn
#define mx(p) e[p].mx
void up(int p){
v(p)=v(p<<1)+v(p<<1|1);
mn(p)=min(mn(p<<1),mn(p<<1|1));
mx(p)=max(mx(p<<1),mx(p<<1|1));
}
void bld(int p,int l,int r){
l(p)=l;r(p)=r;c(p)=0;
if(l==r){v(p)=0;mn(p)=INF;mx(p)=-INF;return;}
int mid=l+r>>1;
bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
up(p);
}
void psd(int p){
if(c(p)){
v(p<<1)=r(p<<1)-l(p<<1)+1;
mn(p<<1)=min(mn(p<<1),c(p));
mx(p<<1)=max(mx(p<<1),c(p));
c(p<<1)=c(p);
v(p<<1|1)=r(p<<1|1)-l(p<<1|1)+1;
mn(p<<1|1)=min(mn(p<<1|1),c(p));
mx(p<<1|1)=max(mx(p<<1|1),c(p));
c(p<<1|1)=c(p);
c(p)=0;
}
}
void init(int _n){n=_n;bld(1,1,n);}
void chg(int p,int ql,int qr,int v){
if(ql>qr)return;
if(ql<=l(p)&&r(p)<=qr){
v(p)=r(p)-l(p)+1;
mn(p)=min(mn(p),v);
mx(p)=max(mx(p),v);
c(p)=v;
return;
}
psd(p);
int mid=l(p)+r(p)>>1;
if(ql<=mid)chg(p<<1,ql,qr,v);
if(qr>mid)chg(p<<1|1,ql,qr,v);
up(p);
}
int cnt(int p,int ql,int qr){
if(ql<=l(p)&&r(p)<=qr)return v(p);
int mid=l(p)+r(p)>>1,res=0;
psd(p);
if(ql<=mid)res+=cnt(p<<1,ql,qr);
if(qr>mid)res+=cnt(p<<1|1,ql,qr);
return res;
}
int amn(int p,int ql,int qr){
if(ql<=l(p)&&r(p)<=qr)return mn(p);
int mid=l(p)+r(p)>>1,res=INF;
psd(p);
if(ql<=mid)res=min(res,amn(p<<1,ql,qr));
if(qr>mid)res=min(res,amn(p<<1|1,ql,qr));
return res;
}
int amx(int p,int ql,int qr){
if(ql<=l(p)&&r(p)<=qr)return mx(p);
int mid=l(p)+r(p)>>1,res=-INF;
psd(p);
if(ql<=mid)res=max(res,amx(p<<1,ql,qr));
if(qr>mid)res=max(res,amx(p<<1|1,ql,qr));
return res;
}
}seg;
int n,m,q,op,c;
array<int,B>f[N];
auto cal(string s){
int d=0;
array<int,B>ans={0};
for(auto &y:s){
if(y==':'){
d++;
continue;
}
int &v=ans[d];
if('a'<=y && y<='f')v=v*16+(y-'a')+10;
else v=v*16+(y-'0');
}
return ans;
}
auto add_one(array<int,B>y){
y[n/16-1]++;
for(int i=B-1;i;--i){
if(y[i]>=65536){
y[i]-=65536;
y[i-1]++;
}
}
return y;
}
int g(array<int,B>v){
int x=lower_bound(f,f+c,v)-f;
return x+1;
}
struct ask{
int op,x;
string s,t;
void rd(){
cin>>op;
if(op==1)cin>>x;
cin>>s;
f[c++]=cal(s);
if(op==2)t=s;
else{
cin>>t;
f[c++]=cal(t);
f[c]=add_one(f[c-1]);
c++;
}
}
void sol(){
int l=g(cal(s)),r=g(cal(t)),w=seg.cnt(1,l,r);
int mn=seg.amn(1,l,r),mx=seg.amx(1,l,r);
if(op==1){
if(!w || (w<r-l+1 && mn==mx && mn==x)){
seg.chg(1,l,r,x);
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
else if(op==2){
cout<<(mn==INF?0:mn)<<endl;
}
else{
cout<<(w==r-l+1 && mn==mx?mn:0)<<endl;
}
}
}e[M];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=q;++i){
e[i].rd();
}
sort(f,f+c);
c=unique(f,f+c)-f;
seg.init(c+5);
for(int i=1;i<=q;++i){
e[i].sol();
}
return 0;
}
运行结果:
文章来源:https://www.uudwc.com/A/PmXAO/
文章来源地址https://www.uudwc.com/A/PmXAO/