Codeforces Round #821(Div.2) (A-C) 题解

技术分享 4年前 (2022-09-21) 0 999+

关注

Codeforces Round #821(Div.2) (A-C)

A.Consecutive Sum

大致题意

给定一组共 n 个数据，如果俩个数的下标在 mod k 意义下同余，则可以交换a[I] 和 a[j] ,求操作后一段连续的数的和的最大值。

基本思路

本题属于水题，因为 t 和 n 都比较小，所以可以直接暴力的把所有最大的数移到最前面的 k 个位置，即从最后 k 个数开始向前枚举比较，做冒泡排序即可。

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=105; ll a[N];  int main(){ 	int T; 	cin>>T; 	while(T--){ 		memset(a,0,sizeof a); 		 		int n,k; 		cin>>n>>k; 		for (int i=1;i<=n;i++){ 			cin>>a[i]; 		} 		 		for (int i=1;i<=k;i++){ 			for (int j=n-i+1;j>=1+k;j-=k) { 				if (a[j]>a[j-k]) swap(a[j],a[j-k]); 			} 		} 		 		ll ans=0; 		for (int i=1;i<=k;i++) ans+=a[i]; 		cout<<ans<<endl; 		 	} 	 	return 0; 	 }

建议

读题速度要快，尽早秒杀。

B.Rule of League

大致题意

有 n 个选手举办羽毛球比赛，总共比 n-1 场，每个人不是赢了 x 场就是赢了 y 场，要求构造

一组合理的每场获胜选手的数据。

基本思路

这是一道考研思维的题，我们可以结合生活实际，首先了解比赛的规则。

比赛必须有输有赢，所以 x 和 y 中必须有一个大于 0 ,一个等于 0 (因为总会有人输，也有人赢)。

因为总共比 n-1 场，而赢得人都赢了 x 或 y 次，所以要求 (n-1) mod max(x,y)=0 ,即赢的人的获胜场次必须是 n-1 的因子。

综上，可以得到三个不存在合理数据的条件，可以由此特判输出 -1 。

接着，对于合理的数据，只要从 1 开始枚举获胜者的编号即可，如果害怕枚举出错，可以模拟比赛

过程，枚举当前场次的对手，这样获胜者的坐标不会出错且时间复杂度不变。

代码如下。

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { 	int t; 	cin>>t; 	while(t--) { 		int n,x,y; 		cin>>n>>x>>y; 		ll ans=0; 		int p=n-1; 		ll nowx=max(x,y),nowy=min(x,y);  		if (nowy!=0 || nowx+nowy==0 || p%nowx!=0) { 			puts("-1"); 			continue; 		}  		int i; 		int tot=1,k=2;  //用k模拟对手 		for (i=1; i<=p;) { 			for (int j=1; j<=nowx; j++) { 				cout<<tot<<" "; 				k++; 			} 			i=i+nowx; 			tot=k; 		} 		cout<<endl;  	} 	return 0; }

C.Parity Shuffle Sorting

大致题意

给定一组非负整数，可以最多进行 n 次操作，选取俩个数，当俩个数之和为奇数，可以把右边的数变成左边的数；如果是偶数，可以将左边的数变成右边的数。要求经过操作后得到一组非递减序列。

基本思路

依旧是一道思维题。

由于俩数之和为奇数时，右边的数可以变成左边的数，所以显然，每个与第一个数之和为奇数的数可以变成第一个数；反之，每个与最后一个数之和为偶数的数可以变成最后一个数。由此可得：每个数都可以变成第一个数或者最后一个数。

除此之外，根据操作规则，我们也能把第一个数变成最后一个数，或者把最后一个数变成第一个数。将头尾俩数变成同一个数之和，便可以将每个数都变成同一个数，操作次数最多为 n-1 次，即单组数据时间复杂度为 O(n) 。

需要注意的是，当 n=1 时，无需操作，可直接输出 0 ；整个程序时间复杂度为 O(n*t) ，因为俩个数最大都为 1e5 所以不能用 memset 函数初始化数组，不然会超时。（实际上也不需要初始化）

代码如下

代码

#include<bits/stdc++.h> using namespace std; const int N=100005; typedef long long ll; ll a[N]; int l[N],r[N]; int main() { 	int T; 	cin>>T; 	while(T--) { 		int n; 		cin>>n; 		for (int i=1; i<=n; i++) cin>>a[i]; 		int cnt=0; 		 		if (n==1){ 			puts("0"); 			continue; 		} 		 		if (a[1]!=a[n]) {  			if (a[1]%2==1 && a[n]%2==0) { 				l[++cnt]=1; 				r[cnt]=n; 				a[n]=a[1]; 			} else if (a[1]%2==1 && a[n]%2==1) { 				l[++cnt]=1; 				r[cnt]=n; 				a[1]=a[n]; 			} else if (a[1]%2==0 && a[n]%2==0) { 				l[++cnt]=1; 				r[cnt]=n; 				a[1]=a[n]; 			} else { 				l[++cnt]=1; 				r[cnt]=n; 				a[n]=a[1]; 			}  		}  		for (int i=2; i<=n-1; i++) { 			int now=a[i]+a[1]; 			if (now%2==0) { 				l[++cnt]=i; 				r[cnt]=n; 			} else { 				l[++cnt]=1; 				r[cnt]=i; 			} 		} 		 		cout<<cnt<<endl; 		for (int i=1; i<=cnt; i++) cout<<l[i]<<" "<<r[i]<<endl;  	}  	return 0; }