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

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

A.Consecutive Sum

大致题意

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

基本思路

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

代码

#include
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<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
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<" ";
				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
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<endl;
		for (int i=1; i<=cnt; i++) cout<" "<endl;

	}

	return 0;
}

---

2022.9.21更新内容

D1.Zero-One (Easy Version)

大致题意

给定俩个二进制数，可以进行操作同时将二进制数a的俩位取反，若俩位相邻，则贡献为 x ,否则为 y ，且 x>=y ，求使俩数相同的最小贡献。

基本思路

本题可用分类讨论进行分析。

首先，为了使俩数相同，可以先找出所有不同的位，计共有 cnt 位（也可以理解为俩个二进制数进行了异或和，最终为1的位就是原先不同的位），而目的就是将所有不同的位变成相同的数（即将所有 1 变成 0 （即cnt=0）。

由于要求同时使俩位数取反，每次操作造成的结果只可能使 cnt+2，cnt-2 ，或不改变 cnt。 所以，当cnt为奇数时，无论多少次操作都不能使 cnt 变为0，所以此时无解。

接下来，只有为偶数的 cnt 才会参与讨论。

当 cnt>2 时，我们能够轻易发现，既能通过相邻变换使 cnt 变为0，也能通过直接修改使其清空。但由于题目规定 x>=y ，所以我们需要优先选择修改的做法，此时只要全部的1都直接修改而不是相邻变换，就可达到最小贡献。(由于cnt>2，所以能够找出 (cnt/2) 对不相邻的 1 将他们直接修改为 0 )

而当 cnt=2 时: 若n只有2位，则只能相邻变换（不过题目规定 n>5）；若俩个1不相邻，只能通过直接修改得到答案；若不符合以上俩种情况，则既能相邻变换，也进行俩次直接修改得到答案。

至此，分类讨论结束。

代码如下

代码

#include
#include
using namespace std;
typedef long long ll;

int main() {
	int t;
	cin>>t;
	while(t--) {

		int n;
		ll x,y;
		cin>>n>>x>>y;

		string a,b;
		cin>>a>>b;
		vector<int> p;
		int cnt=0;

		for (int i=0; iif (a[i]!=b[i]) {
				cnt++;
				p.push_back(i);
			}
		}

		if (cnt%2==1) {
			puts("-1");
			continue;
		}

		if (cnt==2) {
			if (n==2) cout<endl;
			else if (p[0]+1!=p[1]) {
				cout<endl;
			} else {
				cout<2*y)<<endl;
			}
		} else {
			cout<<(cnt/2)*y<<endl;
		}

	}
	return 0;
}

---

D2.Zero-One (Hard Version)

大致题意

此题为 D1 的加强版，题目不再规定 x>=y ，数据范围也有小幅的增加。

除此之外并无变化。

基本思路

本题需要用到 DP 。

这题的 DP 方法有许多种（二维，三维方法皆有，但难于理解与实现），在这篇题解中主要介绍的是目前效率最高的一维 DP 。

首先，由于这一题是上一题的加强版，但数据范围变化不大，所以在 x>=y 时，仍然可以用上一题的分类讨论来解决。

事实上，由于 x>=y 的条件不存在了，对于每一个为 1 的位，不论是使用相邻变换 (若俩位不相邻，可以进行连续的相邻变换使俩位同时取反) 还是直接修改，都有可能取到最小贡献，所以这时，可以用一个dp数组维护最小贡献。

在开始dp之前，还需要说明的是：为达到最小贡献，若用相邻变换的方法取反 1 ，则只能与上一位 1 或下一位 1 使用次方法，不然贡献无法得到最优。

现在设置一个数组 dp[i] 表示在处理第 i 个 1 时的最小贡献，规定 i 从 0 开始计数。那么，当 i 为奇数时，则恰好有偶数个 1 ,这样，我们就可以让当前位与前一位相邻变换，或是直接让他与任意一个 1 直接修改，转移方程便是从这俩者中取最小。

所以 当 i为奇数时，转移方程为 :dp[i]=min(dp[i-1]+y,dp[i-2]+(i与i-1的距离)∗" role="presentation">∗$\ast$x)

而当 i为偶数时，即总共有奇数个 1 ，此时无法确保让当前位找到一个 1 直接与其修改，但能让他与前一位数进行相邻变换。

所以当 i 为偶数时，转移方程为 :dp[i]=min(dp[i-2]+(i与i-1的距离)∗" role="presentation">∗$\ast$x,dp[i-1])。

由此初始值应为 :dp[0]=0,dp[1]=min(y,x(1到0的距离)),dp[2]=min(dp[1],x(2到1的距离))

不过，这个dp还能进一步优化，例如我们只枚举奇数位，然后通过当前奇数位的贡献来得到下一个偶数位的贡献，只不过要注意下一个偶数位的坐标不能越界。

最终的答案即为 dp数组的最后一位。

代码如下。

代码

#include
#include
using namespace std;
typedef long long ll;
const ll INF=1e14;

int main() {
	int t;
	cin>>t;
	while(t--) {

		int n;
		ll x,y;
		cin>>n>>x>>y;

		string a,b;
		cin>>a>>b;
		vector<int> p;
		ll cnt=0;

		for (int i=0; iif (a[i]!=b[i]) {
				cnt++;
				p.push_back(i);
			}
		}

		if (cnt==0) {
			puts("0");
			continue;
		}
		if (cnt%2==1) {
			puts("-1");
			continue;
		}

		if (cnt==2 && p[0]+1==p[1]) {
			cout<2*y)<<endl;
			continue;
		}

		if (x>=y) {
			cout<2)<<endl;
			continue;
		}

		if (cnt==2) {
			cout<1]-p[0])*x)<<endl;
			continue;
		}

		vector dp(cnt);

		dp[0]=0;
		dp[1]=min(y,x*(p[1]-p[0]));
		dp[2]=min(dp[1],x*(p[2]-p[1]));

		for (int i=3; i2) {
			dp[i]=dp[i-1]+y;
			dp[i]=min(dp[i-2]+(p[i]-p[i-1])*x,dp[i]);
			if (i-1) dp[i+1]=min(dp[i-1]+(p[i+1]-p[i])*x,dp[i]);
		}
		cout<-1]<<endl;

	}

	return 0;
}

---

总结

Codeforces 的比赛前三题主要重视的是思维而非算法，并不能读完题就思考用什么算法解决问题，且题目的真意常常不如题面上描述的复杂，所以应该借助样例，探究其中的规律，了解题目的真实意图，这一点与 OI 注重算法思维的比赛有些许不同。

除此之外，由于有时不能直接借用某种算法来解决问题，所以还要会精确地计算时间复杂度，避免超时。当然，由于有可能被其他选手 hack ，在考虑问题的时候需要注意某些特别的数据。

总体而言，div.2的前三题相对简单，想要快速解决，应该多加锻炼思维能力（多打比赛）。

后三题的思维难度较高，但并没有涉及较深入或是很难的算法，毕竟只是 div2 ，但这也意味着，思维能力并不是算法能力能够弥补的，在学习算法的同时也要注意思维的训练。