CF1098B Nice table

话说考场上这题距离正解只差一步了，可惜我走错方向变成枚举左上角的block然后瞎鸡儿乱搞求min了。
事实上这一题猜到结论之后可以想到另一个更科学的做法。
具体来说，可以考虑，要么是行上两种字符交替出现而列上随意，要么是列上两种字符交替出现而行上随意。
所以我们可以枚举这些信息，然后检验一下即可。
顺便提一句，这一题的数据范围真的是恶意满满。考场上是瞎jb哈希，但是现在个人觉得还是string比较科学。

#include<iostream>
#include<cstdio>
#include<cstring>

#define MAXN 300005
char lst[6][2]={{'A','G'},{'A','C'},{'A','T'},{'C','T'},{'G','T'},{'C','G'}};
std::string ch[MAXN],out[MAXN];
int n,m,cnt[MAXN][2],val[MAXN][6][2],nw[2];

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=m;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[i][k-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[i][k-1]);
			}
			val[i][j][0]=(int)(nw[0]>=nw[1]);
			cnt[j][0]+=std::min(nw[0],nw[1]);
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=n;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[k][i-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[k][i-1]);
			}
			val[i][j][1]=(int)(nw[0]>=nw[1]);
			cnt[j][1]+=std::min(nw[0],nw[1]);
		}
	}
	int ans=0x3f3f3f3f;
	int pi,pj;
	for(int i=0;i<2;++i){
		for(int j=0;j<6;++j){
			ans=(cnt[j][i]<ans)?pi=i,pj=j,cnt[j][i]:ans;
		}
	}
	if(!pi){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				putchar(lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][0])]); 
			}
			puts("");
		}
	}else{
		for(int i=1;i<=m;++i){
			for(int j=1;j<=n;++j){
				out[j]+=lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][1])];
			}
		}
		for(int i=1;i<=n;++i){
			std::cout<<out[i]<<std::endl;
		}
	}
}

int main(){
	init();
	return 0;
}