CF1697F 题解

题意

传送门

构造一个长度为 \(n\) 的数列 \(a\)，满足 \(1\le a_i\le k\) 且 \(a\) 不降，以及 \(m\) 个约束，有三种情况：

• 1 i x，表示 \(a_i\ne x\)

• 2 i j x，表示 \(a_i+a_j\le x\)

• 3 i j x，表示 \(a_i+a_j\ge x\)

无解输出 \(-1\)。\(1\le n,m\le2\times10^4,2\le k\le 10\)。

题解

学到了 2-sat 的一种新用法，可以用来解决此类求值问题。

对每个 \(a_i\)，设 \(k\) 个 bool 变量，其中 \(b_{i,j}\) 表示 \(a_i\) 是否 \(\le j\)。于是所有条件都容易满足。复杂度 \(O((n+m)k)\)。

需要注意的是，此类问题不能设 \(b_{i,j}\) 表示 \(a_i\) 是否 \(=j\)。因为 2-sat 的要求是所有约束同时成立，故无法表示不等式。

另外，将一个非 bool 变量拆成若干个 bool 变量，一定要注意它们之间的联系，充分思考后得出等价刻画，否则极易遗漏。