【MX-S5-T3】IMAWANOKIWA (Construction ver.) 题解

· · 题解

结论：

接下来给出证明。

C 是显然的。若不满足 C 即存在非 0 的数，那么 ppc 不可能清 0。

我们证明 DE。

充分性：

若是这个结构，因为 (2,1)\to2,(2,0)\to1，所以只有中间一个 0 可以消去 2，那么必然留下一个 2 无法消去，最后还是 2。

必要性：

若不是这个结构

  • 若 2 的数量大于 2 个，我们有如下策略：

  1. 把所有非 2 的数合并，最后形如 2(0/1)2(0/1)2，不难发现合并顺序并不影响结果。

    • 若没有 0，则用 2 吃掉所有的 1，再两两合并成若干个 1，此时不会剩下其他东西，直接合并成 1 即可。
    • 否则找到所有形如 21212 的极长连续段，它的前面或者后面必然有一个 0，用 2 吃掉所有的 1，再两两合并剩下 1 或 2。
    • 如果周围有 20 或 02。
      • 如果不是 20(1/2)02，那么如果是 1 就和 0 合并成 1 再用 2 吃掉抵消影响。注意此操作不会影响 2 的奇偶性。
      • 否则形如 20(1/2)02，注意到因为 2 是偶数，所以中间的 21212 段中 2 也是偶数，所以实际上只有 20102 一种情况，按如下方法合并即可：20102\to1102\to111\to 1。
    • 否则偶数个 2 合出的是 1 直接结束。

  4. 那么现在只剩下形如 20202 的串且 2 的个数为偶数，注意前后也有可能有 0。

    • 如果前后任何一个位置有 0，那么 0 的数量大于等于 2 的数量，全部合并即可。

    • 否则我们先随便找到一个 20 合并把 2 的数量变成奇数，然后找到所有 20202 的子串，注意这里不是形如，有如下方法可以合并：

      那么我们除了最后一次合并用法 2 其他都用法 1 即可合并出 1，因为每次可以减少两个 2。

  • 否则形如 (0/1)2(0/1)2(0/1)。

  • 如果 0 大于等于 2 个，那么和 2 合并即可。

  • 否则必然形如 (0/1)212(0/1)，用 2 吃掉中间的 1 然后两个 2 合并即可。

至此所有情况讨论完。

所以此结论得证。

证 AB。

充分性：延用偶数变成奇数后的策略。

必要性：假如没有 0，那么 1 不会对 2 的数量产生影响，只能两个 2 对碰，最后还是会剩下一个 2。

至此所有情况讨论完。

所以此结论得证。

实现的时候先判掉所有答案不是 1 的，这些都可以一直删第一位完成。

发现一定存在操作序列满足只操作过前 3 位，下面是策略：

  1. 如果第一个数是 0，那就一直操作第二个数，最后剩一个和 0 合并，无论剩什么都是 1。
  2. 否则一直操作第一个数直到第二个数是 0，然后一直操作第三个数。最后剩下三个数形如 ?0?。
  3. 如果不是 202，那么最多只有一个 2，和 0 合并了就可以了。
  4. 否则因为不是 111202111，那么不是 21111 的那边
    • 是右边，合并的过程中 0 右边一定存在过 1 且后面还有 2，那可以用它把 0 吃掉，最后 22 合并。而这个过程先缩前面，后面一定可以操作点 3，而前面没有 0 只能是有 22，那拿哪个 2 吃 1 都是一样的。
    • 是左边，若 0 左边是 1 那再左边肯定是 2，直接 10 合并然后 22 合并。否则 20 前面极长 1 前面总是 0/2， 直接 12 合并 20 合并然后 0/2,2 合并。

也就是说对于所有情况，其最小的第一次操作一定小于等于 3。

继续往下思考直接分讨寻找字典序最小的构造不如利用这个结论字典序贪心，即贪心的把每一位能往小选就往小选。我们发现如果操作一个位置不影响答案，就可以操作。于是维护序列 0,1,2,202 的个数容易判断哪一位可以被操作。前三位是可以暴力删除的，最终是常数略大 O(n)。