首页 > 代码库 > codeforces 756A

codeforces 756A

2024-09-04 17:58:47   220人阅读

Input

4
4 3 2 1
0 1 1 1
Output
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;
}

 

codeforces 756A


联系
我们