CodeForces - 1450C2 Errich-Tac-Toe (Hard Version)(思维+构造)

题目链接：点击查看

题目大意：给出一个大小为 n * m 的棋盘，规定不能有三个连续的 ' X ' 或三个连续的 ' O ' ，现在可以通过一次操作将 ' X ' 改成 ' O ' 或者将 ' O ' 改成 ' X '，请输出一种修改次数不超过  的构造方法，k 是总棋子数

题目分析：因为不允许有超过三个连续的棋子相连，所以可以将整个棋盘按照 模三取余 划分，大概是下图的样子（图来自官方题解）

对于模三取余的集合 { 0 , 1 , 2 } 来说，我们只需要任选两个数字 t1 和 t2，满足 t1 != t2 且 ，然后将 t1 位置的 X 全部替换成 O，对于 t2 位置同理，可以证明这样是一定存在解的

补充一句，这样将方格矩阵图根据行列划分成三分图真的太妙了，和之前做过的按照奇偶划分为二分图的一个题类似，由此是不是可以扩展成，将其划分成 n 分图呢

代码：
 

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=310;char maze[N][N];int cnt[3][2];int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){memset(cnt,0,sizeof(cnt));int n,k=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%s",maze[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(maze[i][j]=='.')continue; int pos=(i+j)%3;if(maze[i][j]=='X')cnt[pos][0]++;if(maze[i][j]=='O')cnt[pos][1]++;k++;}for(int t1=0;t1<3;t1++)for(int t2=0;t2<3;t2++){if(t1==t2)continue;if(cnt[t1][0]+cnt[t2][1]<=k/3){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if((i+j)%3==t1&&maze[i][j]=='X')maze[i][j]='O';if((i+j)%3==t2&&maze[i][j]=='O')maze[i][j]='X';}goto end;}}end:;for(int i=1;i<=n;i++)puts(maze[i]+1);}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1450C2 Errich-Tac-Toe (Hard Version)(思维+构造)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。