AT3950 [AGC022E] Median Replace

约瑟夫用脑玩 · 2021-07-27 09:42:21 · 题解

题解区令人迷惑的一道题，我来认真解释一下。

这是一篇偏理解的题解，如果你想理解而不是写代码的话可以来瞰瞰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 消掉，那么有三种情况：

栈顶堆 0，下面无 1，即 1 个 0，不合法。
栈顶堆 1，没有 0，即 11111...奇数个 1，合法
栈顶堆 0，下面有 1，考虑 0 和 1 的数量：
- 11100 此时合法
  
  那么我们发现下面堆的 1 只用留 3 个就可以把 2 都消掉，如果 1 比 3 多一定合法。
- 1110 为奇数，不存在
- 1100 不存在
- 110 合法
- 100 不合法
- 10 不存在

如果手动编号转移可能把人都转崩，发现用 0,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 的个数自动转移。

这样做常数肯定减小，但就特别的搞人理解，关键是说的不清楚！

就算有 “?” 自动化转移也很好实现，代码就不放了。