比赛地址弱校连萌寒假专题二
题解前继2015弱校连萌寒假专题二(并查集) 题解(A-H)
I. True Liars
题意：
有一些人，其中p1个人说真话，剩下p2个人说假话，现在有n句话，每句话是一个人说某一个人是否是说真话的人，请你判断是否能唯一判断哪些人说真话、哪些人说假话，升序输出说真话人的编号。
n <= 1000, p1, p2 <= 300。
题解：
一个说真话的人a，如果说b是说真话的，那么b是说真话的，否则b是说假话的；一个说假话的人a，如果说b是说真话的，那么b是说假话的，否则b是说真话的。
说真话的人只会说说真话的人会说真话，说假话的人只会说说假话的人说真话，根据这个可以确定一些人的真假关系，但是不能确定某个人是否是说真话的人。
用带权并查集表示的话，说真话的人和说假话的人是一个二元环，实际上可能会存在多个互不干扰的二元环。
如果能算出每个连通分量里两类人的数量，则可以通过dp来决策每个分量里人员的分配，可以计算出有p1个说真话的人的方案是否唯一，若唯一，按照状态转移的顺序依次标记说真话的人即可。dp的形式类似于分组背包，注意每一个分量都必须标人。
不用带权并查集也可使用二倍并查集，但是要注意dp所需要的size的计算，因为二倍并查集添加了虚结点n + i表示与i关系互异的人。
时间复杂度O(nα(p1+p2)+p1(p1+p2))。
代码：
#include <cstdio>#include <cstring>const int maxp = 601;int n, p1, p2, fa[maxp], dist[maxp], cnt[maxp][2], f[maxp][maxp], pre[maxp][maxp];bool vis[maxp][2];int find(int x){if(x == fa[x])return x;int tmp = fa[x];fa[x] = find(fa[x]);dist[x] ^= dist[tmp];return fa[x];}int main(){while(scanf("%d%d%d", &n, &p1, &p2) == 3 && n + p1 + p2){memset(f, 0, sizeof f);memset(vis, 0, sizeof vis);memset(pre, 0, sizeof pre);memset(cnt, 0, sizeof cnt);memset(dist, 0, sizeof dist);for(int i = 1; i <= p1 + p2; ++i)fa[i] = i;while(n–){int x, y, u, v;char op[5];scanf("%d%d%s", &x, &y, op);if((u = find(x)) != (v = find(y))){fa[u] = v;dist[u] = dist[x] ^ dist[y] ^ (op[0] == 'n');}}for(int i = 1; i <= p1 + p2; ++i){int j = find(i);++cnt[j][dist[i]];}f[0][0] = 1;for(int i = 1; i <= p1 + p2; ++i)if(!cnt[i][0] && !cnt[i][1])for(int j = 0; j <= p1; ++j){f[i][j] = f[i – 1][j];pre[i][j] = pre[i – 1][j];}elsefor(int j = 0; j <= p1; ++j)//·ÇºÃ¼´»µ{if(j >= cnt[i][0] && f[i – 1][j – cnt[i][0]]){f[i][j] += f[i – 1][j – cnt[i][0]];pre[i][j] = i + i;}if(j >= cnt[i][1] && f[i – 1][j – cnt[i][1]]){f[i][j] += f[i – 1][j – cnt[i][1]];pre[i][j] = i + i + 1;}}if(f[p1 + p2][p1] != 1){puts("no");continue;}for(int i = p1 + p2, j = p1; i > 0 && j > 0; –i){int ii = pre[i][j] >> 1, jj = pre[i][j] & 1;if(!ii && !jj)break;vis[ii][jj] = 1;i = ii;j -= cnt[ii][jj];}for(int i = 1; i <= p1 + p2; ++i)if(vis[find(i)][dist[i]])printf("%d\n", i);puts("end");}return 0;}
J. 共和国的隔离
题意：
有n个点，m条边，现在有t次操作，每次操作破坏编号为i的边或者询问x和y点的连通性。
n, m, t <= 10 ^ 5。
题解：
题目并没有要求在线解决，可以倒着处理操作，则破坏操作可以认为是添加操作，利用并查集维护连通性即可，注意边被多次破坏的情况应该转化为选择最早的一次操作添加。
时间复杂度O((m+t)α(n))。
代码：
#include <cstdio>const int maxn = 1e5 + 1, maxm = 1e5 + 1, maxt = 1e5 + 1;int n, m, t, fa[maxn], u[maxm], v[maxm], query[maxt][3], ans[maxt];bool vis[maxm];int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i)scanf("%d%d", u + i, v + i);scanf("%d", &t);for(int i = 1; i <= t; ++i){int x, y;char op[2];scanf("%s", op);if(op[0] == 'Q'){scanf("%d%d", &x, &y);query[i][0] = 1;query[i][1] = x;query[i][2] = y;}else{scanf("%d", &x);if(vis[x])query[i][0] = 2;else{query[i][1] = x;vis[x] = 1;}}}for(int i = 1; i <= n; ++i)fa[i] = i;for(int i = 1; i <= m; ++i)if(!vis[i])fa[find(u[i])] = find(v[i]);for(int i = t; i > 0; –i)if(query[i][0] == 1)ans[i] = find(query[i][1]) == find(query[i][2]);else if(!query[i][0])fa[find(u[query[i][1]])] = find(v[query[i][1]]);for(int i = 1; i <= t; ++i)if(query[i][0] == 1)printf("%d\n", ans[i]);return 0;}
K. Parity
题意：
有一个元素未知的长度为n的01序列，现在有k句话，每句话说明序列的第l位到第r位元素之和的奇偶性，问从第几句话开始出现矛盾。
n <= 10 ^ 9, k <= 5000。
题解：
sum[l, r] = sum[1, r] – sum[1, l – 1]，序列的第l位到第r位元素之和sum[l, r]为奇，表示前缀和[1, l – 1]和前缀和[1, r]的奇偶性不同，否则奇偶性相同。
则可以用带权并查集维护前缀区间的相对奇偶性，也可以开二倍并查集，不过此题n过大，但最终发生改变的前缀区间最多只有2k个，离散化一下即可。
时间复杂度O(kα(k))。
也有伤心的，既有令人兴奋的，也有令人灰心的，
