3 条题解
-
2
首先我们来分析一下题目:有n个物品,每个物品有三种状态(编号为u的物品的三种状态分别为 u,u+n,u+2n),现在有 m 次操作,每次操作要么将两个状态所在的集合合并,要么判断两个状态是否在同一个集合中。如果操作中出现了编号超过 n的状态,则该操作无效。求最后有多少次操作是无效的。
根据题意,我们可以发现这道题就是要用并查集来维护每个物品不同状态之间的关系,每个物品的三种状态都是不同的节点,我们只需要将它们看成三个节点即可。
对于合并操作,我们只需要将两个集合合并,并且把它们对应的另外两个状态也合并起来即可,代码如下:
fa[find(u)] = find(v); fa[find(u + n)] = find(v + n); fa[find(u + n + n)] = find(v + n + n);
对于判断操作,我们只需要检查两个状态所在的集合是否相等,代码如下:
if (find(u) == find(v) || find(u) == find(v + n)) { ans++; }
但是需要特别注意的是,如果在输入操作的时候出现了编号超过 n的状态,则该操作无效,直接跳过即可。
最后需要注意的是,要按照“路径压缩+按秩合并”的方式来实现并查集,否则会超时。具体实现可以参考代码注释。
完整代码:
#include <cstdio> // 快速读入函数 inline int read() { char c = getchar(); int n = 0; while (c < '0' || c > '9') { c = getchar(); } while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); } return n; } const int maxN = 100005; int n, m, ans, fa[maxN * 3]; // 并查集查找操作 int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); } int main() { n = read(), m = read(); for (int i = 1; i <= n * 3; i++) { fa[i] = i; } // 初始化并查集 for (; m; m--) { int opt = read(), u = read(), v = read(); if (u > n || v > n) { ans++; continue; } // 如果 u 或 v 超过了 n 的范围,则直接跳过 if (opt == 1) { // 第一种操作 if (find(u + n) == find(v) || find(u) == find(v + n)) { ans++; } // 如果 u+2n 和 v 在同一个集合中,或者 u 和 v+n 在同一个集合中,则不合法,答案加1 else { // 否则将 u 的三个节点所在的集合与 v 的三个节点所在的集合合并 fa[find(u)] = find(v); fa[find(u + n)] = find(v + n); fa[find(u + n + n)] = find(v + n + n); } } else { // 第二种操作,与第一种操作类似 if (find(u) == find(v) || find(u) == find(v + n)) { ans++; } else { fa[find(u + n)] = find(v); fa[find(u + n + n)] = find(v + n); fa[find(u)] = find(v + n + n); } } } printf("%d\n", ans); // 输出答案 return 0; }
-
0
#include<bits/stdc++.h> using namespace std; const int N=50005; int n,m,k,s,t,fa[N],d[N],ans,x,y,p,q; int getfa(int x){ if (fa[x]==x) return x; int p=getfa(fa[x]); d[x]=(d[x]+d[fa[x]])%3; return fa[x]=p; } int main() { cin>>n>>m; for (int i=1;i<=n;++i) fa[i]=i; for (int i=1;i<=m;++i){ cin>>k>>x>>y; if (x>n || y>n) { ++ans; continue; } p=getfa(x); q=getfa(y); if (k==1){ if (p==q) { if (d[x]!=d[y]) ++ans; } else { fa[p]=q; d[p]=(d[y]-d[x]+3)%3; } } if (k==2){ if (p==q){ if (d[x]!=(1+d[y])%3) ++ans; } else { fa[p]=q; d[p]=(d[y]-d[x]+1+3)%3; } } } cout<<ans<<endl; }
-
0
int main() { n = read(), m = read(); for (int i = 1; i <= n * 3; i++) { fa[i] = i; } for (; m; m--) { int opt = read(), u = read(), v = read(); if (u > n || v > n) { ans++; continue; } if (opt == 1) { if (find(u + n) == find(v) || find(u) == find(v + n)) { ans++; } else { fa[find(u)] = find(v); fa[find(u + n)] = find(v + n); fa[find(u + n + n)] = find(v + n + n); } } else { if (find(u) == find(v) || find(u) == find(v + n)) { ans++; } else { fa[find(u + n)] = find(v); fa[find(u + n + n)] = find(v + n); fa[find(u)] = find(v + n + n); } } }
- 1
信息
- ID
- 218
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 58
- 已通过
- 29
- 上传者