P9151 计数题 题解

zrl123456 · 2025-12-20 21:22:18 · 题解

:::::info[闲话] NOIP2025T2 状物，不过更麻烦更恶心。
来一篇严谨证明题解！
::::: :::::info[题目基本信息] 考察；Ad-hoc，动态规划 DP，贪心（NOI/NOI+/CTSC）。
题目简介：

• 1\le n\le 5\times 10^6

时空限制：

• 时间限制：2s。
• 空间限制：512MB。
  ::::: 首先替换成中位数这个操作看起来就不好处理，我们要把它转化一下。猜测操作可以看作删去子串内的特定的两个字符：
• 如果子串是 \texttt{000}，那么操作后变成 \texttt 0，可以看作删去特定的两个字符，\texttt{111} 同理。
• 其余的子串同时包含 \texttt 0 和 \texttt 1，那么如果删肯定都是对的。

那么根据上面的操作的转化，我们容易得到最终得到的字符串一定是原来字符串的一个子序列，那么我们可以钦定最终得到的字符串对应原字符串的若干个下标，记为 \{id_m\}（特别地，规定 id_0=1,id_{m+1}=n）。
那么现在我们要求 \forall i\in[0,m]，(id_i,id_{i+1}) 内的字符均可以被消完，那么我们现在可以研究一下消完的充要条件是什么。
首先你注意到 id_i 和 id_{i+1} 奇偶性相同是肯定不行的，因为这样 (id_i,id_{i+1}) 内有奇数个元素，而每次操作只会减少 2 个元素。
下面我们来讨论 id_i 和 id_{i+1} 奇偶性不同的情况。
观察一下，最终 (id_i,id_{i+1}) 会被消成两个字符，最后会通过加入 id_i 或 id_{i+1} 来凑出一次操作（忽略 id_i=id_{i+1}-1 的边界情况），那么我们会要求 id_i 或者 id_{i+1} 是加入后的中位数，那么我们注意到，当 id_i\ne id_{i+1} 时，不管中间消成了什么，你一定可以加入它们其中的一个来进行最后一次操作，那么当 id_i 和 id_{i+1} 奇偶性不同且 s_{id_i}\ne s_{id_{i+1}} 时，(id_i,id_{i+1}) 一定能被消完。
现在继续讨论 s_{id_i}=s_{id_{i+1}} 的情况，不妨以 s_{id_i}=s_{id_{i+1}}=\texttt 0 为例，否则也可以同理得出结论。
这时，贪心地想，我们肯定想让 (id_i,id_{i+1}) 内的 \texttt 1 的数量尽可能地减少，那么在第一步，我们先让这些 \texttt 1 自己跟自己消，那么最后只会剩长度为 1 或 2 的 \texttt 1 连续段。
现在 \texttt 1 的连续段内已经不能再消了，那这时考虑通过让 \texttt 0 的连续段和 \texttt 1 的连续段互消来进一步形成较长的 \texttt 1 的连续段从而进一步多消去一些 \texttt 1。
现在我们如果将一个长度不低于 2 的 \texttt 0 连续段和一个 \texttt 1 连续段去互消，那么我们直接就把这个 \texttt 1 连续段消没了，达不到我们的目的，所以我们看一下如果将长度为 1 的 \texttt 0 连续段和 \texttt 1 连续段互消会发生什么。
首先我们可以观察到这个 \texttt 0 不管是向左消（即使左边的 \texttt 1 连续段长度为 1，向右消同理），向右消，还是从左右各借一个数消都能导致消去一个 \texttt 0 和 \texttt 1，所以我们这时可以直接没有任何依赖的转化为消去一个 \texttt 0 和 \texttt 1。那么我们可以将 \texttt 1 连续段升级成无 \texttt{00} 连续段，定义它的权值是完完全全地消完后最后剩余的 \texttt 1 连续段长度，那么我们发现，这个连续段的权值只和它原来的长度奇偶性有关。
现在我们在 (id_i,id_{i+1}) 内还有 \texttt 1 时，肯定不会脑抽去消掉两个 \texttt 0，那么这时 \texttt 0 的个数不低于 \texttt 1 的个数时一定是可以消完的。
可能这时你们还没有反应过来，但是 \texttt 0 的个数不低于 \texttt 1 的个数这个限制是非常强的，加上无 \texttt{00} 连续段的权值不超过 2 以及 id_i 和 id_{i+1} 的奇偶性不同的限制，那么这时不能消完的唯一一种可能的情况是形如 \texttt{11001100\dots00110011} 的，同时容易观察到这时不管怎么消都不可能出现长度大于 2 的 \texttt 1 连续段，所以这个情况是唯一的一种不能消完的情况。

归纳总结一下能否消完的判定：

• 若 id_i 和 id_{i+1} 奇偶性相同，那么不能消完。
• 否则：
  • 若 s_{id_i}\ne s_{id_{i+1}}，那么一定可以消完。
  • 否则仅在满足以下所有条件时不能消完：
    4. 对于每一个极长无 \texttt{00} 连续段，它的长度必须是偶数。

好的我们讨论完后我们发现我们还是得不出多项式做法，因为我们直接算肯定会算重，那么我们希望得到一种最小表示来代表一种合法方案，对于子序列来说我们就是想让下标序列字典序尽可能的小。
在寻找普通子序列时我们只需对于每一个位置都贪心地尽量靠前选择位置就是对的，那么本题我们自然也希望这种方法能够直接套用。
那么我们考虑怎么通过数学语言描述这一贪心的成立条件，我们设要在 (a,d) 之间选择一个位置作为第一段和后面段的分界点，选择一个 a<b<c<d,s_b=s_c，那么我们贪心成立当且仅当 (a,c) 可消，(c,d) 可消，(a,b) 可消的情况下，(b,d) 也可消，如果这个条件成立我们可以从初始的 (1,n) 中选择的状态不断推出贪心成立。
现在我们尝试举出反例证明上述命题不成立。根据能否消完的判定，我们尝试通过奇偶性或形如 \texttt{110011} 证伪。

• 奇偶性：根据上述已知 c,d 奇偶性不同，a,c 奇偶性不同，a,b 奇偶性不同，从而推出 b,d 奇偶性不同，所以无法通过奇偶性证伪。
• 形如 \texttt{110011}：由于 b,c 奇偶性相同以及 s_b=s_c，那么通过一定的画图推导我们能得出这时一定存在整数 k 使得 c=b+4k，这时由于 (c,d) 是 (b,d) 的子串那么 (c,d) 也会形如 \texttt{110011}，与假设矛盾，所以无法通过形如 \texttt{110011} 证伪。

所以上述命题成立，故贪心也成立。
所以这时我们至少能导出一个多项式做法了，设 f_i 表示当只考虑 [1,i] 内的元素时最小表示以 i 结尾的子序列数，对于下一位分别是 0 或 1 的情况枚举下一个位置 j 并判断 (i,j) 是否可消除，这样容易导出 \Theta(n^3) 做法。
考虑优化，我们考虑加速判断对于 s_i\ne s_j 的情况我们容易找到，对于 s_i=s_j 的情况我们考虑怎么做。
首先如果 s_i=s_{i+1} 那直接不用找了，否则观察一下后三条条件，第二条条件直接被 s_i=s_j\ne s_{i+1} 阻断了，不需要考虑。我们发现如果 s_{j-1}=s_j=s_{j+1}=s_i 那么在 j 位置和 j+1 位置肯定有一个 \texttt{00} 连续段的后一个下标与 i 奇偶性不同。再观察第四条条件，如果有一个 \texttt{00} 连续段的后一个下标与 i 奇偶性不同等价于存在极长无 \texttt{00} 连续段长度为奇数，所以我们可以转为判断有无一个 \texttt{00} 连续段的后一个下标与 i 奇偶性不同，这个判断是简单的，优化为 \Theta(n^2)。
再次优化注意到上面两个东西预处理都很好维护，所以直接预处理可以优化成线性。
最后枚举子序列的结尾 i 判断 (i,n] 是否能被消完即可。

时空复杂度均为 \Theta(n)。

code