[Luogu 2024] 食物链
几句随感
我依稀记得联赛前本来想做这题的时候。
当年啊弱到题目与标签就令我望而生畏。
还有翻阅很多遍那现在已经被遗弃的博客。
看到题解中「三倍数组」的字眼就怕难而放弃。
如今我来了，晚了太多。
只可惜，总有的步伐是我留不住的。
也许我会说「其实你的写法可以更简单」。
也许我会说「判断条件可以不用那么多的」。
也许我会说「那句 continue 完全可以删除」。
也许，「不是你想 A 就能 A 的」。
也许，「可是该退还是要退的」。
……
题解
以后并查集杜绝 Merge，一律 Union。
建立补集。并查集分三段，每段长为 n，分别表示 A B C。说白了就是 f 数组开三倍，\([1,n],[n+1,2n],[2n+1,3n]\) 分别表示 A B C。
越界肯定是假的，跳过。
如果 x,y 同类，但这俩已经有捕食关系，这句话就是假的。
如果 x 吃 y，但这俩已经是同类或者 y 已经吃 x，这句话就是假的。
否则，这句话就是真的，那么执行下列操作。
x,y 是同类，分别在 A B C 段内 Union(x,y)。
x 吃 y，A->y 连 B->x，B->y 连 C->x，C->y 连 A->x。（当然 x 吃 y 写成 x 连 y 也是可以的，但鉴于本人刚学了生态系统的能量流动，就按生物的标准写了qwq）
最后输出假话数目就好了。
#include <cstdio>
const int MAXN=50010;
int n,k,ans;
class UFS
{
private:
int f[MAXN*3];
int Find(int x)
{
return x==f[x] ? x : f[x]=Find(f[x]);
}
void Union(int x,int y)
{
f[Find(y)]=Find(x);
}
public:
UFS(int n)
{
for(int i=1;i<=n*3;++i)
f[i]=i;
}
void UnionSame(int x,int y)
{
Union(x,y);
Union(x+n,y+n);
Union(x+(n<<1),y+(n<<1));
}
void UnionEat(int x,int y)
{
Union(x+n,y);
Union(x+(n<<1),y+n);
Union(x,y+(n<<1));
}
bool Connected(int x,int y)
{
return Find(x)==Find(y);
}
};
int main(int argc,char** argv)
{
scanf("%d %d",&n,&k);
static UFS *S=new UFS(n);
for(int i=1,opt,x,y;i<=k;++i)
{
scanf("%d %d %d",&opt,&x,&y);
if(x>n || y>n)
{
++ans;
continue;
}
if(opt==1)
if(S->Connected(x,y+n) || S->Connected(x+n,y))
++ans;
else
S->UnionSame(x,y);
else
if(S->Connected(x,y) || S->Connected(x,y+n))
++ans;
else
S->UnionEat(x,y);
}
printf("%d\n",ans);
delete S;
return 0;
}
谢谢阅读。
