【学习笔记】CF1779G The Game of the Century

挺有意思一道题。

对于普通的情况进行分析是困难的。那么比较好的思路是对特殊情况进行分析，然后得出结论。

我们考虑什么情况是“好”的，如果最外层构成了一个环，那么显然是“好”的，否则设最外层的角为$A$,$B$,$C$，并且$A\to B,B\to C,A\to C$。如果存在$C\to A$的路径，那么显然也是“好”的。那么只要求出$C\to A$的“最短路”即可。

我们可以换一个角度检验这个下界的正确性。我们可以看到，如果某一层的边全是自上而下（或自下而上）的话，那么就会出现断层，因此这一层至少翻转一条边。如果存在$C\to A$的路径，那么就不会出现断层，因此上述下界是合理的。

实际实现时，直接数断层的数量更为简便。复杂度$O(n)$。

#include<bits/stdc++.h>
using namespace std;
int T,n;
string s1,s2,s3;
int solve(string s,string t){
	int res(0);
	for(int i=n-1;i>=0;i--){
		if(i<n-1&&(s[i]!=s[i+1]||t[i]!=t[i+1])||s[i]==t[i])return res;
		res++;
	} 
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>s1>>s2>>s3;
		cout<<min(n,solve(s1,s2)+solve(s1,s3)+solve(s2,s3))<<"\n";
	}
}