ARC110E Shorten ABC

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 给出长为 的字符串 ，字符集为 。

可执行下列操作任意次（包括零次）：

  • 选定 使得 ，将 换成和原来的 均不同的字符（这个字符是确定的），并删除 。

求你能获得的不同的 的个数。

，时限。

可以发现，最终一定是一段段的字符合并在了一起。

记 的权值分别为 ，每次合并相当于将两者的权值 xor 。这告诉我们，区间确定了，合成出的字符就确定了。

但这没有考虑相邻不同的限制。

  • 若区间异或和为 ，显然有异常。

  • 若非 ，区间清一色是显然无法合成。

  • 否则，必能找到一对能合成的字符，且合成之后仍然满足“区间异或和非0”，“区间并非清一色”，归纳即可。

    具体地，随便找一对相邻不等字符 ，若合成后区间清一色，说明其余字符都为与 不同的 ，那么可以让 合并（谁不是边界用谁）。

综上，除非区间异或和为 或清一色（称这样的区间是好的），总有合并方案。（单个字符也可以看做有合并方案）

现在就相当于，将 划分为若干好段，且统计好段们的异或和序列数目。

思考如何判定一个 能否被生成，考虑贪心（简化方案原则）。

首先 的异或和要等于 的异或和。

可能有许多的生成方案，我们考虑其中最“靠前”的一个，即每个好段的右边界都尽量靠前。

每次选一个最短的可行的段进行转移，到 的最后一个字符，直接选完 剩下的所有字符。

为了说明正确性，我们需要证明对于任意存在方案的 ，必然可以被上述算法构造出一种方案。

对于 的某种方案，选出第一个好段的一个异或和为 的后缀，满足去除之后第一个好段仍然是好的，将其转接到第二个好段前方，如此重复，不难发现，正得到了最“靠前”的方案。（调整法）

于是我们只需要计算“靠前”的方案数目。

记 为 的“靠前”的好段划分数目。

每次向前枚举上一个字符 ，找出最小段进行转移。

注意最后一段（必须是异或和为 ）要补掉，故答案不仅仅是 。特殊地，当整个串清一色时不能补 ，此时答案必为 ，特判。

复杂度 。