首页 > 其他 > 详细

<JZOJ5910>duliu

时间:2018-10-19 21:09:50      阅读:157      评论:0      收藏:0      [点我收藏+]

愤怒

考场想到正解

然后觉得我的“正解”和正解差不多 一样的效果

被忽略的与正解的不同也想到了

然而 我懒得再写

于是快乐10

气坏了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define rint register int
using std::sort;
using std::map;
//using std::cout;
//using std::endl;
template <class T>inline void read(T &X)
{
    X=0;int W=0;char ch=0;
    while(!isdigit(ch))W|=ch==-,ch=getchar();
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    X=W?-X:X;return;
}
int n,cnt=0,ans=0;
long long sta[100010],end[100010],xors=0,xore=0,sta2[100010],end2[100010],fa[100010];
bool boo(true);
long long find(long long x){return fa[x]==x?x:fa[x]=find(fa[x]);}
map<int,int>num;
int main()
{
//    freopen("duliu.in","r",stdin);
//    freopen("duliu.out","w",stdout);
    read(n);
    for(rint i=1;i<=n;++i)
        read(sta[i]),sta2[i]=sta[i],xors^=sta[i];
    sta[n+1]=xors;sta2[n+1]=xors;
    for(rint i=1;i<=n;++i)
    {
        read(end[i]),end2[i]=end[i];
        xore^=end[i];
        if(xors==end[i])boo=false;
    }
    end[n+1]=xore;end2[n+1]=xore;
    ++n;
    sort(sta2+1,sta2+n+1);
    sort(end2+1,end2+n+1);

    for(rint i=1;i<=n;++i)
    {
        if(sta2[i]!=end2[i]){printf("-1\n");return 0;}
    }
    cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (sta[i]!=end[i]||i==n)
        {
            if (i<n) ans++;
            if (!num[sta[i]]) cnt++,num[sta[i]]=cnt;
            if (!num[end[i]]) cnt++,num[end[i]]=cnt;
        }
    }
    if (ans==0)
    {
        printf("0\n");
        return 0;
    }
    for (int i=1;i<=cnt;i++) fa[i]=i;
    for (int i=1;i<=n;i++) if (sta[i]!=end[i]) fa[find(num[sta[i]])]=find(num[end[i]]);
    for (int i=1;i<=cnt;i++) if (fa[i]==i) ans++;
    printf("%d\n",ans-1); 
return 0;
}

 

<JZOJ5910>duliu

原文:https://www.cnblogs.com/pile8852/p/9818669.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!