P3825 题解

KSCD_ · 2025-08-31 17:17:22 · 题解

题意

要求构造一个长为 n 的字符串，只包含 A,B,C，其中有至多 d 个位置随便填，剩余位置只能填其中两种字符。还有 m 条限制形如 i,h_i,j,h_j，表示 i 处填 h_i 时 j 处必填 h_j，构造方案或判断无解。n\le 5\times 10^4,d\le 8,m\le 10^5。

题解

先考虑 d=0 的情况，则此时每一位上只有两种选择，可以直接建出 2-SAT 求解。此时若 i 不能填 h_i，则不用考虑该限制；若 j 不能填 h_j，则 i 不能填 h_i，需要特判。其余情况跟 01 的 2-SAT 类似，复杂度 O(n+m)。

若 d\ne 0，变成了难以解决的 3-SAT 问题。然而 d 非常小，考虑将其转化为 d=0 的情况求解。最暴力的方式是直接枚举这些位置填什么，复杂度 O(3^d(n+m))，无法通过，但有不少分。

注意到 d=0 时每个位置都是不能填某值，因此可以转化成这样的限制求解。考虑枚举哪些位置填 A，并钦定其余位置不能填 A，直接求解即可，复杂度 O(2^d(n+m))，可以通过。

再注意到这样事实上浪费了很多状态，因为最终答案在每一位上只有一种取值，只要枚举到另外两种之一即可。考虑把相邻两个位置放在一起，此时必然存在一种两者均不取的字符，枚举这个字符是啥即可，复杂度 O({\sqrt 3}^ d(n+m))，比较优秀。

再注意到 d 太小了，以至于 \lfloor\frac d3\rfloor \le 2，因此可以直接枚举个数最少的字符以及它们的位置，复杂度 O(d^{\lfloor\frac d3\rfloor}(n+m))，表现和上一种差不多。

还可以随机化。由于若枚举不能填的值，对于一种选择方案，每个位置有两种正确的枚举方式，随机填的正确率为 (\frac 23)^d，若答案不唯一概率会更高。因此若随机操作 (\frac 32)^d 次，错误率即可降到 \frac 1e 以下，本题做 2(\frac 32)^d 次即可通过，复杂度 O((\frac 23)^d(n+m))，跑得最快。