浅谈 [NOIP 2023]三值逻辑 无限种解法

前言

对于 NOIP 2023，T1 是个人人都会写的签到题，对于 T3 则是做法唯一只能按照提醒的数据范围一步一步走，对于 T4 则是只能线段树优化 dp。思维局限性大，并没有什么深度挖掘的意义。直到有一天睡觉的时候又想起来 T2 这个题，觉得有必要把这个题相关的所有方法记录下来。故于此记录。

法一：并查集

考虑对于前 20 pts 的解法，理论可以直接枚举所有可能，但是由于可以特判出一些显然错误的方案，所以枚举的方案数是不全的。理论复杂度 \(O(3^n)\) ，而实际远远到不了这个复杂度。

对于中间只有赋值操作的 20 pts，直接并查集维护即可。

考虑正解，显然是有办法对于并查集解法进行优化的。我们要最小化不确定值的个数，那么首先要知道如何判定谁可以是不确定的数。对于任意一个数 \(x\) ，如果 \(x\) 的祖先是 \(-x\)。或者 \(x\) 的祖先是 \(U\)。直接并查集维护，但是期间有一些细节。对于取相反数，会出现 \(fa[-x]\) 导致下标错误，所以要分类讨论 。当然，我们在模拟样例的时候发现，会出现反复取反的情况，即 \(x\) -> \(-x\) -> \(x\)，这样在执行并查集的时候会陷入死循环，所以再开一个 \(v\) 来记录是否到达过 \(x\) 的 \(-x\)。当然，对于数组 \(v\) 也会出现下标为 \(<0\) 的情况，所以下标统一上移 \(n\) 。剩下的直接代码实现即可。

submission

法二：二分图

这个题好玩的地方在于，很多种 trick 都可以对这个题使用。

化繁为简，考虑将 \(T,F,U\) 赋值操作也更改为下面那些类型的操作，\(T\) 更改为 \(x_{n+1}\)，\(F\) 更改为 \(-x_{n+1}\)，\(U\) 更改为 \(x_{n+2}\)

建立 \(01\) 无向图，当涉及取反操作时那么边权为 \(1\)

对于样例，我们发现，如果只有 \(T,F\) 那么结果一定是 \(Unknown\)。所以，如果图上出现了一个环其边权为一的边有奇数条，所以我们现在的任务就是判定是否存在这样的话，即判二分图。如果不是二分图，那么整个联通块都是 \(U\)，单独统计 \(x_{n+2}\)，更新答案

submission

法三：拆点 BFS

把所有的赋值操作改为拆点。每操作一次多拆一个点。

• 操作一：对 \(x\) 建一个新版本赋值，直接实现
• 操作二、三：对于 \(x\) 建一个新版本，和 \(y\) 得最新版本连边权为 \(1\) 或 \(0\) 的无向边，当涉及取反操作时那么边权为 \(1\)

考虑初始情况和末尾情况，操作始末状态相同，需要把每个点始末版本连一条代表相等得边。然后发现每个连通块只有三种状态，且相互独立。可以 BFS 直接计算。

法四：基环树

我们仍然借鉴第二个方法找环的思路，但是并不是使用二分图。

对于我们最后得到结果，只要不是定值就一定可以写成 \(k \times a_i\)，\(k∈[-1,1]\)。我们原来建立的是 \(01\) 无向图，而我们现在建立的就是一个有边权的无向图了。对于 \(a_i\) 为 \(k \times a_j\) 形式，连接 \(i,j\) 边权为 \(k\)。这样就建出了基环树。如果对于一个点其值已知就可以便利图求联通块。

然后，考虑找环。我们再回到解法一所说，如果有 \(x\) 的祖先为 \(-x\) 的情况，就会出现 \(Unknown\)，那么我们就能得出结论，如果我们这个环的边权乘积为 \(-1\)，即化简后出现了 \(a_x \times -a_y\) 的情况，则整个联通块都是 \(U\)

法五：2-SAT

大炮打苍蝇

2-SAT 可以用来解决有 \(n\) 对二元矛盾组所构成的集合从中任意找一个元素 \(x\) 从而找到与其不矛盾的。

思路非常符合本题，因为本题全是二元组。并且取反操作前边都能 \(01\) 边权了，这里自然也可以定义矛盾。

设 \(1\)~\(n+m\) 的点表示为 \(T\) 的点，其中 \(x_{k+n}(1≤k≤n)\) 表示在第 \(k\) 次操作被操作的变量的值（操作后）。设 \(n+m+1\)~\(2 * (n+m)\) 表示 \(x_1,...x_{n+m}\) 为 \(F\) 的点。

如果给 \(x_i\) 为 \(U\)， \(i\) 和 \(i + n + m\) 连双向边。\(x_i\) 为 \(T\)， \(i + n + m\) 向 \(i\) 连单向边。 \(x_i\) 为 \(F\)， \(i\) 向 \(i + n + m\) 连单向边。 \(x_i\) 赋值为 \(x_j\)， \(j\) 决定了 \(i\)，\(i\) 也可以倒推出 \(j\)，\(cur_j\) 和 \(i\) 连双向边，\(cur_j + n + m\) 和 \(i + n + m\) 连双向边。如果是 \(x_i\) 赋值为 \(¬x_j\)， \(j\) 决定了 \(i\)，\(i\) 也可以倒推出 \(j\)，\(cur_j + n + m\) 和 \(i\) 连双向边，\(cur_j\) 和 \(i + n + m\) 连双向边。

\(cur_i\) 为当前操作最后一次更新 \(i\) 的操作编号加 \(n\)，若没有则为 \(i\)。

之后 SCC 跑 Tarjan 缩点就好，\(scc_{res_i} = scc_{res_i + n + m}\) 数量即为答案。

submisionn