题解：AT_agc045_c [AGC045C] Range Set

happybob · 2025-11-04 17:46:02 · 题解

不错的性质观察题。

先考虑判定。将过程反过来。本质等价于，对于目前串 s，选择一个长度 \geq a 的不含 1 的段，将段内的字符都变为 \texttt{?}，或者选择一个长度 \geq b 的不含 0 的段，将段内的字符都变为 \texttt{?}。问最终是否可能得到全 \texttt{?} 的串。

注意到，a,b 的地位对等。不妨假设 a\leq b。若存在一个长度 =b 的全 1 子段则立即判定为合法。进一步，将所有 \geq a 的全 0 段变为 1 后，若存在一个长度 =b 的全 1 子段则判定为合法。不难说明这是充分必要的条件。

对于计数，考察问题的反面。不符合条件当且仅当将所有 <a 的 0 子段划分序列后每个段长度严格小于 b。至此已经不难 O(n^2) DP 了。