每日一题8.23
种类并查集的两道题目
第一个题P5937 [CEOI 1999] Parity Game - 洛谷
Alice 和 Bob 在玩一个游戏：他写一个由 0 和 1 组成的序列。Alice 选其中的一段（比如第 3 位到第 5 位），问他这段里面有奇数个 1 还是偶数个 1。Bob 回答你的问题，然后 Alice 继续问。Alice 要检查 Bob 的答案，指出在 Bob 的第几个回答一定有问题。有问题的意思就是存在一个 01 序列满足这个回答前的所有回答，而且不存在序列满足这个回答前的所有回答及这个回答。
输入格式
第 1 行一个整数 n，是这个 01 序列的长度。
第 2 行一个整数 m，是问题和答案的个数。
第 3 行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是 Bob 的回答。odd表示有奇数个 1，even 表示有偶数个 1。
输出格式
输出一行，一个数 x，表示存在一个 01 序列满足第 1 到第 x 个回答，但是不存在序列满足第 1 到第 x+1 个回答。如果所有回答都没问题，你就输出所有回答的个数。
输入输出样例
输入 #1复制
10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd
输出 #1复制
3
说明/提示
对于 100% 的数据，1≤n≤109，m≤5×103。
解决方案
根据前缀和可以分为两种并查集：a和b奇偶性相同和不同。分别分配到1~n和n+1~2n
比如x和y奇偶性相同的话就merge（x,y）,merge(x+n,y+n)表示x和y是同一种类（即同奇偶性）
不同的话就merge(x,y+n),merge(x+n,y);表示x和y不是同一种类；
不过这个题还要离散化一下，代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 40000 + 10;
int fa[N];
struct node
{int x, y;string z;
}a[N];//设置一个结构体a方便离散化
void init()
{for (int i = 1; i <= N; i++)fa[i] = i;
}
int find(int x)
{if (fa[x] == x)return x;return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{int fx = find(x), fy = find(y);if (fx!= fy)fa[fx] = fy;
}//并查集板子
inline void solve()
{int n,m;cin >> n >> m;if (!m){cout << 0 << endl;return;}init();vector<int>v;//储存着所有出现过的数然后离散化for (int i = 1; i <= m; i++){string z;int x, y;cin >> x >> y>> z;a[i] = {x-1, y, z};v.push_back(x-1);v.push_back(y);}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()));//去重离散化int len = v.size();//一个种类的大小for (int i = 1; i <= m; i++){int x =lower_bound(v.begin(), v.end(), a[i].x) - v.begin(),y = lower_bound(v.begin(), v.end(), a[i].y) - v.begin();//找到输入的x，y在v中对应的编号char c=a[i].z[0];if (c == 'e')//说明要x和y同一奇偶性{if (find(x) == find(y + len))//如果x和y不是同奇偶性的话，就说明这句话不可能实现{cout<<i-1<<endl;return;}merge(x, y);merge(x+len, y + len);//合并}else//同理{if (find(x) == find(y)){cout << i - 1 << endl;return;}merge(x, y + len);merge(x + len, y);}}cout << m << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin >> t;while (t--){solve();}
}第二个题：P2024 [NOI2001] 食物链 - 洛谷
题目描述
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1∼N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
- 第一种说法是
1 X Y，表示 X 和 Y 是同类。 - 第二种说法是
2 X Y，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X 或 Y 比 N 大，就是假话；
- 当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行两个整数，N,K，表示有 N 个动物，K 句话。
第二行开始每行一句话（按照题目要求，见样例）
输出格式
一行，一个整数，表示假话的总数。
输入输出样例
输入 #1复制
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
输出 #1复制
3
说明/提示
对于全部数据，1≤N≤5×104，1≤K≤105。
解决方案：
和第一个题类似也是一个种类并查集，但是这个题又三个种类，a，b，c，a吃b，b吃c，c吃a
a，b，c分别在1~n,n+1~2n,2n+1~3n;
所以要a和b是同一种类即
merge(x, y);
merge(x + n, y + n);
merge(x + 2 * n, y + 2 * n);要a吃b即
merge(x, y + n);
merge(x + n, y + 2 * n);
merge(x + 2 * n, y);#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 400000 + 10;
int fa[N];
void init(int x)
{for (int i = 1; i <= x; i++)fa[i] = i;
}
int find(int x)
{if (fa[x] == x)return x;return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{int fx = find(x), fy = find(y);if (fx != fy)fa[fx] = fy;
}//并查集板子
inline void solve()
{int n, m;cin >> n >> m;int op, x, y;init(3*n+100);vector<int> tab(3*n+100, 0);int res = 0;for (int i = 1; i <= m; i++){cin >> op >> x >> y;if (x > n || y > n){res++;continue;}if (op == 1){if (find(x) == find(y + n) || find(x) == find(y + 2 * n))//如果x吃y或者y吃x就说明x，y不可能是同一种类res++;else{merge(x, y);merge(x + n, y + n);merge(x + 2 * n, y + 2 * n);}}else{if (find(x) == find(y)||find(x)==find(y+2*n))//如果x和y是同一种类或者y吃x就不可能存在x吃yres++;else{merge(x, y + n);merge(x + n, y + 2 * n);merge(x + 2 * n, y);}}}cout << res << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin >> t;while (t--){solve();}
}