「题解」CF1450C2 Errich-Tac-Toe (Hard Version)

$update:$ 增加了 $\text{Reference}$

棋盘上有一些棋子，可以把 X 变成 O，也可以把 O 变成 X，从而使棋盘上横竖没有连续三个相同的棋子。

发现操作次数至多 $\lfloor\frac{k}{3}\rfloor$ 满足 抽屉原理 的格式，那么应用这个原理，问题就转化为了构造三个方案，使每个方案都为平局且操作总数为 $k$。

将所有格子分成三类，第 $i\ (i\in[0,3))$ 类包含所有的格子 $(x+y)\bmod 3=i$。

不难发现只要一类格子全是 X，另一类格子全是 O 就合法。

那么有三种构造方案：

• 把第 $0$ 类格子上的 X 全改为 O，第 $1$ 类格子上的 O 全改为 X。

• 把第 $1$ 类格子上的 X 全改为 O，第 $2$ 类格子上的 O 全改为 X。

• 把第 $2$ 类格子上的 X 全改为 O，第 $0$ 类格子上的 O 全改为 X。

显然这三种都能使局面变成平局，且操作总数为 $k$，所以操作次数最少的方案一定 $\leq \lfloor\frac{k}{3}\rfloor$。

$\texttt{Code:}$

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rint register int
using namespace std;
namespace IO{
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	inline int read(){
		int w=0,f=1; char ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
		while(ch>='0'&&ch<='9'){w=(w<<3)+(w<<1)+(ch^48); ch=getchar();}
		return w*f;
	}
	inline void write(int x){
  		static int sta[35]; int top=0;
  		if(x<0) putchar('-'),x=-x;
  		do{sta[++top]=x%10,x/=10;}while(x);
  		while(top) putchar(sta[top--]+48); puts("");
	}
}
using namespace IO;
namespace CL{
	#define fill(x,y) memset(x,y,sizeof(x))
	#define copy(x,y) memcpy(x,y,sizeof(y))

	const int maxn=305;
	
	int T,n,k,cnt1,cnt2,cnt3;
	int uid[maxn][maxn];
	char mp[maxn][maxn],ans1[maxn][maxn],ans2[maxn][maxn],ans3[maxn][maxn];
	inline void print(char s[maxn][maxn]){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) printf("%c",s[i][j]);
			puts("");
		}
	}
	inline void init(){
		fill(mp,'\0'),fill(ans1,'\0'),fill(ans2,'\0'),fill(ans3,'\0');
		k=cnt1=cnt2=cnt3=0;
	}
	
	inline int main(){
		T=read();
		while(T--){
			n=read();
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++){
					char ch=getchar();
					while(ch!='O' && ch!='X' && ch!='.') ch=getchar();
					if(ch!='.') k++;
					mp[i][j]=ch;
					uid[i][j]=(i+j)%3;
				}
			copy(ans1,mp),copy(ans2,mp),copy(ans3,mp);
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++){
					if(uid[i][j]==0 && mp[i][j]=='O') ans1[i][j]='X',cnt1++;
					if(uid[i][j]==1 && mp[i][j]=='X') ans1[i][j]='O',cnt1++;
				}
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++){
					if(uid[i][j]==1 && mp[i][j]=='O') ans2[i][j]='X',cnt2++;
					if(uid[i][j]==2 && mp[i][j]=='X') ans2[i][j]='O',cnt2++;
				}
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++){
					if(uid[i][j]==2 && mp[i][j]=='O') ans3[i][j]='X',cnt3++;
					if(uid[i][j]==0 && mp[i][j]=='X') ans3[i][j]='O',cnt3++;
				}
			if(cnt1<=k/3) print(ans1);
			else if(cnt2<=k/3) print(ans2);
			else if(cnt3<=k/3) print(ans3);
			init();			
		}
		return 0;
	}
}
signed main(){return CL::main();}

$\text{Reference}$

$2021$ 国家集训队论文 《信息学竞赛中构造题的常用解题方法》—蒋凌宇