POJ1733 Parity game(并查集模型+带权并查集+离散化)

思路：一类经典的并查集题目，经典模型就是将[l,r]这个区间化为(l-1,r]，那么1的个数就可以表示为sum[r]-sum[l-1]，也就确定了奇偶性，我们可以用r[]数组表示这个端点到它的根节点的1的奇偶（这个区间就是(i,root(i)]（0代表偶，1代表奇）  对于每个输入的区间，我们查找它们的根节点是否相同

          如果相同，证明这个区间的奇偶性在之前已经得知，那么直接判断即可

          如果不同，那么就是u-1与v此时不在同一个集合中，那么我们可以知道(u-1,root([u-1])]区间和(v,root([v])]区间1的奇偶，并且我们知道了(u-1,v]区间1的奇偶，那么就可以推算出(root([u-1]),root([v])]区间的属性，进而合并两者。在合并时，根节点，r[root(u)]=r(u)^r(v)^r(u-1,v]， 在路径压缩过程中r[i]=r[i]^r[root(i)],比如(a,b]中1的个数为偶数，(b,c]中1的个数为奇数，(a,c]中1的个数显然为奇数

注意：这题目的点最大值高达10^9，而语句只有5000条，所以需要离散化一下

1. 把问题转化为并查集模型：
a b even等价于(0..a-1)与(0..b)同奇同偶
a b odd等价于(0..a-1)与(0..b)不同奇不同偶
我们用same和diff两个数组来代表每个点的相同和不同，比如令same[i]=i,diff[i]=i+10000(这个你随便加啦，只要不重复就好)。
对于集合的合并：
对于a b even,就union(same(a-1),same(b))，union(diff(a-1),diff(b))，表示a~b有偶数个的话，0~a-1必然和0~b是同奇同偶或异奇异偶。
对于a b odd,则union(same(a-1),diff(b))，union(diff(a-1),same(b))。
对于判断是否合法：
a b even，则find(same(a-1))=find(same(b))，此时必然同时有find(diff(a-1))=find(diff(b))
a b odd，则find(diff(a-1))=find(same(b))，此时必然同时有find(same(a-1))=find(diff(b))
这样就可以判断了.循环每个提问,先判断,不符合就continue, 否则union;

2. 解决01串长的问题——利用哈希表：
经过上面的分析还是不行，01串长度为十亿，你直接存必然MLE，但注意到问答之后5000个所以使用哈希表(开散列)，mod一个数，比如10009这样的质数。
这样的话经过映射就解决啦！不多说了，还不懂的话，去看程序。
总的来说，这道题综合了并查集和哈希表，而且需要一番思考才可以转化，是一道很有价值的题！

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 5005;
struct Node
{int u, v;char str[10];
}que[maxn];
int a[maxn*2], pre[maxn], r[maxn*2];
int Find(int x)
{if(x != pre[x]){int f = pre[x];pre[x] = Find(pre[x]);r[x] = r[x] ^ r[f];}return pre[x];
}
int main()
{int n, q, cnt;while(scanf("%d", &n) != EOF){cnt = 0;scanf("%d", &q);for(int i = 0; i < q; i++){scanf("%d%d%s", &que[i].u, &que[i].v, que[i].str);que[i].u--;a[cnt++] = que[i].u;a[cnt++] = que[i].v;}sort(a, a+cnt);cnt = unique(a, a+cnt) - a;for(int i = 0; i < cnt; i++){pre[i] = i;r[i] = 0;}int ans = 0;for(int i = 0; i < q; i++){int u = lower_bound(a, a+cnt, que[i].u) - a;int v = lower_bound(a, a+cnt, que[i].v) - a;int ra = Find(u);int rb = Find(v);if(ra == rb){if(r[u] == r[v] && que[i].str[0] == 'o')break;if(r[u] != r[v] && que[i].str[0] == 'e')break;ans++;}else{if(que[i].str[0] == 'o'){pre[ra] = rb;r[ra] = r[u]^r[v]^1;}else{pre[ra] = rb;r[ra] = r[u]^r[v];}ans++;}}printf("%d\n", ans);}return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 100005;
int head[maxn], nxt[maxn], fa[maxn], link[maxn], same[maxn], dif[maxn], tol;
int Hash(int x)
{int p = x % 99991;int i = head[p];while(i){if(link[i] == x)return i;i = nxt[i];}tol++;link[tol] = x;nxt[tol] = head[p];head[p] = tol;return tol;
}
int Find(int x)
{if(x != fa[x])fa[x] = Find(fa[x]);return fa[x];
}
int main()
{int n, q;while(scanf("%d%d", &n, &q) != EOF){tol = 0;memset(head, 0, sizeof(head));for(int i = 0; i <= 40000; i++)fa[i] = i;for(int i = 0 ; i <= 20000; i++)same[i] = i, dif[i] = i + 20000;int ans = 0, flag = 0;while(q--){int a, b;char str[10];scanf("%d%d%s", &a, &b, str);if(flag == 1)continue;a--;a = Hash(a);b = Hash(b);int a1 = Find(same[a]), a2 = Find(dif[a]), b1 = Find(same[b]), b2 = Find(dif[b]);if(str[0] == 'o'){if(a1 == b1 || a2 == b2){flag = 1;continue;}fa[a1] = b2;fa[a2] = b1;}else{if(a1 == b2 || a2 == b1){flag = 1;continue;}fa[a1] = b1;fa[a2] = b2;}ans++;}printf("%d\n", ans);}return 0;
}