1. 奇偶游戏
题意： 依次给出多个区间的含 1 11 的个数的奇偶性，找出第一个不符合的答案的回答。
思路：
如此发现，传递性形同于异或，即将给定的区间【a,b】的奇偶性，可视为【1,a-1】区间和【1,b】区间的奇偶性的异或结果，这是因为异或的前缀和性质，读者可自行了解（简单理解：x xx xor x xx = 0 =0=0）。所以给定一个区间【a,b】的奇偶性，实际上可以转化为A − 1 A-1A−1和B BB的奇偶性。（ 大写A AA 定义为前缀和序列：【1,a】区间）
由上转化，我们需要维护的是前缀和序列的奇偶性：
【a,b】奇：A − 1 A-1A−1 和 B BB不同类。（01，10）
【a,b】偶：A − 1 A-1A−1 和 B BB 同类。（00，11）
我们可以通过并查集维护这种具有连通性，传递性的关系。考虑如下：（为了书写简便，以下用A代替上述推导的A-1了）
定义边权d [ u ]:
d [ u ] = = 0 d[u]==0d[u]==0，表示 u uu 与父节点 p [ u ] p[u]p[u] 奇偶性同。
d [ u ] = = 1 d[u]==1d[u]==1，表示 u uu 与父节点 p [ u ] p[u]p[u] 奇偶性不同。
如图所示，A AA 与 p [ A ] p[A]p[A] 同，p [ A ] p[A]p[A] 与 r A rArA 不同，那么如何推得 A AA 与根节点 r A rArA 的关系也是不同呢？显然 d [ A ] d[A]d[A] xor d [ p [ A ] ] d[p[A]]d[p[A]] 就是答案。所以在路径压缩中，每个节点只需要做如上所述的异或运算即可得到和根节点的奇偶性关系。
那么在一个集合中，得到了每个节点和根节点的奇偶性关系，通过传递性，就可以知道该集合中的任意两个节点之间的关系了。
上述考虑完并查集的路径压缩以及同属一个集合之间节点的关系，现在考虑一下如何合并两个集合。
读者可能会思考：上述判断不成立只有在同属于一个集合的情况下才会去判断，那么不属于一个集合然后合并的时候会不会存在矛盾呢？由于异或，由于传递性，是不会产生矛盾的。可以模拟一下各种情况。
代码：
#include <iostream> #include <cstring> #include <algorithm> #include <set> using namespace std; const int N = 200010; int n, m; int p[N], d[N]; int a[N << 1]; int find(int x) // 并查集 { if (p[x] != x) { int r = find(p[x]); // d[x] ^= d[p[x]]; // 路径压缩中的权值计算 d[x] += d[p[x]]; d[x] %= 2; p[x] = r; } return p[x]; } struct node { int a, b, c; }; node f[N << 1]; /* 由于题目数据太大，所以这里需要离散化处理。 此程序采用set离散化，注意需要用到的值还包含x-1。 */ int main() { cin >> n >> m; for (int i = 0; i < N; i++) p[i] = i; set<int> s; for (int i = 0; i < m; i++) { int u, v; string c; cin >> u >> v >> c; int x; if (c == "odd") { x = 1; } else { x = 0; } f[i] = {u, v, x}; s.insert(u), s.insert(v); s.insert(u - 1), s.insert(v - 1); } int idx = 0; for (auto c: s) a[++idx] = c; for (int i = 0; i < m; i++) { int u = f[i].a, v = f[i].b, c = f[i].c; int A = lower_bound(a + 1, a + 1 + idx, u - 1) - a, B = lower_bound(a + 1, a + 1 + idx, v) - a; int fx = find(A), fy = find(B); bool o = true; if (fx == fy) { // if ((d[A] ^ d[B]) != c) o = false; if ((d[A] + d[B]) % 2 != c) o = false; } else { p[fx] = fy; // d[fx] = d[A] ^ d[B] ^ c; d[fx] = d[A] + d[B] + c; } if (!o) { cout << i << endl; return 0; } } cout << m << endl; return 0; }
2. 银河英雄传说
思路：
代码：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 2e6 + 10; int p[N], dis[N], siz[N]; int find(int x) // 并查集 { if (p[x] != x) { int r = find(p[x]); dis[x] += dis[p[x]]; p[x] = r; } return p[x]; } int main() { int n; scanf("%d", &n); for (int i = 0; i < N; i++) siz[i] = 1, p[i] = i; int a, b; char op[2]; for (int i = 0; i < n; i++) { scanf("%s%d%d", &op, &a, &b); int fx = find(a), fy = find(b); if (op[0] == 'M') { if (fx != fy) { p[fx] = fy; dis[fx] = siz[fy]; siz[fy] += siz[fx]; } } else { if (fx != fy) { printf("-1\n"); } else printf("%d\n", max(0, abs(dis[b] - dis[a]) - 1)); } } return 0; }
