Input
4
4 3 2 1
0 1 1 1
2
4个饼 每一秒 都会到对应 上面一行的位置
0的话不翻转 1 翻转
要求 每个饼要到所有的位置
而且正反面都要到过所有的位置
我是思路是并查集 先看看有多少个换
显然是要和到一起的
然后1的个数如果是偶数的话就有问题 最少改变多少个数
#include<stdio.h> #include<algorithm> #include<string.h> #include<string> #include<math.h> using namespace std; #define MAXN 200010 int z[MAXN]; int x[MAXN]; int find1(int a) { if(a==z[a]) return a; else { int b=find1(z[a]); return z[a]=b; } } int c[5]; int main () { int n; scanf("%d",&n); for(int i=1;i<=n;i++) z[i]=i; for(int i=1;i<=n;i++) { int a,b,fa,fb; scanf("%d",&a); fa=find1(i); fb=find1(a); if(fa!=fb) z[fa]=z[fb]; } for(int i=1;i<=n;i++) { int a; scanf("%d",&a); c[a]++; } int ans1=0; for(int i=1;i<=n;i++) { x[i]=find1(i); if(i==x[i]) { ans1++; } } if(ans1==1) ans1--; if(c[1]%2==0) ans1++; printf("%d\n",ans1); return 0; }
原文：http://www.cnblogs.com/cherryMJY/p/6411411.html