[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;

}

谢谢阅读。

巴特西

[Luogu 2024] 食物链

[Luogu 2024] 食物链

几句随感

题解

最新文章

热门文章