Codeforces 888 div3 A-G

avatar
作者
筋斗云
阅读量:0

A. Escalator Conversations

分析

二者身高差为k的倍数且不超过m-1倍,身高差不能为0(即不能在同一个阶梯)

C++代码

#include<iostream> using namespace std; void solve(){ 	int n,m,k,H,ans=0; 	cin>>n>>m>>k>>H; 	for(int i=0;i<n;i++){ 		int x; 		cin>>x; 		if(H!=x&&abs(H-x)%k==0&&abs(H-x)/k<=m-1)ans++; 	} 	cout<<ans<<endl; } int main(){ 	int t; 	cin>>t; 	while(t--){ 		solve(); 	} 	return 0; } 

B. Parity Sort

分析

把奇数和偶数分开排序,然后依次填充原数组奇数和偶数的地方,判断是否有前面的数大于后面的情况,如果有,则输出NO

C++代码

#include<iostream> #include<vector> #include<algorithm> using namespace std; void solve(){ 	int n; 	cin>>n; 	vector<int> s(n+5,0),a,b; 	for(int i=1;i<=n;i++){ 		cin>>s[i]; 		if(s[i]%2)b.push_back(s[i]); 		else a.push_back(s[i]); 	} 	sort(a.begin(),a.end()); 	sort(b.begin(),b.end()); 	int ia=0,ib=0,flag=0; 	for(int i=1;i<=n;i++){ 		if(s[i]%2==0)s[i]=a[ia++]; 		else s[i]=b[ib++]; 		if(s[i]<s[i-1]){ 			flag=1; 			break; 		} 	} 	if(flag)puts("NO"); 	else puts("YES"); } int main(){ 	int t; 	cin>>t; 	while(t--){ 		solve(); 	} 	return 0; }

C. Tiles Comeback

分析

k=1,直接从a[1]跳到a[n]

k!=1

1、a[1]==a[n],找有没有k个a[1]即可

2、a[1]!=a[n],找k个a[1]和k个a[n]且要按顺序

C++代码

#include<iostream> using namespace std; void solve(){ 	int n,k; 	cin>>n>>k; 	int a[n+5]; 	for(int i=1;i<=n;i++)cin>>a[i]; 	if(k==1)puts("YES"); 	else if(a[1]==a[n]){ 		int sum=0; 		for(int i=1;i<=n;i++) 			if(a[i]==a[1])sum++; 		if(sum>=k)puts("YES"); 		else puts("NO"); 	}else{ 		int cnt1=1,cnt2=1,l=n; 		for(int i=2;i<=n;i++){ 			if(a[i]==a[1])cnt1++; 			if(cnt1==k){ 				l=i; 				break; 			} 		} 		for(int j=n-1;j>l;j--) 			if(a[j]==a[n])cnt2++; 		if(cnt2<k)puts("NO"); 		else puts("YES"); 	} } int main(){ 	int t; 	cin>>t; 	while(t--){ 		solve(); 	} 	return 0; }

D. Prefix Permutation Sums

分析

对于给定的数组a,找出它的原数组s

因为a只丢了一个元素,所以原数组的1~n的排列中一定有两个数没出现,如果大于两个元素,则原数组不存在

对原数组的每个小于等于n的元素标记出现过,如果元素出现次数大于1或者元素>n,就用cnt记录下来;接下来找出未出现过的两个数的和sum,如果等于cnt,则表示原数组存在,否则不存在

C++代码

#include<iostream> #include<vector> using namespace std; typedef long long LL; void solve(){ 	int n; 	cin>>n; 	LL a[n+5]={0},b[n+5]={0},cnt=0,flag=0; 	for(int i=1;i<n;i++)cin>>a[i]; 	vector<LL> s; 	for(int i=1;i<n;i++){//找出原数组s 		LL t=a[i]-a[i-1]; 		s.push_back(t); 	} 	for(int i=0;i<n-1;i++){ 		if(s[i]<=n){ 			b[s[i]]++; 			if(b[s[i]]>1)cnt=s[i]; 		}else cnt=s[i]; 	} 	LL sum=0,k=0; 	for(int i=1;i<=n;i++) 		if(!b[i])k++,sum+=i; 	if(k>2||k==2&&sum!=cnt)flag=1; 	if(!flag)puts("YES"); 	else puts("NO");  } int main(){ 	int t; 	cin>>t; 	while(t--){ 		solve(); 	} 	return 0; }

E. Nastya and Potions

分析

一个药水x可以被几种药物混合制成就建几条指向x的边,建完边后就用拓扑排序做,所有入度为0的药水的价格只能是它本身的价格,入度不为0的价格可以由其他的药水混合制成,最终的最低价格为min(直接买的价格,由其他药水混合的价格)

C++代码

#include<iostream> #include<queue> using namespace std; typedef long long LL; const int N=200010; int h[N],e[N],ne[N],idx; LL a[N],d[N],w[N]; int n,k; void add(int a,int b){ 	e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void solve(){ 	cin>>n>>k; 	for(int i=1;i<=n;i++) 		h[i]=-1,w[i]=0,d[i]=0; 	idx=0; 	for(int i=1;i<=n;i++)cin>>a[i]; 	while(k--){//输入所有无限免费供应的药水 		int x; 		cin>>x; 		a[x]=0; 	} 	for(int i=1;i<=n;i++){ 		int m,x; 		cin>>m; 		while(m--){ 			cin>>x; 			add(x,i); 			d[i]++;//i的入度加一 		} 	} 	queue<int> q; 	for(int i=1;i<=n;i++)         //入度为0的药水的价格只能是它本身的价格,不能由别的药水混合制成 		if(!d[i])w[i]=a[i],q.push(i); 	while(q.size()){ 		int t=q.front(); 		q.pop(); 		w[t]=min(w[t],a[t]);//更新药水t的价格 		for(int i=h[t];i!=-1;i=ne[i]){ 			int j=e[i]; 			w[j]+=w[t];//计算药水j由别的药水混合所需的价格 			if(--d[j]==0)q.push(j); 		} 	} 	for(int i=1;i<=n;i++)cout<<w[i]<<" "; 	cout<<endl; } int main(){ 	int t; 	cin>>t; 	while(t--){ 		solve(); 	} 	return 0; }

F. Lisa and the Martians

分析

求(a[i]^x)&(a[j]^x)的最大值,即a[i]^x和a[j]^x的二进制数相同的位置尽可能多且尽可能在高位,即a[i]和a[j]二进制相同的位置尽可能多,即不同的位置尽可能少且尽可能为低位,

则可以装换成求a[i]^a[j]的最小值

有个常用结论:n个数的最小异或对答案就是排序后最小的相邻异或和

所以直接排序后求最小相邻异或和即可

然后计算t

对于选择的a[i]和a[j],从前往后枚举第0~k-1位,

如果a[i]和a[j]的第i位都是0,则t的第i位一定是1

如果a[i]和a[j]的第i位都是1,则t的第i位一定是0

如果一个0一个1,则t的第i位随意

C++代码

#include<iostream> #include<algorithm> #include<map> #include<array> #include<vector> using namespace std; const int N=200010,INF=2e9; void solve(){ 	int n,k; 	cin>>n>>k; 	vector<array<int,2>> a(n); 	for(int i=0;i<n;i++){ 	    int x; 		cin>>x; 		a[i]={x,i+1}; 	} 	sort(a.begin(),a.end()); 	int minn=INF,id1,id2,ai,aj; 	for(int i=0;i<n-1;i++){ 		auto [c,d]=a[i]; 		auto [e,f]=a[i+1]; 		if((c^e)<minn){ 			minn=(c^e); 			id1=d,id2=f; 			ai=c,aj=e; 		} 	} 	int t=1,x=0; 	for(int i=0;i<=k-1;i++){ 		int a1=ai>>i&1,a2=aj>>i&1; 		//a1=a2=0则x的该位一定是1;  a1!=a2则x的该位可以是0也可以是1,这里当成0; a1=a2=1则x的该位一定是0 		if((a1==0&&a2==0))x+=t; 		t*=2; 	} 	cout<<id1<<" "<<id2<<" "<<x<<endl; } int main(){ 	int t; 	cin>>t; 	while(t--){ 		solve(); 	} 	return 0; } 

G. Vlad and the Mountains

分析

这题在线做法肯定会超时,那么可以用离线做法,先存储所有询问,再统一处理

首先,对于一对询问a,b,e,依题意,不能到达高度大于h[a]+e的山上

所以把每条边的权值设置成连接该边的两点的高度较大值

vector<array<int,3>> edge;//按照edge[i]={w,a,b},先是权值,然后是两个点

然后把每条边按照权值从小到大排序

vector<array<int,4>> query;//按照edge[i]={h[a]+e,a,b,i},先是h[a]+e,然后两个点,然后是询问的编号

对所有询问按照h[a]+e从小到大排序

然后依次枚举每个询问,每次将权值<=h[a]+e的边加入到并查集,然后判断a和b是否在同一连通块中,如果是,就可以从a走到b,否则不能

C++代码

#include<iostream> #include<vector> #include<array> #include<algorithm> using namespace std; const int N=200010; int p[N],h[N]; int find(int x){ 	if(p[x]!=x)p[x]=find(p[x]); 	return p[x]; } void merge(int a,int b){ 	a=find(a),b=find(b); 	if(a!=b)p[a]=b; } void solve(){ 	int n,m,q; 	cin>>n>>m; 	for(int i=1;i<=n;i++)p[i]=i;//并查集  	for(int i=1;i<=n;i++)cin>>h[i]; 	vector<array<int,3>> edge(m);//存储所有的边  	for(int i=0;i<m;i++){ 		int a,b; 		cin>>a>>b; 		edge[i]={max(h[a],h[b]),a,b}; 	} 	sort(edge.begin(),edge.end());  	cin>>q; 	vector<array<int,4>> query(q); 	for(int i=0;i<q;i++){ 		int a,b,e; 		cin>>a>>b>>e; 		query[i]={h[a]+e,a,b,i}; 	} 	sort(query.begin(),query.end()); 	 	vector<int> ans(q,0); 	int t=0; 	for(auto [h,u,v,i]:query){ 	    //把所有高度小于等于h的点都加入到并查集中 		while(t<m&&edge[t][0]<=h){//只能走到高度小于等于h的山 			merge(edge[t][1],edge[t][2]); 			t++; 		} 		if(find(u)==find(v))ans[i]=1; 	}  	for(int i=0;i<q;i++) 		if(ans[i])puts("YES"); 		else puts("NO"); } int main(){ 	int t; 	cin>>t; 	while(t--){ 		solve(); 	}  	return 0; }

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!