Poj1733 Parity Game（带权并查集）

题面

Poj

题解

反正只要你判断是否满足区间的奇偶性，假设每一位要么是$1$要么是$0$好了。

假设有$S$的前缀和为$sum[]$，则有：

若$S[l...r]$中有奇数个$1$，则$sum[l-1]$与$sum[r]$不同奇偶；反之，则同奇偶

用一个带权并查集维护，设权值数组$s[i]$表示区间$[root[i]...i]$的和的奇偶性。

对于一个区间$[l,r]$，分情况讨论：

如果$root[l]=root[r]$，直接判断就行了。

否则的话，计算一下$s[fv]=t\oplus s[u]\oplus s[v]$

但是$n$太大了，需要离散化（懒人离散化用$map$，美滋滋）

#include <map>

#include <cstdio>

#include <cstring>

using std::map;

typedef long long ll;

const ll N = 1e4 + 10, Q = 5e3 + 10;

ll n, q, s[N], f[N], cnt;

map <ll, ll> m;

ll find (ll x) {

	if(f[x] == -1) return x;

	ll tmp = find(f[x]);

	s[x] ^= s[f[x]];

	return f[x] = tmp;

}

ll insert (ll x) {

	if (m.find(x) == m.end()) m[x] = ++cnt;

	return m[x];

}

int main() {

	while (scanf ("%lld%lld", &n, &q) != EOF) {

		char str[4];

		memset(f, -1, sizeof f);

		memset(s, 0, sizeof s);

		ll ans = q;

		for (register ll i = 1, u, v; i <= q; ++i) {

			scanf ("%lld%lld%s", &u, &v, str);

			if (ans < q) continue;

			u = insert(u - 1), v = insert(v);

			ll fu = find(u), fv = find(v);

			ll t = 0;

			if (str[0] == 'o') ++t;

			if (fu == fv) {  //root相等

				if (s[u] ^ s[v] != t)

					ans = i - 1;

			} else { //一定有fu<fv(编号比较)

				f[fv] = fu;

				s[fv] = s[u] ^ s[v] ^ t;

                //矢量的异或运算

			}

		}

		printf ("%lld\n", ans);

	}

	return 0;

}

巴特西

Poj1733 Parity Game（带权并查集）

题面

题解

最新文章

热门文章