本文主要是介绍Codeforces 1250 E The Coronation —— 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
给你n个串，对每一个串你可以进行一次翻转操作，使得最终这些串两两运算时，他们同一位置上的值相同的位置数最小的大于等于k，问你最少要反转多少个以及翻转哪几个。
题解：
自己想真的没有思路，看了题解恍然大悟是并查集。位置和i位置j的关系分成4种情况：
1.无论i和j是否翻转都<k：无解
2.不翻转i，翻转j之后>=k：i与j+n相连，i+n与j相连
3.不翻转i，不翻转j>=k：i与j相连，j与j+n相连
4.无论翻不翻转都<k：不连边
然后我们设置n+1-2n的点的权值为1，然后在判断取i还是i+n（就是不翻转与翻转）时只需要判断哪个并查集中的权值小即可。
#include<bits/stdc++.h>
using namespace std;
const int N=55;
char s[N][N];
int fa[N*2],sum[N*2],n,m,k;
int deal(int i,int j){int f1=0,f2=0,num=0;for(int k=1;k<=m;k++)if(s[i][k]==s[j][k])num++;if(num<k)f1=1;num=0;for(int k=1;k<=m;k++)if(s[i][k]==s[j][m-k+1])num++;if(num<k)f2=1;if(f1&&f2)return -1;if(f1&&!f2)return 0;if(!f1&&f2)return 1;return 2;
}
int finds(int x){return x==fa[x]?x:fa[x]=finds(fa[x]);}
void merge(int x,int y){int fax=finds(x),fay=finds(y);if(fax!=fay)fa[fay]=fax,sum[fax]+=sum[fay];
}
int vis[N*2];
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);memset(vis,0,sizeof(vis));memset(sum,0,sizeof(sum));for(int i=1;i<=n*2;i++)fa[i]=i;for(int i=n+1;i<=n*2;i++)sum[i]=1;for(int i=1;i<=n;i++)scanf("%s",s[i]+1);int f=0;for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){int ans=deal(i,j);if(ans==-1){f=1;break;}else if(!ans)merge(i,j+n),merge(i+n,j);else if(ans==1)merge(i,j),merge(i+n,j+n);}}if(f){printf("-1\n");continue;}vector<int>ans;ans.clear();for(int i=1;i<=n;i++){if(finds(i)==finds(i+n)){f=1;break;}else if(vis[finds(i)])continue;else if(vis[finds(i+n)])ans.push_back(i);else if(sum[finds(i)]>sum[finds(i+n)])ans.push_back(i),vis[finds(i+n)]=1;else vis[finds(i)]=1;}if(f){printf("-1\n");continue;}printf("%d\n",ans.size());for(auto i:ans)printf("%d ",i);printf("\n");}return 0;
}这篇关于Codeforces 1250 E The Coronation —— 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
