[AGC022E] Median Replace

题解

可以发现,假设最终能变成 0,如果有 000,第一步操作把它变成 0 一定最终仍然能变成 0。这是因为,假设存在一个第一步不是对这三个数操作,考虑第一次影响到这三个数中某个数的操作,如果这个操作就是把这三个 0 变成一个 0,那么可以直接把这次操作移动到第一次操作。否则的话,那么把这次操作改为把这三个 0 变成一个 0 肯定不会更劣。(因为把序列上的一个 0 改为 1 得到的序列一定不会更劣)用类似的思路可以证明,如果有 010,第一步把它变成 0 也不会更劣,如果有 101 第一步把它变成 1 也不会更劣。

考虑一个序列,反复进行以上三种操作直到不能操作,把得到的序列划分为若干个 0 / 1 的连续段,除了开头和结尾的连续段,每个连续段长度至少为 \(2\),且 0 的连续段长度不会超过 \(2\)。显然把 111 变成 1 是不优的。不难用归纳法证明满足这个条件的序列无论怎么操作,都不会出现 000。(考虑在进行一步操作之后,利用 010 变为 0 的结论再进行一次操作,这样就会得到一个更短的满足这个条件的序列)而其他操作都会使 0 的个数和 1 的个数同时减少 1。这就说明满足这个条件的序列,最终能变成 1,当且仅当 1 的个数大于 0 的个数。(长度必为奇数)

对这个东西 dp 一下即可。如果存在一个前缀 1 的个数减去 0 的个数大于等于 \(2\),这个序列必然可以变成 0。所以实际需要记的状态数很少。

代码