CCF-CSP真题《202303-4 星际网络II》思路+python，c++满分题解

叁歲伎倆 2023-10-13 12:19 15阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

--------------------

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202303-4</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>星际网络II</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>2.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>1.0GB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题描述</h3> <p>随着星际网络的进一步建设和规模的增大，一个新的问题出现在网络工程师面前——地址空间不够用了！原来，星际网络采用了传统的IPv6协议，虽然有&nbsp;2128&nbsp;级别的可用地址数量，但面对广袤无垠的宇宙和爆炸式增长的网络用户数，如此庞大的地址空间也面临了用尽的那一天。</p> <p>新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。最终，经过2333年的不懈努力，西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”，又称IPxxaf。</p> <p>在IPxxaf协议中，一个地址由&nbsp;n&nbsp;位二进制位组成，其中&nbsp;n&nbsp;是&nbsp;16&nbsp;的倍数。日常表示一个地址时，采用类似IPv6协议的十六进制表示法，每&nbsp;4&nbsp;位用&nbsp;<code>:</code>&nbsp;隔开。如&nbsp;n=32&nbsp;时，地址为&nbsp;<code>2a00:0001</code>&nbsp;，即表示一个二进制为&nbsp;<code>0010 1010 0000 0000 0000 0000 0000 0001</code>&nbsp;的地址。注意不会出现IPv6中省略每组的前导&nbsp;<code>0</code>&nbsp;或用&nbsp;<code>::</code>&nbsp;省略一段&nbsp;<code>0</code>&nbsp;的情况。</p> <p>为方便起见，记&nbsp;num(s)&nbsp;为地址&nbsp;<code>s</code>&nbsp;按高位在前、低位在后组成的&nbsp;n&nbsp;位二进制数，称一段“连续的地址“为&nbsp;num(s)&nbsp;成一段连续区间的一系列地址。</p> <p>西西艾弗星的网络管理员负责地址的分配与管理。最开始，整个地址空间都是未分配的。用户可以随时向管理员申请一些地址：</p> <p><code>1 id l r</code>：表示用户&nbsp;id&nbsp;申请地址在&nbsp;l∼r&nbsp;范围内（包含&nbsp;l&nbsp;和&nbsp;r，下同）的一段连续地址块。</p> <p>在地址申请操作中，管理员需要先检查地址是否可用。如果用户申请的地址全部未被分配，则检查通过；若地址中存在已经分配给其他用户的地址，则检查失败。</p> <p>但有一种特殊情况：申请的地址中没有已经分配给其他用户的地址，但含有一些先前已分配给该用户本人的地址。此时可以认为检查通过，但若申请的地址先前已全部分配给该用户则检查失败。</p> <p>如果上述检查通过，则管理员向用户返回&nbsp;<code>YES</code>，并将申请的地址分配给该用户；若不通过，则向用户返回&nbsp;<code>NO</code>，同时不改变现有的地址分配。</p> <p>网络管理员要定期检查地址的分配情况，具体而言有如下两种操作：</p> <p><code>2 s</code>：检查地址&nbsp;s&nbsp;被分配给了哪个用户。若未被分配，则结果为&nbsp;0。</p> <p><code>3 l r</code>：检查&nbsp;l∼r&nbsp;范围内的所有地址是否完整地分配给了某个用户。若是，回答该用户的编号；若否，回答&nbsp;0。</p> <p>在整个网络的运行过程中，共出现了&nbsp;q&nbsp;次申请地址和检查地址分配的操作。作为西西艾弗星的一名重要的网络技术顾问，你要帮网络管理员依次处理每个操作，并回答相应的结果。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>第一行，2&nbsp;个正整数&nbsp;n,q。</p> <p>接下来&nbsp;q&nbsp;行，每行一个操作，格式如上所述，其中的&nbsp;id&nbsp;为正整数，l,r,s&nbsp;均为IPxxaf地址串，其中十六进制均用数字和小写字母表示。</p> <h3>输出格式</h3> <p>输出到标准输出。</p> <p>输出&nbsp;q&nbsp;行，每行一个非负整数或字符串，表示此次操作的结果。</p> <p>其中，对于操作&nbsp;1&nbsp;，输出&nbsp;<code>YES</code>&nbsp;或&nbsp;<code>NO</code>；对于操作&nbsp;2,3，输出一个非负整数。</p> <h3>样例输入1</h3> 
    <blockquote> 
     <p>32 12<br> 1 1 0001:8000 0001:ffff<br> 2 0001:a000<br> 3 0001:c000 0001:ffff<br> 1 2 0000:0000 000f:ffff<br> 2 0000:1000<br> 1 1 0001:8000 0001:8fff<br> 1 2 0000:0000 0000:ffff<br> 2 0000:1000<br> 1 1 0002:8000 0002:ffff<br> 3 0001:8000 0002:ffff<br> 1 1 0001:c000 0003:ffff<br> 3 0001:8000 0002:ffff</p> 
    </blockquote> <h3>样例输出1</h3> 
    <blockquote> 
     <p>YES<br> 1<br> 1<br> NO<br> 0<br> NO<br> YES<br> 2<br> YES<br> 0<br> YES<br> 1</p> 
    </blockquote> <h3>样例解释</h3> <p>第&nbsp;4&nbsp;个操作时，由于用户&nbsp;2&nbsp;申请的部分地址已被分配给用户&nbsp;1，因此申请不通过；</p> <p>第&nbsp;6&nbsp;个操作时，由于用户&nbsp;1&nbsp;申请的全部地址已被分配给用户&nbsp;1，因此申请不通过；</p> <p>第&nbsp;11&nbsp;个操作时，用户&nbsp;1&nbsp;申请的部分地址已被分配给用户&nbsp;1，其余地址尚未被分配，申请通过；</p> <h3>数据范围</h3> <p>对于所有数据，n≤512,&nbsp;q≤5×104，n&nbsp;为&nbsp;16&nbsp;的倍数，id≤q，对于操作&nbsp;1,3&nbsp;保证&nbsp;num(l)≤num(r)。</p> 
    <table> 
     <thead> 
      <tr> 
       <th>测试点编号</th> 
       <th>n≤</th> 
       <th>q≤</th> 
       <th>特殊性质</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1∼4</td> 
       <td>16</td> 
       <td>200</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>5∼6</td> 
       <td>64</td> 
       <td>200</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>7∼9</td> 
       <td>512</td> 
       <td>200</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>10∼11</td> 
       <td>16</td> 
       <td>20000</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>12∼13</td> 
       <td>64</td> 
       <td>50000</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>14∼16</td> 
       <td>512</td> 
       <td>50000</td> 
       <td>所有操作 1 的&nbsp;id&nbsp;互不相同</td> 
      </tr> 
      <tr> 
       <td>17∼20</td> 
       <td>512</td> 
       <td>50000</td> 
       <td>无</td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[星际网络II][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;
    }

**运行结果：**

![31f519da61c448ce9c4ece754696a21f.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[II]: http://118.190.20.162/view.page?gpid=T162
[31f519da61c448ce9c4ece754696a21f.png]: https://img-blog.csdnimg.cn/31f519da61c448ce9c4ece754696a21f.png