P2024 题解

ikunTLE · 2025-01-14 20:53:09 · 题解

题目传送门

省流

一句话概括：在带权并查集模板的基础上多做了个对权值取模 3 的操作。

思路

首先考虑怎么样的动物是一类。如图是一条食物链，如 1\to2 代表 2 吃 1，那么不难想到每 3 个动物都是同一种动物。那么在图中，1 和 4 是同一种动物。

然后可以想到将边权全部赋值为 1，这样 1\to4 的边权和即为 3，则 1 和 4 是同一种生物。也可以将其看为取模运算，即设 A\to B 路径长度为 L，则若 L\bmod3=0，则满足 A 和 B 为同一种生物。同时也可以推断出，若 L\bmod3=1，则 B 吃 A；若 L\bmod3=2，则 A 吃 B。

然而这道题并不能用图直接进行存储，因为图不相连且输入信息会有假话。考虑使用并查集，主要难点在于查找与合并上（用 D_i 表示编号为 i 的动物与其父亲节点的关系）：

• 初始化：并查集照常，D_i 都初始化为 0，代表自己和自己是同一种动物。
• 查找：在原先的基础上要更新点 x 的权值。则令 y 为 x 的父亲，更新 D_x=(D_x+D_y)\bmod3。即从 x 点到 y 点需要将 y 的权转移到 x 点上。
• 合并：合并注意到有是同类和吃的两种关系，则需要定义传参 w 代表这种关系，可以用 0 代表同类，1 代表吃。想要将 x 拼接到 y 上，需要更新 x 的权值。令 z 为 x 的父亲，则更新 D_z=(D_y-D_x+w+3)\bmod3。其中 +3 是为了防止出现负数。

来到主函数的处理。

• 首先处理 X 或 Y 比 N 大的情况，因为若成立，这一定是一句假话。
• 然后判断若 X 和 Y 的父亲不同，按着参数 w 合并 X 和 Y。
• 只剩下 X 和 Y 的父亲相同的情况，此时若仍存在 D_X\ne D_Y 且 X 和 Y 为同类的说法，或它们不能互相吃（D_X\ne(D_Y+1)\bmod3）两者是吃的关系，这也是一句假话。
• 剩下的情况相当于说了句废话。

最后输出假话的次数即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e4+10;
int fa[N],d[N];
void _init(){
    for(int i=0;i<N;++i)
        fa[i]=i;
    return;
}
int _find(int x){
    if(x!=fa[x]){
        int temp=fa[x];
        fa[x]=_find(fa[x]);
        d[x]=(d[x]+d[temp])%3;
    }
    return fa[x];
}
void _merge(int x,int y,int w){
    int xx=_find(x),yy=_find(y);
    if(xx!=yy){
        fa[xx]=yy;
        d[xx]=(w+d[y]-d[x]+3)%3;
    }
    return;
}
int main(){
    _init();
    int n=read(),k=read(),cnt=0;
    while(k--){
        int op=read(),x=read(),y=read();
        int xx=_find(x),yy=_find(y);
        if(x>n||y>n||op==2&&x==y)
            ++cnt;
        else if(xx!=yy)
            _merge(x,y,op-1);
        else if(op==1&&d[x]!=d[y]||op==2&&d[x]!=(d[y]+1)%3)
            ++cnt;
    }
    printf("%d\n",cnt);
    return 0;
}