思路
实际上,如果你会简单版本,那么困难版本也没有那么难了。
同样考虑构造一种通解,如下,
红色的格子改为 X
,绿色的格子改为 O
,就是一种通解,同样的,这样改可能会超过棋子总数的 \(\frac 1 3\)。
同样考虑将棋子按照位置分类,假如该棋子的位置是 \((i,j)\),那么按照 \((i+j)\bmod 3\) 的值分类即可,将值为 \(0\) 的看作第 \(0\) 类,值为 \(1\) 的看作第 \(1\) 类,将值为 \(2\) 的看作第 \(2\) 类。
显然的是,将所有第 \(0\) 类棋子改为 X
,所有第 \(1\) 类棋子改为 O
是一种方案,还有将第 \(1\2\) 类棋子改为 X
,所有第 \(2\3\) 类棋子改为 O
两种方案,总共三种方案,所需要更改的棋子数是将所有棋子全部改完所需要的次数。
根据抽屉原理,三种方案必定至少有一种方案需要的次数少于总棋子数的 \(\frac 1 3\),所以分别统计需要更改个数,最后随意选择一种合理的方案更改即可。
AC code
#include<bits/stdc++.h>
using namespace std;
int T,n,numx[3],numo[3],sum,xz;
char ch[305][305];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n),sum=numx[0]=numx[1]=numx[2]=numo[0]=numo[1]=numo[2]=0;
for(int i=1;i<=n;++i)
{
scanf("%s",ch[i]+1);
for(int j=1;j<=n;++j)
{
if(ch[i][j]=='O') ++numo[(i+j)%3],++sum;
if(ch[i][j]=='X') ++numx[(i+j)%3],++sum;//记录每种方案需要更改的棋子数
}
}
if(numx[0]+numo[1]<=sum/3) xz=0;
if(numx[1]+numo[2]<=sum/3) xz=1;
if(numx[2]+numo[0]<=sum/3) xz=2;//判断使用那种方法
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(ch[i][j]=='.') printf(".");
else
{
if((i+j)%3!=xz&&(i+j)%3!=(xz+1)%3) printf("%c",ch[i][j]);
else
{
if((i+j)%3==xz) printf("O");
else printf("X");
}//对应更改即可
}
}
puts("");
}
}
return 0;
}
标签:方案,改为,int,Hard,numx,CF1450C2,Version,棋子,numo
From: https://www.cnblogs.com/One-JuRuo/p/17829040.html