Parity game

POJ

题意:给一个01序列，现在随意拿出来一个区间，然后说出区间内含有奇数个1还是偶数个1，因为有可能存在假话，让你判断前多少条没有假话，也就是查找第一个假话的位置-1.序列长度\(n<=1e9\),区间数量\(m<=10000.\)

分析:边带权和扩展域都能够解决.个人认为扩展域并查集更好理解.

没时间分析了,留个坑,以后应该也不会回来补的.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int N=20005;
int b[N],fa[N],d[N];
struct ppx{int x,y,z;}a[N];
inline int get(int x){
    if(x==fa[x])return x;
    int root=get(fa[x]);
    d[x]^=d[fa[x]];
    return fa[x]=root;
}
int main(){
    int n,m,tot=0;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        char s[5];
        scanf("%d%d%s",&a[i].x,&a[i].y,s);
        if(s[0]=='o')a[i].z=1;
        else a[i].z=0;
        b[++tot]=a[i].x;b[++tot]=a[i].y;
    }
    sort(b+1,b+tot+1);
    int sum=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=m;++i){
        a[i].x=lower_bound(b+1,b+sum+1,a[i].x-1)-b;
        a[i].y=lower_bound(b+1,b+sum+1,a[i].y)-b;
    }
    for(int i=1;i<=sum;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        int p=get(a[i].x),q=get(a[i].y);
        if(p==q){
            if(d[a[i].x]^d[a[i].y]!=a[i].z){
                printf("%d\n",i-1);
                return 0;
            }
        }
        else{
            fa[p]=q;d[p]=d[a[i].x]^d[a[i].y]^a[i].z;
        }
    }
    printf("%d\n",m);
    return 0;
}


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int N=40005;
int b[N],fa[N];
struct ppx{int x,y,z;}a[N];
inline int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
int main(){
    int n,m,tot=0;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        char s[5];
        scanf("%d%d%s",&a[i].x,&a[i].y,s);
        if(s[0]=='o')a[i].z=1;
        else a[i].z=0;
        b[++tot]=a[i].x;b[++tot]=a[i].y;
    }
    sort(b+1,b+tot+1);
    int sum=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=m;++i){
        a[i].x=lower_bound(b+1,b+sum+1,a[i].x-1)-b;
        a[i].y=lower_bound(b+1,b+sum+1,a[i].y)-b;
    }
    for(int i=1;i<=2*sum;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        int x1=a[i].x,x2=a[i].x+sum;
        int y1=a[i].y,y2=a[i].y+sum;
        if(!a[i].z){
            if(get(x1)==get(y2)){
                printf("%d\n",i-1);
                return 0;
            }
            fa[get(x1)]=get(y1);
            fa[get(x2)]=get(y2);
        }
        else{
            if(get(x1)==get(y1)){
                printf("%d\n",i-1);
                return 0;
            }
            fa[get(x1)]=get(y2);
            fa[get(x2)]=get(y1);
        }
    }
    printf("%d\n",m);
    return 0;
}