P9874

Sampson_YW · 2023-12-11 10:00:14 · 题解

对于一条限制，如果出现了 O，那么就表示这个位置上必须填某个字符。如果出现了 -，那么就可以知道某个字符至少出现了几次，记为 L_i。如果出现了 x，那么就可以知道某个字符恰好出现了几次，记为 R_i。并且如果某个位置是 - 或 x，那么就表示这个位置上不能填某个字符。

如果有 L_i>R_i 或者 \sum L_i>k，那么无解。否则 \sum L_i\leq k，可以将这些字符状压成一个长度为 \sum L_i 的二进制位，代表填没填过。每次转移就枚举一个字符，判断一下这个字符能不能填到这个位置上，并且填上之后有是不是仍然满足出现次数的限制，如果两个条件都满足就可以转移。

转移分为：填出现次数小于 L_i 的字符，填出现次数大于等于 L_i 的字符两种。前一种每次转移的枚举次数是 O(k) 的，后一种每次转移的枚举次数是 O(|\Sigma|) 的。

所以直接暴力转移的复杂度是 O\left((|\Sigma|+k)k2^k\right) 的，我没跑过去。对于第二种转移预处理：只考虑出现次数的限制时，能填的字符是哪些。复杂度 O(k^22^k)。

code