POJ 1733 Parity game（带权并查集）

题目大意：给你m条信息，每条信息告诉你区间l~r的1的个数是奇数还是偶数，如果后面出现信息跟前面矛盾则这条信息是错误的，问在第一条错误信息之前的正确信息数。

解题思路：对于l~r之间的1的个数的奇偶性，其实可以理解成r比l-1多的1的个数的奇偶，这样刚好可以跟前面一段区间连起来。分两个种类，奇数1，偶数0，同样满足0->1>0的关系像食物链一样。跟How Many Answers Are Wrong差不多。

代码：

 #include<cstdio>

 #include<cmath>

 #include<cctype>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<string>

 #define LC(a) (a<<1)

 #define RC(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 using namespace std;

 typedef long long LL;

 const int INF=0x3f3f3f3f;

 const int N=2e4+;

 int root[N],val[N];

 struct node{

     int l,r,cla;

 }arr[N];

 int X[N];

 int find(int x){

     if(root[x]==x)

         return x;

     int tmp=find(root[x]);

     val[x]=(val[x]+val[root[x]])%;

     return root[x]=tmp;

 }

 int bin_search(int l,int r,int x){

     while(l<=r){

         int mid=(l+r)/;

         if(X[mid]==x)

             return mid;

         else if(X[mid]<x)

             l=mid+;

         else

             r=mid-;

     }

     return -;

 }

 int main(){

     int n,m;

     while(~scanf("%d",&n)){

         scanf("%d",&m);

         int m1=,m2=,ans=;

         memset(val,,sizeof(val));

         for(int i=;i<=m;i++){

             char s[];

             scanf("%d%d%s",&arr[i].l,&arr[i].r,s);

             if(s[]=='e')

                 arr[i].cla=;

             else

                 arr[i].cla=;

             X[++m1]=arr[i].l;

             X[++m1]=arr[i].r;

         }

         //去重

         sort(X+,X++m1);

         for(int i=;i<=m1;i++){

             if(X[i]!=X[i-])

                 X[++m2]=X[i];

         }

         for(int i=;i<=m2;i++){

             root[i]=i;

         }

         for(int i=;i<=m;i++){

             int l=bin_search(,m2,arr[i].l)-;

             int r=bin_search(,m2,arr[i].r);

             int c=arr[i].cla;

             int t1=find(l);

             int t2=find(r);

             if(t1==t2){

                 if((val[l]+c)%!=val[r]){

                     ans=i-;

                     break;

                 }

             }

             else{

                 root[t2]=t1;

                 val[t2]=(val[l]-val[r]+c+)%;

             }

         }

         if(!ans)

             ans=m;

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

POJ 1733 Parity game（带权并查集）

最新文章

热门文章