首页 > 其他分享 >CSP20230319-4 星际网络II 题解

CSP20230319-4 星际网络II 题解

时间:2023-03-24 15:22:40浏览次数:57  
标签:0000 0001 int 题解 CSP20230319 tr II 地址 opts

〇、题目

题目描述

随着星际网络的进一步建设和规模的增大,一个新的问题出现在网络工程师面前——地址空间不够用了!原来,星际网络采用了传统的IPv6协议,虽然有 \(2^{128}\) 级别的可用地址数量,但面对广袤无垠的宇宙和爆炸式增长的网络用户数,如此庞大的地址空间也面临了用尽的那一天。

新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。最终,经过2333年的不懈努力,西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”,又称IPxxaf。

在IPxxaf协议中,一个地址由 \(n\) 位二进制位组成,其中 \(n\) 是 \(16\) 的倍数。日常表示一个地址时,采用类似IPv6协议的十六进制表示法,每 \(4\) 位用 : 隔开。如 \(n=32\) 时,地址为 2a00:0001 ,即表示一个二进制为 0010 1010 0000 0000 0000 0000 0000 0001 的地址。注意不会出现IPv6中省略每组的前导 0 或用 :: 省略一段 0 的情况。

为方便起见,记 \(num(s)\) 为地址 s 按高位在前、低位在后组成的 \(n\) 位二进制数,称一段“连续的地址“为 \(num(s)\) 成一段连续区间的一系列地址。

西西艾弗星的网络管理员负责地址的分配与管理。最开始,整个地址空间都是未分配的。用户可以随时向管理员申请一些地址:

1 id l r:表示用户 \(id\) 申请地址在 \(l\sim r\) 范围内(包含 \(l\) 和 \(r\),下同)的一段连续地址块。

在地址申请操作中,管理员需要先检查地址是否可用。如果用户申请的地址全部未被分配,则检查通过;若地址中存在已经分配给其他用户的地址,则检查失败。

但有一种特殊情况:申请的地址中没有已经分配给其他用户的地址,但含有一些先前已分配给该用户本人的地址。此时可以认为检查通过,但若申请的地址先前已全部分配给该用户则检查失败。

如果上述检查通过,则管理员向用户返回 YES,并将申请的地址分配给该用户;若不通过,则向用户返回 NO,同时不改变现有的地址分配。

网络管理员要定期检查地址的分配情况,具体而言有如下两种操作:

2 s:检查地址 \(s\) 被分配给了哪个用户。若未被分配,则结果为 \(0\)。

3 l r:检查 \(l\sim r\) 范围内的所有地址是否完整地分配给了某个用户。若是,回答该用户的编号;若否,回答 \(0\) 。

在整个网络的运行过程中,共出现了 \(q\) 次申请地址和检查地址分配的操作。作为西西艾弗星的一名重要的网络技术顾问,你要帮网络管理员依次处理每个操作,并回答相应的结果。

输入格式

从标准输入读入数据。

第一行,\(2\) 个正整数 \(n,q\)。

接下来 \(q\) 行,每行一个操作,格式如上所述,其中的 \(id\) 为正整数,\(l,r,s\) 均为IPxxaf地址串,其中十六进制均用数字和小写字母表示。

输出格式

输出到标准输出。

输出 \(q\) 行,每行一个非负整数或字符串,表示此次操作的结果。

其中,对于操作 \(1\),输出 YESNO;对于操作 \(2\),输出一个非负整数。

样例输入1

32 12
1 1 0001:8000 0001:ffff
2 0001:a000
3 0001:c000 0001:ffff
1 2 0000:0000 000f:ffff
2 0000:1000
1 1 0001:8000 0001:8fff
1 2 0000:0000 0000:ffff
2 0000:1000
1 1 0002:8000 0002:ffff
3 0001:8000 0002:ffff
1 1 0001:c000 0003:ffff
3 0001:8000 0002:ffff

样例输出1

YES
1
1
NO
0
NO
YES
2
YES
0
YES
1

样例解释

第 \(4\) 个操作时,由于用户 \(2\) 申请的部分地址已被分配给用户 \(1\),因此申请不通过;

第 \(6\) 个操作时,由于用户 \(1\) 申请的全部地址已被分配给用户 \(1\),因此申请不通过;

第 \(11\) 个操作时,用户 \(1\) 申请的部分地址已被分配给用户 \(1\),其余地址尚未被分配,申请通过;

数据范围

对于所有数据,\(n\leq 512,q\leq 5\times10^4\),\(n\) 为 \(16\) 的倍数,\(id\leq q\),对于操作 \(1,3\) 保证 \(num(l)\leq num(r)\)。

测试点编号 \(n\leq\) \(q\leq\) 特殊性质
\(1\sim4\) \(16\) \(200\)
\(5\sim6\) \(64\) \(200\)
\(7\sim9\) \(512\) \(200\)
\(10\sim11\) \(16\) \(20000\)
\(12\sim13\) \(64\) \(50000\)
\(14\sim16\) \(512\) \(50000\) 所有操作 1 的 \(id\) 互不相同
\(17\sim20\) \(512\) \(50000\)

一、思路

首先看到这个离谱的 IP 表示方法,我们就想把它离散化。

这个东西有一个好处:因为长度相等而且数字的 ASCII 码小于字母的,所以我们可以直接比较字符串。

在离散化的时候,注意到他要判断是否连续,所以在离散化的时候要注意当前 IP 和上一个是否相邻。

于是整个问题就转化为了给你一个不超过 \(2\times 10^5\) 大小的数组,进行区间涂色和查询。

这个时候有一个类似于哈希的思路:给每个颜色一个权值 \(w_i\),记一个区间的和 \(Sum_{l,r}\) 为这个区间内所有点的颜色的 \(w_i\) 之和。

那么这时一个区间 \(l,r\) 的颜色如果都是 \(i\)(或者没有颜色),那么显然 \(Sum_{l,r}\) 一定是 \(i\) 的倍数。

但是我们发现有可能 出现 \(x\times w_1=y\times w_2\) 的情况,这个时候可能和就没法代表一个固定的东西了。

为了避免上面情况的发生,因为 \(x\) 和 \(y\) 实际上只能是长度,不超过 \(2\times 10^5\)。于是,我们很容易想到选取大于 \(2\times 10^5\) 的 \(2\times 10^5\) 个质数作为 \(w_i\) 即可,大约 \(4\times 10^6\) 就可以筛出这么多。

那既然 \(Sum_{l,r}\) 能固定了,就可以解决三种操作了:

  1. 如果 \(w_{id}\nmid Sum_{l,r}\) 或者 \(Sum_{l,r}=(r-l+1)\times w_{id}\),那么答案就是 NO,否则就是 YES,然后直接区间把颜色改为 \(w_{id}\)。
  2. 单点查询颜色。
  3. 记录区间颜色权值的最小值(或者最大值) \(Min_{l,r}\),而显然在一个区间颜色都相等的情况下一定有 \(Sum_{l,r}=(r-l+1)\times Min_{l,r}\)(因为所有颜色都是一样的),这个时候就输出 \(Min_{l,r}\) 对应的颜色,否则就是 \(0\)。

直接线段树维护即可。

这个思路是不是十分抽象,我也觉得这很抽象。这个奇妙的思路来源于 小 H。OrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrz

二、代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
struct op{//离散化所以要记录操作
	int opt;
	string x,y;
	int l,r;
	int user;
}opts[50005];
string plusone(string s){int w;//IP地址+1
	s[w=s.length()-1]++;
	while(w>=0&&s[w]=='g'){
		s[w]='0';
		if(s[w-1]==':') s[w-2]++,w-=2;
		else s[w-1]++,w--;
	}
	if(s[w]==58) s[w]='a';
	return s;
}
struct LSH{//离散化
	set<string> s;int cnt;
	unordered_map<string,int> toNum;
	inline void pls(string str){s.insert(str);}
	inline void run(){
		auto it=s.begin(),ti=s.end();//ti是it的上一个
		for(;it!=s.end();it++){
			if(it!=s.begin()){
				if(ti==s.end()) ti=s.begin();
				else ti++;
				if(plusone(*ti)!=(*it)) cnt++;
			}
			toNum[*it]=++cnt;
		}
	}
	inline int gNum(string s){return toNum[s];}
}lsh;
bitset<4000005> isnp;int pr[400005],prcnt;int W[200005],anscnt;
map<int,int> ni;
void shai(int n){//筛出足够多的质数
	isnp[1]=1;
	for(int i=2;i<=n;i++){
		if(!isnp[i]){
			pr[++prcnt]=i;
			if(i>200000) W[++anscnt]=i,ni[i]=anscnt;//记录一下倒过来是什么
			if(anscnt>=200000) return;
		}
		for(int j=1;j<=prcnt&&1ll*i*pr[j]<=n;j++){
			isnp[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
}
#define ll long long
ll MIN(ll a,ll b){return a==0?b:b==0?a:a<b?a:b;}//这里建议没有数的时候min就是 0,方便输出但是要自己定义一下新的min
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
struct node{//下面是线段树
	ll sum,mn,lazy,len;
	node operator +(node b){return {sum+b.sum,MIN(mn,b.mn),0,len+b.len};}
	node operator =(ll b){return {sum=b*len,mn=b,lazy=b,len};}
}tr[800005];
void build(int p,int l,int r){
	if(l==r){tr[p]={0,0,0,1};return;}
	build(ls,l,mid);build(rs,mid+1,r);tr[p]=tr[ls]+tr[rs];
}
void pushdown(int p){if(tr[p].lazy) tr[ls]=tr[p].lazy,tr[rs]=tr[p].lazy,tr[p].lazy=0;}
void chg(int p,int l,int r,int L,int R,ll c){
	if(l>=L&&r<=R){tr[p]=c;return;}
	pushdown(p);
	if(L<=mid) chg(ls,l,mid,L,R,c);
	if(R>mid) chg(rs,mid+1,r,L,R,c);
	tr[p]=tr[ls]+tr[rs];
}
ll qsum(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R) return tr[p].sum;
	ll ans=0;
	pushdown(p);
	if(L<=mid) ans+=qsum(ls,l,mid,L,R);
	if(R>mid) ans+=qsum(rs,mid+1,r,L,R);
	return ans;
}
ll qmin(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R) return tr[p].mn;
	ll ans=0;
	pushdown(p);
	if(L<=mid) ans=MIN(ans,qmin(ls,l,mid,L,R));
	if(R>mid) ans=MIN(ans,qmin(rs,mid+1,r,L,R));
	return ans;
}
int main(){
	shai(4000000);
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		cin>>opts[i].opt;
		if(opts[i].opt==1) cin>>opts[i].user>>opts[i].x>>opts[i].y;
		else if(opts[i].opt==2) cin>>opts[i].x;
		else cin>>opts[i].x>>opts[i].y;
		lsh.pls(opts[i].x);
		if(opts[i].opt!=2) lsh.pls(opts[i].y);
	}
	lsh.run();
	for(int i=1;i<=q;i++) opts[i].l=lsh.gNum(opts[i].x),(opts[i].opt!=2)&&(opts[i].r=lsh.gNum(opts[i].y));
	n=lsh.cnt;//相当于一共就这么多节点
	build(1,1,n);
	for(int i=1;i<=q;i++){int op=opts[i].opt,l=opts[i].l,r=opts[i].r,id=opts[i].user;//按照思路写出来非常轻松
		if(op==1){
			ll sum=qsum(1,1,n,l,r);
			if((sum%W[id])||sum/W[id]==r-l+1) cout<<"NO"<<endl;
			else{
				chg(1,1,n,l,r,W[id]);
				cout<<"YES"<<endl;
			}
		}
		if(op==2){
			cout<<ni[qmin(1,1,n,l,l)]<<endl;
		}
		if(op==3){
			ll sum=qsum(1,1,n,l,r),mn=qmin(1,1,n,l,r);
			if(mn==0||sum%mn==0&&sum/mn==r-l+1) cout<<ni[mn]<<endl;
			else cout<<0<<endl;
		}
	}
	return 0;
}

三、总结

题目很抽象,思路也很抽象(

不过感觉似乎这个 trick 在一些题上能派上小用场。

标签:0000,0001,int,题解,CSP20230319,tr,II,地址,opts
From: https://www.cnblogs.com/tigerchen/p/Abstract_problem.html

相关文章

  • 【sklearn版本问题解决】
    一、报错fromsklearn.utils.validationimportcheck_memoryImportError:cannotimportname'check_memory'二、解决1.首先我去看了相关位置的源码发现validation.py里......
  • LeetCode45. 跳跃游戏 II
    classSolution{public://f[i]表示跳到i所需的最小步数intjump(vector<int>&nums){vector<int>f(10010,0x3f3f3f3f);intn=nums.size()......
  • 查看 docker-for-mac的 runtiime
    使用容器命名空间dockerrun-it--rm--privileged--pid=hostjustincormack/nsenter1进入容器uanme-a#Linuxdocker-desktop5.15.49-linuxkit#1SMPPREEMPTT......
  • 关于安装google-colab包速缓慢的问题解决
    最近想从colab上重构源码包在本地实现,但是总有一个包是来自google.colab的fromgoole.colabimportfiles提示没有google.colab的安装模块,需要安装google-colab的这个包......
  • T324159 卡空间的题目/电脑白吃 题解
    https://www.luogu.com.cn/problem/T324159题目大意:给定一个大小为\(n\)的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于\(\lfloor\frac{n}{2}\rfloo......
  • CF1168C And Reachability 题解 线性dp
    题目链接https://codeforces.com/problemset/problem/1168/C题目大意给定一个数组\(a\),从下标\(x\)能够转移到下标\(y\)要满足\(x\lty\)且\(a_{p_i}\,\&\,a......
  • 【LeeCode】557. 反转字符串中的单词 III
    【题目描述】给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。【示例】【代码】adminpackagecom.company;//2023-03-23impo......
  • P3489 [POI2009]WIE-Hexer 题解
    一、题目描述:大陆上有 n 个村庄,m 条双向道路,p 种怪物,k 个铁匠,铁匠都在一个村庄里,他可会给你打造他所能打造的所有剑,特定的剑可以对付特定的怪物,每条道路上都可......
  • 【坚持每日一题9.27】639. 解码方法 II
    一条包含字母 A-Z的消息通过以下的方式进行了编码:‘A’->1‘B’->2…‘Z’->26要解码一条已编码的消息,所有的数字都必须分组,然后按原来的编码方案反向映射回......
  • P4221 [WC2018]州区划分 题解
    题目链接题目描述给出\(n\)个城市,\(m\)条边,一个划分合法当且仅当所有划分中的点集和集合中点之间存在的边集所构成的图不构成欧拉回路且联通。定义一个点集的值为......