Java教程

食物链

本文主要是介绍食物链,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

更好的阅读体验

我们定义:对于任意一个 \(i\):

  • \(i\) 表示其本身。
  • \(n + i\) 表示 \(i\) 的天敌。
  • \(2n + i\) 表示 \(i\) 的猎物。

(您可能不知道定义是最难想的)

题目中对于假话的定义是:

  1. 当前的话与前面的某些真的话冲突,就是假话;
  2. 当前的话中 X 或 Y 比 N 大,就是假话;
  3. 当前的话表示 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++ !

这篇关于食物链的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!