C. Errich-Tac-Toe 构造

C1. Errich-Tac-Toe (Easy Version) （构造）

https://codeforces.com/contest/1450/problem/C1
题意：给定n*n矩阵，最初全为空，在其中可以放置X和O，若相同的连成一行或一列则获胜，每次操作可以将X->O||O->X，要求操作次数< \(\lfloor \frac {k} {3} \rfloor\)， k为O和X总数，在easy中输入只有X。
n<=300
题解：看到\(\lfloor \frac {k} {3} \rfloor\) 想到可能是划分类，想到可以按(i+j)%3划分，任意连续的三个必然属于三个不同的类。只需将一个类中的X变为O，而根据抽屉原理，必有一类<=\(\lfloor \frac {k} {3} \rfloor\)。
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

char g[510][510];
int cnt[10];
void solve(){
	int n;cin>>n;
	for(int i=0;i<3;i++) cnt[i]=0;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		for(int j=1;j<=n;j++) g[i][j]=s[j-1];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(g[i][j]=='X') cnt[(i+j)%3]++;
		}
	}
	int mp=-1,sum=cnt[0]+cnt[1]+cnt[2];
	for(int i=0;i<3;i++){
		if(cnt[i]<=sum/3) mp=i; 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(g[i][j]=='.') cout<<g[i][j];
			else{
				if((i+j)%3==mp) cout<<'O';
				else cout<<g[i][j];
			}
		}
		cout<<endl;
	}
}
signed main(){
	int T;cin>>T;
	while(T--) solve();
}

C2. Errich-Tac-Toe (Hard Version)

https://codeforces.com/contest/1450/problem/C2
题意：与easy版本一致，但输入不在保证只有X。
题解：我们再思考，对于连续三个格不能为同一种颜色那么可以等价于至少有两种颜色，我们将任意两个不同类中一个取X一个取O排列组合，总共有6种可能性，记作f(i,j)，其中i表示选择i类的X全变为O，j表示选择j类的O全变为X，那么任意三个数中便会出现两种不同颜色了。由于∑f(i,j)=2k，故由抽屉原理，必有一个f(i,j)<=\(\lfloor \frac {2k} {6} \rfloor\),满足条件。
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

char g[510][510];
int f[10][10];
void solve(){
	int n;cin>>n;
	int cx[10]={0},co[10]={0};
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		for(int j=1;j<=n;j++) g[i][j]=s[j-1];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(g[i][j]=='X') cx[(i+j)%3]++;
			else if(g[i][j]=='O') co[(i+j)%3]++;
		}
	}
	int sum=0;
	pair<int,int> mp;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(i==j) continue;
			f[i][j]=cx[i]+co[j];
			sum+=f[i][j];
		}
	}

	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(i==j) continue;
			if(f[i][j]<=sum/6) mp={i,j};
		} 
	}
	auto [u,v]=mp;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(g[i][j]=='.') cout<<g[i][j];
			else{
				if(g[i][j]=='X'){
					if((i+j)%3==u) cout<<'O';
					else cout<<'X';
				}
				else{
					if((i+j)%3==v) cout<<'X';
					else cout<<'O';
				}
			}
		}
		cout<<endl;
	}
}
signed main(){
	int T;cin>>T;
	while(T--) solve();
}