[poj1733] Parity game

题目链接

题意

??一个由0,1组成的序列，每次给出一段区间1的数量的奇偶，问哪一条信息不合法。

法一

??带权并查集。边权\(d[x]\)为0，表示\(x\)与\(fa[x]\)奇偶性相同；为1，表示\(x\)与\(fa[x]\)奇偶性不同。先检查\(x\)和\(y\)是否再同一个集合内（奇偶性是否已知），\(d[x]\bigoplus d[y]\)即为\(x\)和\(y\)的奇偶性关系，\(d[x]\bigoplus d[y]\neq op\)，则产生矛盾。若\(x\)和\(y\)不在同一个集合内，先找到树根\(fx\)和\(fy\)，\(fa[fx]=fy\)，由于\(op=d[x]\bigoplus d[y]\bigoplus d[fx]\)，从而\(d[fx]=d[x]\bigoplus d[y]\bigoplus op\)。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int 	N = 1e5 + 5, INF = 2e9;

int n, m, cnt;
int l[N], r[N], op[N], fa[N], a[N], d[N];
char ch[10];

int find(int x) {
	if (x != fa[x]) {
		int fx = find(fa[x]);
		d[x] ^= d[fa[x]];
		fa[x] = fx;
	}
	return fa[x];
}

void Union(int x, int y, int i) {
	int fx = find(x);
	int fy = find(y);
	fa[fx] = fy;
	d[fx] = d[x] ^ d[y] ^ op[i];
}

int main() 
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%s", &l[i], &r[i], ch);
		if (ch[0] == ‘o‘) op[i] = 1;
		a[++cnt] = l[i] - 1;
		a[++cnt] = r[i] - 1;
	}
	sort(a + 1, a + cnt + 1);
	n = unique(a + 1, a + cnt + 1) - a - 1;
	for (int i = 1; i <= n; ++i) fa[i] = i;
	for (int i = 1; i <= m; ++i) {
		int x = lower_bound(a + 1, a + n + 1, l[i] - 1) - a;
		int y = lower_bound(a + 1, a + n + 1, r[i]) - a;
		if (find(x) == find(y)) {
			if ((d[x] ^ d[y]) != op[i]) { printf("%d\n", i - 1); return 0; }
		}
		else Union(x, y, i);
	}
	printf("%d\n", m);
    return 0;
}

法二

??扩展域并查集，类似于食物链的处理方法，将每个变量\(x\)拆成两个节点\(x_{odd}\)和\(x_{even}\)，\(x_{odd}\)表示\(sum[x]\)为奇数，\(x_{even}\)表示\(sum[x]\)是偶数。

??对每个问题，离散化后\(l-1\)和\(r\)的值分别为\(x\)和\(y\)，\(op\)表示问题的判断。（1）\(op=0\)，合并\(x_{odd}\)和\(y_{odd}\)，\(x_{even}\)和\(y_{even}\)，即“\(x\)为奇数”与“\(y\)为奇数”，“\(x\)为偶数”与“\(y\)为偶数”。（2）\(op=1\)，合并\(x_{odd}\)和\(y_{even}\)，\(x_{even}\)和\(y_{odd}\)，即“\(x\)为奇数”与“\(y\)为偶数”，“\(x\)为偶数”与“\(y\)为奇数”。处理每个问题前，需要检查是否存在矛盾。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 1e5 + 5, INF = 2e9;

int n, m, cnt;
int l[N], r[N], op[N], fa[N], a[N];
char ch[10];

int find(int x) {
	if (fa[x] != x) {
		fa[x] = find(fa[x]);
	}
	return fa[x];
}

void Union(int x, int y) {
	fa[find(x)] = find(y);
}

int main() 
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%s", &l[i], &r[i], ch);
		if (ch[0] == ‘o‘) op[i] = 1;
		a[++cnt] = l[i] - 1;
		a[++cnt] = r[i];
	}
	sort(a + 1, a + cnt + 1);
	n = unique(a + 1, a + cnt + 1) - a - 1;
	for (int i = 1; i <= 2 * n; ++i) fa[i] = i;
	for (int i = 1; i <= m; ++i) {
		int x = lower_bound(a + 1, a + n + 1, l[i] - 1) - a;
		int y = lower_bound(a + 1, a + n + 1, r[i]) - a;
		if (!op[i]) {
			if (find(x) == find(y + n)) { printf("%d\n", i - 1); return 0; }
			Union(x, y);
			Union(x + n, y + n);
		}
		else {
			if (find(x) == find(y)) { printf("%d\n", i - 1); return 0; }
			Union(x, y + n);
			Union(x + n, y);
		}
	}
	printf("%d\n", m);
    return 0;
}

[poj1733] Parity game

原文：https://www.cnblogs.com/2inf/p/12805842.html