POJ-1733___Parity game —— 种类并查集 + 离散化

本文主要是介绍POJ-1733___Parity game —— 种类并查集 + 离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门

题目大意：

  给一个长度为$n$的$01$字符串$n<=1000000000$，接下来有$m$个语句，每个操作会给给一个区间$l$~$r$，若后面是$even$则表示这个区间里有偶数个$1$，若后面是$odd$则表示这个区间里有奇数个$1$。
  最后问当第一个错误语句出现的时候，前面有多少句正确语句。

解题思路：

  区间并查集解决，如过并查集不是掌握的很好第一时间可能想到的是线段树，因为数据比较大。这里用离散化来处理大数据问题。

代码思路：

  离散化处理只需要注意$n$的大小对解题有没有影响，那么将语句中所有给出的数字放到一个数组里，排序+去重，得到的新序列即是离散化后的新序列，大小是相对的，因为我们只需要得到它在序列中的排位。
  判断语句不用多说，在路径压缩的时候注意$r[x]$ ^$=$ $r[fx]$，即在递归的时候不断判断奇偶性。
  还有一点，针对于并查集的区间问题，考虑到区间端点重合的问题，要将做端点$--$或者右端点$++$，区分好区间问题与种类问题

核心：熟练地掌握种类并查集的区间问题 和 离散化处理的优化

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
const int N = 5010;
int n, m, a[N*2];
int f[N*2], r[N*2];struct Q {int u, v;char s[5];
} q[N*2];int find(int x) {if(x != f[x]) {int fx = f[x];f[x] = find(f[x]);r[x] ^= r[fx];}return f[x];
}void init(int n) {for(int i=0; i<=n; i++) {f[i] = i;r[i] = 0;}
}int main() {scanf("%d%d", &n, &m);int ans=0, cnt=0;int fa, fb;for(int i=0; i<m; i++) {scanf("%d%d%s", &q[i].u, &q[i].v, &q[i].s);q[i].u--;a[cnt++] = q[i].u;a[cnt++] = q[i].v;}sort(a, a+cnt);cnt = unique(a, a+cnt) - a;init(cnt);for(int i=0; i<m; i++) {int u = lower_bound(a, a+cnt, q[i].u) - a;int v = lower_bound(a, a+cnt, q[i].v) - a;int fu = find(u);int fv = find(v);if(fu==fv) {if(r[u] == r[v] && q[i].s[0] == 'o') break;if(r[u] != r[v] && q[i].s[0] == 'e') break;ans++;} else {if(q[i].s[0] == 'o') {f[fv] = fu;r[fv] = r[u] ^ r[v] ^ 1;	//之间为单数，则异或 1} else {f[fv] = fu;r[fv] = r[u] ^ r[v];		//之间为复数，则不异或}ans++;}}printf("%d", ans);
}

这篇关于POJ-1733___Parity game —— 种类并查集 + 离散化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---