AT3950 [AGC022E] Median Replace

题解区令人迷惑的一道题，我来认真解释一下。 这是一篇偏理解的题解，如果你想理解而不是写代码的话可以来瞰瞰qwq。 先考虑对于无 “?” 的确定串考虑是否合法，首先我们要求最后剩的数是 1，那么我们就得消 0。 消 0 最有效的手段就是 000，我们从左往右维护一个栈表示前面剩余数的情况，那么我们希望看到的就是 0 堆在栈顶，从而消去 0。 考虑栈顶都是 0 时来了个 1，我们偏感性的理解一下： - 如果只是虚晃一枪，后面继续给你丢 0，那么我们显然把 [x01]00... 变成 [x]00 不劣，更可能消 000。 - 如果是真的要给你很多 1，那么我们把 x[011]1.. 变成 x[1]1 也不劣，本来就会挨着往前消。 简单来说就是如果后面来 1，我们正常来说就会把这个 01 给消掉，如果后面来 0，这个 01 阻断了前后 0 的相连，我们也会把它消掉。 那么以上就是栈顶堆 0 的情况： - 如果有 000 直接消成 0，血赚，情况不变 - 如果有 01，消掉不亏，情况不变或把 0 消完 栈顶堆 1 的情况： - 如果一直来 1，我们暂且不考虑需要几个 1，先堆着，情况不变。 - 如果来了 0，我们希望的就是 0 堆着消掉，我们也堆着，此时就转化为栈顶为 0 的情况。 发现按此策略，0上面不可能堆 1，1 上面可能堆 0。 那么有情况：空栈，全是 0，全是 1，1 上有 0。 但由于串为奇数，每次消掉 2 个，最后的栈也一定为奇数。 首先 0 至多 2 个，如果再多就会有 000 消掉，那么有三种情况： 1. 栈顶堆 0，下面无 1，即 1 个 0，不合法。 1. 栈顶堆 1，没有 0，即 11111...奇数个 1，合法 1. 栈顶堆 0，下面有 1，考虑 0 和 1 的数量： - 11100 此时合法 那么我们发现下面堆的 1 只用留 3 个就可以把 2 都消掉，如果 1 比 3 多一定合法。 - 1110 为奇数，不存在 - 1100 不存在 - 110 合法 - 100 不合法 - 10 不存在 如果手动编号转移可能把人都转崩，发现用 0,1 的个数来代表状态是唯一确定的！ $\left(x,y\right)$ 代表栈中 $x$ 个 0，$y$ 个 1。 以下仅列举串长为奇数的情况，偶数同理，画个表格(横 $y$)： $\begin{array}{|c|c|c|c|c|}(x,y)&0&1&2&>2\\0&\text{空栈}&\text{合法}&\text{不存在}&\text{合法}\\1&\text{不合法}&\text{不存在}&\text{合法}&\text{合法}\\2&\text{不存在}&\text{不合法}&\text{不存在}&\text{合法}\end{array}$ 如果丧心病狂，手动转移，把不存在的状态全部压掉应该可以做到 $5\sim6$ 种状态。 完全不压直接转移就是 12 种状态，压了一半是 9 种状态。 我说停、停，还能压一半？然而事实就是如此，许多题解都这么搞：把 $y=3$ 的那层直接压到 $y=2$ 的那层转移，仍然使用 0,1 的个数自动转移。 这样做常数肯定减小，但就特别的搞人理解，关键是说的不清楚！ 就算有 “?” 自动化转移也很好实现，代码就不放了。