题解：AT_agc045_c [AGC045C] Range Set

· · 题解

显然状态的 01 可以翻转，不妨假设 A \leq B。

正着做很难 dp，反着来试试。

考虑终止状态怎么还原到初始全零的状态，由于执行的是覆盖操作，在此之前被覆盖的值是何种我们一概不管，0/1 任填，设为 ?。

那么操作一就变成了让一段现在是 0 和 ? 长度为 A 的连续段全都变成 ?，操作二同理。

那最后变成全 0 的条件显然就是把 1 全部删除，要求进一步转化成了，需进行至少一次操作二。

如何凑出一个长度为 B 的合法段也是好做的，可以先把若干个 A 段变成 ? 然后拼起来。

复杂度 O(n^2)。

Submission #71382704 - AtCoder Grand Contest 045。