CF1450C2 Errich-Tac-Toe (Hard Version)

One_JuRuo · 2023-11-13 14:27:46 · 题解

思路

实际上，如果你会简单版本，那么困难版本也没有那么难了。

同样考虑构造一种通解，如下，

红色的格子改为 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;
}