Codeforces Round 941 (Div. 2)

[题目链接](https://codeforces.com/contest/1966)

A. Card Exchange

题意

给你n个牌，每个牌都有一个数字。

每次你可以选择恰好k个相同数字的牌， 然后将他们替换为任意的k-1张牌。（这k-1张牌的上的数字任意）

问在经过一些操作后，最终能剩下的牌的数量最少是多少。

思路

最终剩下牌的数量 = n - 最多执行的操作次数。

所以我们很明显地发现，如果起初不存在相同的k个数，那么就无法进行操作，直接输出n即可。

给出结论，如果可以进行第一次操作，那么就可以使得最终牌的数量变为k - 1。

下面是证明：

我们设当前有n张牌 ， 在满足”存在相同的k张牌“的前提下， 有如下两种情况：

1. 只有k张牌，且全部相同。那么再进行一次操作就可以实现最终剩下k-1张牌。
2. 除了这k张牌之外，还有其他的牌（设他的值为num），那么我们就可以选择k-1张num来替换起初的k张相同牌， 这样就变为了总数为n-1的，仍然满足”存在相同的k张牌“的状态。最终会逐渐转化为第一种情况，并变为只剩k-1张牌的情况。

按照以上两种情况进行考虑，就可以保证最终会剩下k-1张牌。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n,k;
	cin>>n>>k;
	vector<int> cnt(105);
	rep(i,1,n){
		int num;cin>>num;
		cnt[num]++;
	}
	bool f = 0;
	rep(i,1,100){
		if(cnt[i] >= k ) f = 1;
	}
	if(!f){
		cout<<n<<endl;
		return ;
	}else{
		cout<<min(n,k-1)<<endl;
		return ;
	}
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

B. Rectangle Filling

题意

有一个n*m的表格，涂满了黑白两色。

规定如下操作： 每次选出两个相同颜色的格子， 让**”以他们为对角线的矩形区域“** 全部变为和选择方格同一种颜色。

在进行一些次数的操作后，能否使得整个n*m的表格全部变为某一种颜色。

思路

若四条边中同时存在某一种颜色，那么就可以将整个表格变为同一个颜色，否则就不可以。

比如有如下样例：

3 4
BWBB
WBWB
BBBW

我们可以将上面的表格变为白色， 只需从四个边中各自任意选出一个白色块W（可以重复选择某一块，如(3,4)这个W块，即作为靠下的边，也作为靠右边。）

我们选出至多四个块， 然后将他们作为操作时要选择的块，就可以使得整个表格变为这个颜色。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n,m;
	cin>>n>>m;
	int bl,br,bu,bd;
	int wl,wr,wu,wd;
	bl = bu = wl = wu = 0x3f3f3f3f;
	br = bd = wr = wd = -0x3f3f3f3f;
	rep(i,1,n){
		rep(j,1,m){
			char ch;cin>>ch;
			if(ch == 'B'){
				bl = min(bl,j);br = max(br,j);
				bu = min(bu,i);bd = max(bd,i);
			}else{
				wl = min(wl,j);wr = max(wr,j);
				wu = min(wu,i);wd = max(wd,i);
			}
		}
	}
	if(bl == 1 && br == m && bu == 1&&bd == n){
		cout<<"YES\n";return ;
	}
	if(wl == 1 && wr == m && wu == 1&&wd == n){
		cout<<"YES\n";return ;
	}
	cout<<"NO\n";
	return ;
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

C. Everything Nim

题意

有n个堆， 第$i$个堆初始有$a_i$ 个石头， $Alice$和$Bob$轮流进行操作，Alice先手，每次操作如下：

1. 选择一个数x，保证$x > 0$且x不大于 任何非空堆 的剩余石头数量。

2. 从所有的非空堆中都拿去x个石头。

最终无法操作（即所有堆全部为空）者会输掉比赛。

二人都选取最优策略，问谁会胜利

思路

我们先将堆按照从小到大的顺序排序， 并且去重。我们会从小到大地不断清空每一堆。

**情况一：**当某一堆和前一堆的数量只差1的时候， 清空这堆时别无他法，只能设置x为1，并拿走这堆的最后一个，（因为在清空前一个堆的时候已经将这一堆拿到只剩下1个石头）

**情况二：**如果这一堆和上一堆的数量差大于1，那么就可以选择

1. 全部拿走，即让对手去清空下一堆。
2. 拿到只剩一个， 即让自己去清空下一堆。

可以发现这两者会正好对应相反的结果， 而我们又可以从中任选一个，所以就一定会获胜。
于是就有如下结论：第一个遇到情况二的人会获胜。

注意考虑第一堆的数量情况，如果第一堆的数量大于2，那么Alice起手变获胜

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n;
	cin>>n;
	vector<int> a(n+5);
	rep(i,1,n){
		cin>>a[i];
	}
	sort(a.begin()+1,a.begin()+1+n);
	bool f = 1;
	int cnt = 0;
	for(int i = 0;i<n;i++){
		if(a[i] == a[i+1]) continue;
		if(a[i] == a[i+1] - 1){
			f ^= 1;
		}else{
			f^= 1;
			break;
		}
	}
	if(f)cout<<"Bob\n";
	else cout<<"Alice\n";
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

D. Missing Subsequence Sum

题意

给出n和k， 请你构造一个长度不大于25的数组， 保证：

• a中不存在某个子序列的和为k
• 对于任意$1\le v \le n , v \not= k$ ,都有 **a中存在某个子序列的和为k**

思路

k将$[1,n]$ 分割为了两部分， $[1,k-1]$和 $[k+1,n]$ ，我们分别构造这两部分。

对于$[1,k-1]$部分， 我们使用二进制数组来构造$[1,2,4,...,2^p,Q]$ , 这些数的组合可以表示出 $[1,2^{p+1}-1+Q]$ 之间的任意数，于是我们设置$2^{p+1}$ 为”小于等于k的 最大的二次幂数“ , 即$2^{p+1} \le k$且$2^{p + 2} > k$ 。而$Q = k - 2^{p+1}$ 。 这样我们就可以构造出所有的$[1,k-1]$ 的数。

对于$[k+1,n]$ 部分，我们先选两个数$k+1,k+2$ 。 此时我们可以表示出$[k+1,k+2]$之间的数，

我们设能表示的最大的数是mx, 那么下一个要表示的数$nxt$就是$mx + 1$ ,我们选择数$nxt -(k+1)$ 作为下一个要加的数，这时候就可以将”可表示区域“ 拓宽为$[k+1,mx+nxt-(k+1)]$ ,但是我们发现，如果$num = nxt - (k + 1) \le k$ 那么会导致k被$num + (k - num)$ 表示出来，就出现了问题，如果出现了这个问题，我们就不能直接将$nxt - (k+1)$ 插入答案序列中，而是选择换成$nxt$ 直接插入序列中。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n,k;
	cin>>n>>k;
	int mx = 0;
	int nx = 1;
	vector<int> ans;
	while(mx + (mx + 1) < k - 1){
		ans.push_back(mx+1);
		mx += mx + 1;
	}
	ans.push_back(k - 1 - mx);
	mx = k - 1;
	ans.push_back(k+1);
	ans.push_back(k+2);
	mx = k+2;
	while(mx < n){
		int tt = mx-k;
		if(tt <= k){
			ans.push_back(mx+1);
			mx += mx+1;
			continue;
		}
		ans.push_back(tt);
		mx += tt;
	}
	cout<<ans.size()<<endl;
	for(auto p : ans){
		cout<<p<<" ";
	}
	puts("");
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}