P2024 [NOI2001] 食物链 总结

q0y1 · 2023-09-26 09:13:01 · 个人记录

P2024 [NOI2001] 食物链

思路

我们设 c[x] 为动物 x 相对于它的父亲 fa[x] 的种类名称，然而种类有三种，我们分别定义为：0, 1, 2，由于每个动物的种类名称是没有限制的，所以我们只要当作标签即可，为保证关系与关系之间有传递性，所以我们定义：如果 y 吃 x 那么 c[x] = (c[y] + 1) \mod 3 这样就可以表示一个数吃另一个数，题目说 x 和 y 是同类，或 x 吃 y 其实本质就是 x 和 y 有一种关系，说白了就是两个点中间的一条边，也就是 x 属于的集合与 y 属于的集合的关系，然后每个集合内部又有许多关系，所以说如果 x 和 y 在一个集合，说明如果我知道 x 或 y 的任意一个种类名称，我就可以知道另一个的种类名称了，于是便可用并查集来维护集合，那集合内部的关系怎么维护呢？

其实就是上面所说的：如果 y 吃 x 那么 c[x] = (c[y] + 1) \mod 3 也就是说如果父亲 x 吃 y 那么这条关系便是 1，如果父亲 x 被 y 吃那么这条关系便是 -1，如果为同类，便是 0，所以如果要判断假话，就判断 c[x] 与 c[y] 之间关系是否正确即可，可是对于 x、y 之前本就没有关系的呢？

我们就需要建立关系，可是我们如果改一次，就从头更新到脚趾尖，那么显然超时，所以我们充分发扬人类智慧，将线段树里的 lazy\_tag 弄过来，不过我们发现每次在询问的时候都会更新一次，所以不用想线段树一样弄两个数组，直接用 c 来维护即可，可怎么维护呢？

直接加上关系即可，因为反正是要加上的，然后要用路径压缩，由于 c 存储是一个相对值，所以在路径压缩时需要把从当前点到根的路径上的相对值都加上，说白了就是先处理 fa[x] 然后直接加上 c[fa[x]] 即可，因为 c[fa[x]] 已经把前面的都加上了。

最后考虑如何合并，我们知道两个集合的合并，其实是两个集合的根的合并，但是 c 的维护就会出问题，因为要实现的是给定的两个点合并，那么我们可以得出一个图来（x 吃 y 或者 x 和 y 是同类）： 然后根据上面的定义，我们可以得出（接下来的运算都要取模）：

那么可以的到关系式：

即：

这个时候就可得到两集合合并时的 lazy\_tag 修改值，实现了各个功能后，直接模拟即可。

code

#include <iostream>

using namespace std;

const int MaxN = 5e4 + 10;

int fa[MaxN], c[MaxN], n, k, ans;

int Ff(int x) {
  if (fa[x] < 0)
    return x;
  int root = Ff(fa[x]);
  c[x] = (c[x] + c[fa[x]]) % 3;
  return fa[x] = root;
}

void Merge(int x, int y, int f) {
  int fx = Ff(x), fy = Ff(y);
  c[fy] = (f - c[y] + c[x] + 6) % 3, fa[fy] = fx;
}

int main() {
  //freopen("tmp.in", "r", stdin);
  //freopen("tmp.out", "w", stdout);
  cin >> n >> k;
  fill(fa + 1, fa + n + 1, -1);
  for (int i = 1, op, x, y; i <= k; i++) {
    cin >> op >> x >> y;
    if (x > n || y > n) {
      ans++;
      continue;
    }
    if (op == 1) {
      if (Ff(x) != Ff(y)) {
        Merge(x, y, 0);
      } else if (c[x] != c[y]) {
        ans++;
      }
    } else {
      if (Ff(x) != Ff(y)) {
        Merge(x, y, 1);
      } else if ((c[y] - 1 + 3) % 3 != c[x]) {
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

总结

首先是要构造出种类规则，然后转换成 并查集 的语言，然后利用线段树的 lazy\_tag思想、以及前缀和思想来实现路径压缩，最后理解规则，构造式子，推出式子即可。