Codeforces Round 941 (Div. 2)（A,B,C,D,E）

比赛链接

这场难度不高，基本没考算法，全是思维题。B是推结论，C是博弈，D是构造，需要对二进制有一定理解，E是思维题，2300分的暴力和模拟。

A. Card Exchange

题意：

您有 $n$ 张牌，每张牌上都写着一个数字，还有一个固定整数 $k$ 。你可以多次进行下面的运算：

• 从手牌中任意选择 $k$ 张数字相同的纸牌。
• 将这些牌换成 $k-1$ 张牌，每张牌都可以替换成你选择的任何数字（包括你刚刚换的牌上写的数字）。

下面是第一个例子的一个可能的操作顺序，其中有 $k=3$ ：

在这个过程结束时，你手中最少有多少张牌？

思路：

如果一开始手上就没有 $k$ 张相同的牌，那么我们一次操作都做不了，这样答案就是 $n$。

如果有 $k$ 张及以上相同的牌，那么我们删掉这 $k$ 张，可以另选一张别的牌，把 $k-1$ 张这样的牌加入进来。以此类推，我们一定可以把牌的个数删到 $k-1$ 张，这时因为个数不够就不能再操作了。

code：

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
 
int T,n,k;
 
int main(){
	cin>>T;
	while(T--){
		cin>>n>>k;
		map<int,int> mp;
		for(int i=1,t;i<=n;i++){
			cin>>t;
			mp[t]++;
		}
		int maxx=0;
		for(auto [val,cnt]:mp)
			maxx=max(maxx,cnt);
		printf("%d\n",(maxx>=k)?k-1:n);
	}
	return 0;
}

B. Rectangle Filling

题意：

有一个由白色和黑色方格组成的 $n\times m$ 网格。在一次操作中，您可以选择任意两个相同颜色的方格，并将它们之间的子方格中的所有方格都染成相同的颜色。

具体来说，如果您选择了位置 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，这两个位置当前的颜色都是 $c$ ，那么就可以将 $(x,y)$ （其中 $\min (x_1,x_2)\le x\le \max (x_1,x_2)$ 和 $\min (y_1,y_2)\le y\le \max (y_1,y_2)$ 的颜色设置为 $c$ 。

此图显示了网格上两种可能的操作序列：

在进行任意次数（可能为零）的运算后，网格中所有方格的颜色是否可能相同？

思路：

假设我们把所有位置涂成白色，一个粗暴的想法是，如果两个对角位置（左上和右下，或者左下和右上）都是白色的就好了，这样选上这一对对角位置一次操作就可以了。但是事情不会这么顺利，对角位置有可能是黑的。

不过既然我们要把所有黑的位置都变成白的，所以不如我们先把一对对角位置清理出来，这样再选这对对角位置把其他位置清理成白色就行了。

拿左上角举例，如果要清理出来左上角，就必须保证第一行至少有一个白色位置，第一列至少有一个白色位置，同理其他角落位置。如果清理出左上和右下，就要保证第 $1$ 行，第 $n$ 行，第 $1$ 列，第 $m$ 列都各有至少一个白色位置。同理清理出左下和右上也需要上面这个条件。当一个角落位置本来就是白的，我们可以看作它所在行列同样是存在至少一个白色位置。因此我们只需要判断上面情况成立就行了。

同理涂成黑色的情况。

code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=505;
 
int T,n,m;
string s[maxn];
 
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>s[i];
			s[i]=" "+s[i];
		}
		vector<bool> f(8,false);
		for(int i=1;i<=m;i++)
			if(s[1][i]=='W')f[0]=true;
			else f[1]=true;
		for(int i=1;i<=m;i++)
			if(s[n][i]=='W')f[2]=true;
			else f[3]=true;
		for(int i=1;i<=n;i++)
			if(s[i][1]=='W')f[4]=true;
			else f[5]=true;
		for(int i=1;i<=n;i++)
			if(s[i][m]=='W')f[6]=true;
			else f[7]=true;
		if((f[0]&f[2]&f[4]&f[6]) || (f[1]&f[3]&f[5]&f[7]))puts("YES");
		else puts("NO");
	}
	return 0;
}

C. Everything Nim

题意：

爱丽丝和鲍勃正在玩一个关于 $n$ 堆石头的游戏。轮到每个棋手时，他们都会选择一个正整数 $k$ ，这个正整数最多等于最小的非空堆的大小，然后从每个非空堆中一次性取出 $k$ 个石子。第一个无法下棋的棋手（因为所有棋子都是空的）就算输。

既然爱丽丝先下，那么如果双方都以最佳方式下棋，谁会赢呢？

思路：

因为石子的顺序没有影响，所以不妨先排个序，因为是同时取走，所以石子个数相同的石子堆之间是一直保持相同的，所以我们还能去个重。然后因为我们在取第 $i$ 堆石子的时候，第 $i-1$ 堆石子一定被取完了，在取第 $i$ 堆石子的时候实际上我们是在对剩下的 $a_i-a_{i-1}$ 个石子来取。因此我们让第 $i$ 堆石子的个数等于 $a_i-a_{i-1}$，这样同时对所有石子堆取石子就变成了先取最前面的非空石子堆，取完再依次取后面的石子堆。

因为我们一次至少取一个石子，至多直接将这堆石子都取走。所以我们如果是先手的话，除非这堆石子只有一个石子，这时我们只能取走这堆石子。当石子堆石子个数大于 $1$ 时，我们其实是拥有决定谁来取下一个石子堆的权利的。

比如说如果我们想要下一堆石子我们先取，我们只需要将这个石子堆取到只剩一个，然后让对方取走这堆最后一个石子即可。反之我们直接取完这堆石子即可。

因为一个局面下一定只有必胜或者必败两种局面，因此先手或后手取下一堆石子一定一个为必胜的，一个为必败的。我们能决定谁来面对必胜局面，谁来面对必败局面，这时我们就已经赢了，也就是说 先手面对的石子堆的石子个数大于 $1$ 的局面 是必胜的。

不过有可能我们一开始面对的若干个石子堆的石子个数等于 $1$，并不大于 $1$。这时就是两个人轮流取，谁先取到最后一堆石子或者石子个数大于 $1$ 的石子堆，谁就赢了。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
 
int T,n,a[maxn];
 
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		sort(a+1,a+n+1);
		n=unique(a+1,a+n+1)-a-1;
		for(int i=n;i>=1;i--)a[i]-=a[i-1];
		
		bool win=true;
		for(int i=n-1;i>=1;i--)
			if(a[i]==1)win^=1;
			else win=true;
		
		puts((win)?"Alice":"Bob");
	}
	return 0;
} 

D. Missing Subsequence Sum

题意：

给你两个整数 $n$ 和 $k$ 。构造一个大小最多为 $25$ 的非负整数序列 $a$ ，使得下列条件成立。

• 没有和为 $k$ 的 $a$ 的子序列。
• 对于 $v\ne k$ 所在的所有 $1\le v\le n$ ，存在一个和为 $v$ 的 $a$ 的子序列。

如果 $b$ 可以从 $a$ 中删除几个（可能是零个或全部）元素，而不改变其余元素的顺序，那么序列 $b$ 就是 $a$ 的子序列。例如， $[5,2,3]$ 是 $[1,5,7,8,2,4,3]$ 的子序列。

可以证明，在给定的约束条件下，解总是存在的。

思路：

因为 $n=10^6$，而数组里只有 $25$ 个数，因为我们表示数字用的二进制，而且 $2^{20}>10^6$，这提示这个题我们需要用二进制来凑。

对于 $1\sim k-1$ 的部分，我们直接用二的次幂来凑，把 $2^0,2^1,2^2,\dots ,2^x(2^{x+1}-1\le k-1)$，加入进来，这样可以表示到 $2^{x+1}-1$，再加入一个 $k-1-(2^{x+1}-1)=k-2^{x+1}$ 即可。这样凑完，我们就不能加入任何一个 $1\sim k-1$ 的数了。

对于 $k+1\sim n$ 的部分。考虑到我们可以凑出 $1\sim k-1$ 的所有数，所以高位我们只要能凑出 $k$ 的倍数就行了，一个倍数到下一个倍数之间正好就差 $1\sim k-1$。

凑倍数同理还是用二的次幂来凑，把 $2^0\ast k,2^1\ast k,2^2\ast k,\dots ,2^x\ast k(2^x\ast k\le n)$，但是我们不能加入 $2^0\ast k$ 也就是 $k$，作为替代，我们加入 $3\ast k$ 即可（这样可以保证凑出 $k$ 的 $\ge 2k$ 倍数，可以这样来想，如果 $a\ast k$ 的 $a$ 二进制第 $0$ 位为 $1$，那么 $a-3$ 第 $0$ 位为 $0$，剩下的部分就可以用若干二的次幂来凑）。

不过这样会剩下 $k+1\sim 2k-1$ 的部分，我们直接加入 $k+1$ 即可，因为我们可以凑出 $1\sim k-1$ 的所有数，所以我们带上 $k+1$ 就可以凑出 $k+1\sim 2k$ 的所有数。

因为我们一直插入的都是二的次幂，它增长的很快，对于 $1\sim k-1$ 的部分我们最多会插入 $\lfloor {\log }_{2}k\rfloor +1$ 个数，对于 $k+1\sim n$ 的部分我们最多会插入 $\lfloor {\log }_2\lfloor \frac{n}{k}\rfloor \rfloor +1$，总的加入的数的个数$$\lfloor {\log }_{2}k\rfloor +1+\lfloor {\log }_2\lfloor \frac{n}{k}\rfloor \rfloor +1\le {\log }_{2}k+{\log }_2\frac{n}{k}+2$$$$={\log }_{2}k+{\log }_{2}n-{\log }_{2}k+2$$$$={\log }_{2}n+2$$

$n$ 最多就 $10^6$，加入的总个数反正超不过 $25$。

code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
 
int T,n,k;
 
int main(){
	cin>>T;
	while(T--){
		cin>>n>>k;
		vector<int> ans;
		int i;
		for(i=0;(1<<i+1)<k;i++)ans.push_back((1<<i));
		if(k-(1<<i)>0)ans.push_back(k-(1<<i));
		
		if(k+1<=n)ans.push_back(k+1);
		if(2*k<=n)ans.push_back(2*k);
		if(3*k<=n)ans.push_back(3*k);
		for(int j=4;j*k<=n;j<<=1)
			ans.push_back(j*k);
		
		cout<<ans.size()<<endl;
		for(auto x:ans)
			cout<<x<<" ";
		cout<<endl;
	}
	return 0;
}

E. Folding Strip

题意：

有一张纸条，上面是长度为 $n$ 的二进制字符串 $s$ 。您可以将纸条折叠在任意一对相邻数字之间。

如果在折叠后，位于上方或下方的所有字符都匹配，则认为一组折叠有效。请注意，所有折叠都是同时进行的，因此折叠之间的字符不必匹配。

例如，这些是 $s=110110110011$ 和 $s=01110$ 的有效折叠：

折叠条的长度是指完成所有折叠后从上面看到的长度。因此，对于上面的两个例子，经过上面所示的折叠后，长度分别为 $7$ 和 $3$ 。

请注意，对于上述 $s=01110$ 的折叠，如果我们单独进行两个折叠中的任何一个，这都不是一个有效的折叠。然而，由于我们在完成所有折叠之前不检查有效性，因此这个折叠是有效的。

在完成一组有效的折叠后，你能形成的最小长度条带是多少？

思路：

折一折之后发现一个性质，就是如果有连续的奇数个 $0$ 或 $1$ 时，我们可以通过折过去再折回来（就是示例图片的第二个折法）的操作，把这连续的相同字符变成一个字符，而且不影响也不需要看其他位置。再推一下，发现连续的偶数个相同字符我们也可以通过这种折法变成两个相同字符。

如果我们事先将原本的字符串处理一下，把奇数个相同字符直接缩成一个字符，偶数个相同字符直接缩成两个字符，应该会好做一些。但是害怕处理后一些本来可以对称折起来的方法就不能折了，不过不用担心，如果可以对称折起来，说明两边完全一样，这样处理后两边仍然是完全一样的，还是可以对称折起来，所以处理一下不影响。

处理后的字符串会变成一串 $01$ 串，然后偶尔某个位置是两个相同字符，然后接下来又是一串 $01$。形如 $010101101001\dots$。对这个串，我们可以在所有两个相同字符的位置折一下，两边正好对称。我们要找折完后得到的纸条的长度，可以去模拟对折的时候左右端点的变化的过程，然后把到达的最左边和最右边的位置记录一下，最后左右端点之间的长度就是答案了。

code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=2e5+5;

int T,n;
string s;

void ggbond(vector<int>& bond){
	int len=0;
	for(int l=1,r=1;l<=n;l=r){
		while(r<=n && s[r]==s[l])r++;
//		cout<<l<<" "<<r<<endl;
		len++;
		if(((r-l)&1)==0){
			bond.push_back(len);
			len=1;
		}
	}
	bond.push_back(len);
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>s;
		s=" "+s;
		vector<int> bond;
		ggbond(bond);
		
		int l=0,r=0;
		for(int i=0,t=0;i<bond.size();i++){
			int len=bond[i];
			if(i&1){
				t=t-len;//向左翻折
				l=min(l,t);
			}
			else {
				t=t+len;//向右翻折
				r=max(r,t);
			}
		}
		
		cout<<r-l<<endl;
	}
	return 0;
}