[POJ1733]Parity game（并查集 + 离散化）

传送门

题意：有一个长度已知的01串，给出[l,r]这个区间中的1是奇数个还是偶数个，给出一系列语句问前几个是正确的

思路：如果我们知道[1,2][3,4][5,6]区间的信息，我们可以求出[1,6]的信息

　　　可以将将闭区间[x,y]转换成(x 1,y]左开右闭区间

　　　那么我们可以用并查集来做，每次输入两个数 x 和 y 判断两者是否在同一并查集中，如果在，那么可以直接判断奇偶

　　　如果两者不在同一并查集中将两者合并，并求出两者的根之间的距离

　　　距离可在 find 函数中维护

注意：数据范围比较大，需要离散化

——代码

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define N 1000001 5 6 int n, m, cnt, ans; 7 int a[N], b[N], q[N << 1], f[N << 1], d[N << 1]; 8 char s[N][10]; 9 10 inline int read() 11 18 19 inline int find(int x) 20 27 return f[x]; 28 } 29 30 int main() 31 45 std::sort(q + 1, q + cnt + 1); 46 cnt = std::unique(q + 1, q + cnt + 1) q 1; 47 for(i = 1; i <= cnt; i++) f[i] = i, d[i] = 0; 48 for(i = 1; i <= m; i++) 49 58 else 59 ans++; 64 } 65 printf("%d\n", ans); 66 } 67 return 0; 68 }
View Code

上一篇：[CODEVS1911] 孤岛营救问题（分层图最短路）

下一篇：[CODEVS1912] 汽车加油行驶问题（分层图最短路）

---

并查集 离散化