poj 1733 Parity game（种类并查集）-白红宇

poj 1733 Parity game（种类并查集）

阅读量：4949 次

发布时间：2019-06-11

本文共 1057 字，大约阅读时间需要 3 分钟。

题意：

有0或1构成的一段区间总长度为n。m个询问，每次询问一段区间1的个数为奇数还是偶数，问从第一个询问開始，前几个询问正确的个数有几个；

思路：

n<=10^9，m<=5000;非常多数用不到，所以能够离散化一下；

将和为奇数的区间标记为1，为偶数的区间标记为0。

对于每一个询问，合并操作时。假设两区间重合且奇偶性之和与询问所给的奇偶性同样，则该询问正确，否则错误；

若区间不重合。合并区间，并合并奇偶性；

#include
      
       #include
       
        #include
        
         #include
         #include
          
           using namespace std;int n,m,t,cnt,ans;char ch[10];int fa[5000100],w[5000100];void init(){    for(int i=0;i<5000100;i++)    {        fa[i]=i;w[i]=0;    }}int find(int x){    if(x==fa[x]) return x;    int temp=fa[x];    fa[x]=find(fa[x]);    w[x]=(w[x]+w[temp])%2;    return fa[x];}int combine(int x,int y,int d){    int t1=find(x);    int t2=find(y);    if(t1==t2)    {        if((w[x]+w[y])%2==d) return 1; //奇偶性同样，则正确        else return 0;    }    else{        fa[t1]=t2;        w[t1]=(w[x]+w[y]+d)%2; //更新区间奇偶性        return 1;    }}int main(){    int i,j,k,a,b,x,y,d;    scanf("%d%d",&n,&m);    init();    map
           
            mm; cnt=ans=0; for(i=0;i

转载于:https://www.cnblogs.com/blfbuaa/p/7106156.html

你可能感兴趣的文章

MediaWiki左侧导航栏通过特殊页面就可以设置。