我们定义:对于任意一个 $i$:
- $i$ 表示其本身。
- $n + i$ 表示 $i$ 的天敌。
- $2n + i$ 表示 $i$ 的猎物。
(您可能不知道定义是最难想的)
题目中对于假话的定义是:
- 当前的话与前面的某些真的话冲突,就是假话;
- 当前的话中 X 或 Y 比 N 大,就是假话;
- 当前的话表示 X 吃 X,就是假话。
其中,第 $2$、$3$ 条容易判断(直接特判),那第 $1$ 条呢?
首先声明一下,只有真话才会被录入信息。
- 如果 $x$ 和 $y$ 是同类,若 $x$ 是 $y$ 的天敌或猎物,那么是假话。
- 如果 $x$ 吃 $y$,若 $x$ 和 $y$ 是同类,那么是假话。
- 如果 $x$ 吃 $y$,若 $x$ 是 $y$ 的猎物,那么是假话。
- 如果 $x$ 吃 $y$,若 $y$ 是 $x$ 的天敌,那么是假话。
关于 $i$ 的天敌和猎物,我们已经有所定义。
所以,到这里,应该很容易看出来是并查集。
看出来是并查集,就很容易做了。
若您不会并查集,请移步至 AcWing 836. 合并集合。
最后注意:合并时也有些讲究。(自己想想啊呀,待会看代码)
Code:
#include <iostream>
#include <cstdio>
using namespace std;
int n, k, ans = 0;
int fa[150010]; //注意数组开 3 倍。
int find (int x) {
if(fa[x] != x) return fa[x] = find(fa[x]);
return fa[x];
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= 3 * n; i ++ )
fa[i] = i; //基本初始化。
while (k -- ) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(x > n || y > n) { ans ++; continue; }
if(op == 1) {
if(find(x) == find(y + n)) {
ans ++;
continue;
}
if(find(x) == find(y + 2 * n)) {
ans ++;
continue;
}
fa[find(y)] = find(x);
fa[find(y + n)] = find(x + n);
fa[find(y + 2 * n)] = find(x + 2 * n);
}
if(op == 2) {
if(x == y) { ans ++; continue; }
if(find(x) == find(y)) { ans ++; continue; }
if(find(x) == find(y + 2 * n)) {
ans ++;
continue;
}
fa[find(x)] = find(y + n);
fa[find(y)] = find(x + 2 * n);
fa[find(x + n)] = find(y + 2 * n);
}
}
printf("%d", ans);
return 0;
}
若您觉得有帮助,就点个赞吧。
更多精彩请关注我的博客号~
祝各位 rp++ !
支持
扩展域太强了
这个思路很棒
这思路虽然不好想,但是真的厉害👍
请问 fa[find(x + n)] = find(y + 2 * n)
这一句是什么意思呢?
这上面的赋值语句 可以同意都前者为以x为中心,后者以y为中心
例
以及
不得不说大佬思路真的一绝
这样定义太妙了,楼主太牛啦
谢谢支持!
为什么不解释一下定义呢??
???解释了呀?您哪里不懂呀?
您好,就是我想请问一下,为什么是这么定义的,n+i为什么就是天敌了。
您可能没有理解我的意思。 $n + i$ 是天敌只是我们自己假设定义的,您也可以定义 $2n + i$ 是天敌或者其他的。
如果您定义 $2n + i$ 是天敌,$n + i$ 是猎物,那判断和合并可能就要变一下,但是思路依然不变。
为了更方便的使用并查集,来判断真假话。
嗷嗷~
orz
″
%%
厉害厉害
这是应该是扩展域并查集吧我记得。。。。
%%%
赞了hh