有一个长度已知的01串，给出[l,r]这个区间中的1是奇数个还是偶数个，给出一系列语句问前几个是正确的
解法一：带权并查集。
#include<iostream> #include<algorithm> #define f(i,l,r) for(i=(l);i<=(r);i++) using namespace std; const int MAXN=5005; int fa[MAXN<<1],d[MAXN<<1]; int m,n,L; string s; struct Node{ int l,r,ans; }q[MAXN]; int h[MAXN<<1]; inline void Makeset() { int i; f(i,1,L){ fa[i]=i; } } inline int Find(int x) { if(fa[x]==x) return fa[x]; int root=Find(fa[x]); d[x]^=d[fa[x]]; return fa[x]=root; } int main() { ios::sync_with_stdio(false); int i,j; cin>>m>>n; f(i,1,n){ cin>>q[i].l>>q[i].r>>s; if(s=="even") q[i].ans=0; else q[i].ans=1; h[i+i-1]=q[i].l-1; h[i+i]=q[i].r; } sort(h+1,h+1+i+i); L=unique(h+1,h+1+i+i)-(h+1); Makeset(); f(i,1,n){ int x=lower_bound(h+1,h+1+L,q[i].l-1)-h; int y=lower_bound(h+1,h+1+L,q[i].r)-h; int fx=Find(x),fy=Find(y); if(fx==fy){ if(q[i].ans!=(d[x]^d[y])){ cout<<i-1<<endl; return 0; } } else{ fa[fx]=fy; d[fx]=d[x]^d[y]^q[i].ans; } } cout<<n<<endl; return 0; }解法二：扩展域并查集。
#include<iostream> #include<algorithm> #define f(i,l,r) for(i=(l);i<=(r);i++) using namespace std; const int MAXN=10005; struct Node{ int l,r,ans; }q[MAXN]; int fa[MAXN<<1],h[MAXN]; int L,n,m; string s; inline void Makeset() { int i; f(i,1,L+L){ fa[i]=i; } } inline int Find(int x) { return fa[x]==x?x:fa[x]=Find(fa[x]); } inline void Union(int x,int y) { x=Find(x);y=Find(y); fa[x]=y; } int main() { ios::sync_with_stdio(false); int i,j; cin>>m>>n; f(i,1,n){ cin>>q[i].l>>q[i].r>>s; if(s=="even") q[i].ans=0; else q[i].ans=1; h[i+i-1]=q[i].l-1; h[i+i]=q[i].r; } sort(h+1,h+1+i+i); L=unique(h+1,h+1+i+i)-(h+1); Makeset(); f(i,1,n){ int x=lower_bound(h+1,h+1+L,q[i].l-1)-h; int y=lower_bound(h+1,h+1+L,q[i].r)-h; if(q[i].ans==0){ if(Find(x)==Find(y+L)){ cout<<i-1<<endl; return 0; } Union(x,y); Union(x+L,y+L); } else{ if(Find(x)==Find(y)){ cout<<i-1<<endl; return 0; } Union(x+L,y); Union(x,y+L); } } cout<<n<<endl; return 0; }
