Codeforces Round 941 (Div. 2) （A~D）

1966A - Card Exchange 

        题意：

       思路：手玩一下发现当存在某个数字个数超过k个，那么就能一直操作下去。那么答案就是k-1.

void solve() 
{
	cin >> n >> m;
	map<int,int>mp;
	int maxx = 1;
	for(int i = 0 ; i < n ; i ++){
		int x;
		cin >> x;
		mp[x]++;
		maxx = max(maxx , mp[x]);
	}	
	if(n < m){
		cout << n <<endl; 
	}
	else{
		if(maxx >= m){
			cout  << m - 1 << endl;
		}
		else{
			cout << n <<endl;
		}
	}
}      

1966B - Rectangle Filling 

        题意：

        思路：若要使得所有方格同色，关键在于四个角上的颜色，若对角上的颜色一样就能直接将所有格子变为同色。因此本题变为能否使得对角上颜色相同，分类讨论

void solve() 
{
	cin >> n >> m;
	int mp[n + 5][m + 5];
	for(int i = 1 ; i <= n ;  i ++){
		string str;
		cin >> str;
		for(int j = 1 ; j <= m ; j ++){
			if(str[j - 1] == 'W'){
				mp[i][j] = 1;
			}
			else
				mp[i][j] = 0;
		}
	}	
	if(n == 1){
		if(mp[1][1] != mp[1][m]){
			cout << "NO\n";
		}
		else{
			cout<<"YES\n";
		}
		return;
	}
	if(m == 1){
		if(mp[1][1] == mp[n][1]){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
		return;
	}
	if(mp[1][1] == mp[n][m] || mp[1][m] == mp[n][1]){
		cout<<"YES\n";
	}
	else{
		if(mp[1][1] == mp[1][m]){
			for(int i = 1 ; i <= m ; i ++){
				if(mp[1][i] != mp[1][1]){
					cout <<"YES\n";
					return;
				}
			}
			for(int i = 1 ; i <= m ; i ++){
				if(mp[n][i] != mp[n][1]){
					cout <<"YES\n";
					return;
				}
			}		
			cout <<"NO\n";
		}
		else{
			for(int i = 1 ; i <= n ; i ++){
				if(mp[i][1] != mp[1][1]){
					cout <<"YES\n";
					return;
				}
			}
			for(int i = 1 ; i <= n ; i ++){
				if(mp[i][m] != mp[n][m]){
					cout <<"YES\n";
					return;
				}
			}		
			cout <<"NO\n";			
		}
	}
}    

1966C - Everything Nim 

        题意：

        思路：为了方便考虑，我们令所有大小相同的堆为一个堆。接下来考虑终态：即只剩下一个堆。然后考虑若此时存在两个堆，那么对于Alice而言，其操作可以使得小的那个堆只剩下1，下一步Bob必须选1，然后Alice就胜利了。相反，若小的那个堆一开始就是1，那么Alice就输了。接下来推广到若干堆的情况：对于任意一方而言，若最小堆不是1，那么便可以控制胜利，于是我们只需要枚举到最小堆不是1的情况即可，然后看是谁在操作就是谁赢。

void solve() 
{
	cin >> n;
	set<int>st;
	for(int i = 1 ; i <= n ; i ++){
		int x;
		cin >> x;
		st.insert(x);
	}	
	vector<int>v;
	for(auto it : st)
		v.pb(it);
	vector<int>tag;
	int len = v.size();
	int cnt = 1;
	for(int i = 1 ; i < len ; i ++){
		if(v[i] - v[i - 1] == 1){
			cnt++;
		}
		else{
			tag.pb(cnt);
			cnt = 1;
		}
	}
	tag.pb(cnt);
/*	for(auto it : tag){
		cout << it << endl;
	}*/
	if(tag.size() == 1){
		if(v[0] == 1){
			if(tag[0] & 1){
				cout <<"Alice\n";
			}
			else{
				cout<<"Bob\n";
			}
		}
		else{
			cout<<"Alice\n";
		}
	}
	else{
		if(v[0] == 1 && tag[0] % 2 == 1){
			cout <<"Bob\n";
		}
		else
			cout<<"Alice\n";
	}
//	cout << endl;
}   

1966D - Missing Subsequence Sum 

        题意：

       思路：首先处理 < k 的部分，我们可以通过二进制的思想来构造整数，例如可以用来表示，其中36代表了99-63 .接下来考虑 > k 的部分，考虑到一个规律：可以表示的任何数,也就是说通过再配合上前面的就能表示出任意>k的数了，这就是构造方案。

void solve() 
{
	//1 ~ 99 101 201 301
	//
	vector<int>ans;
	cin >> n >> m;
	int st = 1;
	int t = m;
	if(m == 1){
		ans.pb(2);
		ans.pb(3);
		ans.pb(4);
		int st = 8;
		for(int i = 3 ; i < 25 ; i ++){
			ans.pb(st);
			st *= 2;
		}
		cout << ans.size() << endl;
		for(auto it : ans){
			cout << it <<" ";
		}
		cout << endl;
		return ;
	}
	while(st < t){
		ans.pb(st);
		t -= st;
		st *= 2;
	}
	if(t - 1)
		ans.pb(t - 1);
	ans.pb(m + 1);
	ans.pb(m * 2 + 1);
	ans.pb(m * 3 + 1);
	ans.pb(m * 4 + 1);
	st = m * 8 + 1;
	int len = ans.size();
 
	for(int i = len + 1; i <= 25 ; i ++){
		ans.pb(st);
		st = st * 2 - 1;
	}
	cout << ans.size() << endl;
	for(auto it : ans){
		cout << it <<" ";
	}
	cout << endl;
}