本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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))$，跑得最快。