[ARC095E] Symmetric Grid

遗传算法

首先观察题目范围很小，看上去可以随机化乱搞。相信各位都能想到模拟退火，不过其实还有一个算法竞赛中基本不会用到（事实上咱没有在 OI 题目中见过这个算法）的算法——遗传算法
不知道各位是否听说过遗传算法，它的核心思想就像生物学里的进化论一样，优胜劣汰。其实学习过生物学的各位听到这个名字应该可以自行推理出它的几个基本步骤：

1.变异：随机交换某一行或某一列，模仿生物中的变异过程；
2.择优：按照中心对称的失配数（你可以看做一个估价函数）排序；
3.适者生存：按照参数将后几名的对象淘汰，用前几名的参数赋值给他们。

然后循环以上几个步骤直到出现中心对称的情况输出 yes 或者循环次数达到上限输出 no 就行了。
事实上实际应用中的遗传算法比起这个要复杂得多，你也可以引入更多的随机变量或者多次运行算法防止陷入局部最优解。不过只是解决这道题的话上述这个最基本的模型已经够用了。这段代码非常简洁，咱应该 $10min$ 左右就写完了（切紫题最舒服的一次）
另外遗传算法在算法竞赛中的使用其实非常有限，本文权当科普了。一般来说还是要写模拟退火

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 14;
const int SIZE = 10;
const int LIVE = 5;
mt19937 rng(time(0));
int n,m;
struct POP{
	int nowval;
	char c[MAXN][MAXN];
	inline void Shuffle(){
		bool UD = rng() % 2;
		int up = UD ? n : m;
		int l = (rng() % up) + 1,r = (rng() % up) + 1;
		if(UD){
			for(int i = 1;i <= m;i++){
				swap(c[l][i],c[r][i]);
			}
		}else{
			for(int i = 1;i <= n;i++){
				swap(c[i][l],c[i][r]);
			}
		}
		return ;
	}
	inline void Calc(){
		nowval = 0;
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= m;j++){
				const int OPi = (n + 1) - i,OPj = (m + 1) - j;
				nowval += c[i][j] != c[OPi][OPj];
			}
		}
		return ;
	}
}pop[SIZE + 2];
bool Cmp(POP p1,POP p2){
	return p1.nowval < p2.nowval;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin>>pop[1].c[i][j];
		}
	}
	for(int i = 2;i <= SIZE;i++){
		pop[i] = pop[1];
	}
	int t = 10000;
	while(t--){
		for(int i = 1;i <= SIZE;i++){
			pop[i].Shuffle();
		}
		for(int i = 1;i <= SIZE;i++){
			pop[i].Calc();
		}
		sort(pop+1,pop+SIZE+1,Cmp);
		if(pop[1].nowval == 0){
			cout<<"YES"<<endl;
			return 0;
		}
		for(int i = LIVE+1;i <= SIZE;i++){
			pop[i] = pop[(i % LIVE)+1];
		}
	}
	cout<<"NO"<<endl;
	return 0;
}