P9869 [NOIP2023] 三值逻辑 题解

· · 题解

本题解只用到了 BFS。

首先想到拆点，如果点 x 修改了 k_x 次就拆成 k_x+1 个点。

对于操作一直接对 x 建一个新版本，暴力赋值即可；对于操作二、三则相当于对于 x 建一个新版本，和 y 得最新版本连边权为 1 或 0 得边，表示两点之间是相等还是相反。注意到这些边都是无向边，且确定一个端点另一个端点随之确定。

特别的，由于操作始末状态相同，需要把每个点始末版本连一条代表相等得边。

然后发现每个连通块只有三种状态，且相互独立。于是直接暴力 bfs 即可。

特别注意第二种操作 x=y 的情况。

时间复杂度 O(n)。link