题目链接：https://codeforces.com/problemset/problem/1099/E
You are given an $n×m$ table, consisting of characters «A», «G», «C», «T». Let's call a table nice, if every $2×2$ square contains all four distinct characters. Your task is to find a nice table (also consisting of «A», «G», «C», «T»), that differs from the given table in the minimum number of characters.
Input
First line contains two positive integers $n$ and $m$ — number of rows and columns in the table you are given $(2≤n,m,n×m≤300000)$. Then, $n$ lines describing the table follow. Each line contains exactly $m$ characters «A», «G», «C», «T».
Output
Output $n$ lines, $m$ characters each. This table must be nice and differ from the input table in the minimum number of characters.
Examples
Input
2 2
AG
CT
Output
AG
CT
Input
3 5
AGCAG
AGCAG
AGCAG
Output
TGCAT
CATGC
TGCAT
Note
In the first sample, the table is already nice. In the second sample, you can change $9$ elements to make the table nice.
题解：
一个 nice table 必然属于以下两种情况：
1、每行都由两个字符交替组成，相邻两行的字符集合交集为空；
2、每列都由两个字符交替组成，相邻两列的字符集合交集为空。
对于上述两种情况中的一种，不妨先对于每行，枚举其可能的字符集，而对于一个字符集，又有正序和逆序两种情况。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+;
const char choice[][]={{'A','C'},{'A','G'},{'A','T'},{'C','G'},{'C','T'},{'G','T'}}; int n,m;
string str[maxn]; int ord[][maxn][],cnt[][maxn]; string out[maxn];
void print(int rc,int k)
{
for(int i=;i<n;i++) out[i]="";
if(rc==) //R
{
for(int i=;i<n;i++)
for(int j=;j<m;j++)
out[i]+=choice[(i&)?-k:k][(j&)^ord[][i][k]];
}
else //C
{
for(int j=;j<m;j++)
for(int i=;i<n;i++)
out[i]+=choice[(j&)?-k:k][(i&)^ord[][j][k]];
}
for(int i=;i<n;i++) cout<<out[i]<<endl;
}
int main()
{
cin>>n>>m;
for(int i=;i<n;i++) cin>>str[i]; memset(cnt,,sizeof(cnt));
for(int i=;i<n;i++)
{
for(int k=;k<;k++)
{
int now1=, now2=;
for(int j=;j<m;j++)
{
now1+=(str[i][j]!=choice[(i&)?-k:k][j&]);
now2+=(str[i][j]!=choice[(i&)?-k:k][(j&)^]);
}
ord[][i][k]=now1<now2?:; //0正序，1逆序
cnt[][k]+=min(now1,now2);
}
}
for(int j=;j<m;j++)
{
for(int k=;k<;k++)
{
int now1=, now2=;
for(int i=;i<n;i++)
{
now1+=(str[i][j]!=choice[(j&)?-k:k][i&]);
now2+=(str[i][j]!=choice[(j&)?-k:k][(i&)^]);
}
ord[][j][k]=now1<now2?:; //0正序，1逆序
cnt[][k]+=min(now1,now2);
}
} int ans=0x3f3f3f3f,RC,K;
for(int rc=;rc<=;rc++)
{
for(int k=;k<;k++)
{
if(cnt[rc][k]<ans) ans=cnt[rc][k], RC=rc, K=k;
}
}
//cout<<ans<<endl;
print(RC,K);
}
（注：借鉴了https://www.luogu.org/blog/xht37/cf1098bcf1099e-nice-table的代码，到了这个点心态真的要放平……心态不稳代码基本不可能AC……）