題意
思路
- 我們假設已經了有了 s 串的前綴和 sum [], 那么對于一次詢問：
- 第一種型別：x y even 表示 sum [y] - sum [x] == 偶數， 那么可以推測出：sum [y] 與 sum [x] 的奇偶性
相同， - 第二種型別：x y odd 表示 sum [y] - sum [x] == 奇數， 那么可以推測出：sum [y] 與 sum [x] 的奇偶性
不同，
- 第一種型別：x y even 表示 sum [y] - sum [x] == 偶數， 那么可以推測出：sum [y] 與 sum [x] 的奇偶性
- 帶權并查集解法
- 如果我們這題要使用帶權并查集的話，我們考慮兩個數 u 與 v 的奇偶性情況：
- 奇偶性相同：那么那么就相當于 u 與 v 之間的距離為 0， 在合并的時候我我們可以根據這個按照實際意義推出合并的運算式，
- 奇偶性不同：那么那么就相當于 u 與 v 之間的距離為 1，在合并的時候我們也可以推測出 d (fu) 的值
帶值并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m;
unordered_map<int, int> mp;
int f[N], d[N];
int get(int x)
{
if (mp.count(x) == 0) mp[x] = ++ n;
return mp[x];
}
int find(int x)
{
if (f[x] != x)
{
int root = find(f[x]);
d[x] += d[f[x]];
f[x] = root;
}
return f[x];
}
int main()
{
scanf("%d %d", &n, &m);
n = 0;
for (int i = 1; i < N; i ++) f[i] = i;
int res = m;
int x, y; char type[10];
for (int i = 1; i <= m; i ++) {
scanf("%d %d %s", &x, &y, type);
x = get(x - 1), y = get(y);
int fx = find(x), fy = find(y);
int t = 0;
if (type[0] == 'o') t = 1;
if (fx == fy)
{
if (((d[x] + d[y]) % 2 + 2) % 2 != t)
{
res = i - 1;
break;
}
}
else
{
f[fx] = fy;
d[fx] = d[x] ^ d[y] ^ t;
}
}
printf("%d\n", res);
return 0;
}
種類并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int n, m;
int f[N];
unordered_map<int, int> mp;
int get(int x)
{
if (mp.count(x) == 0) mp[x] = ++ n;
return mp[x];
}
int find(int x)
{
if (f[x] != x) f[x] = find(f[x]);
return f[x]; //這里必須回傳 f[x] , 對于這種遞回方式
}
int main()
{
scanf("%d %d", &n, &m);
n = 0;
for (int i = 1; i < N; i ++) f[i] = i;
int x, y; char type[10];
int res = m;
for (int i = 1; i <= m; i ++) {
scanf("%d %d %s", &x, &y, type);
x = get(x - 1), y = get(y);
if (type[0] == 'e')
{
if (find(x + N / 2) == find(y))
{
res = i - 1;
break;
}
f[find(x)] = find(y);
f[find(x + N / 2)] = find(y + N / 2);
}
else
{
if (find(x) == find(y))
{
res = i - 1;
break;
}
f[find(x)] = find(y + N / 2);
f[find(y)] = find(x + N / 2);
}
}
printf("%d\n", res);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/349738.html
標籤：其他