AT_agc048_f之传奇闹麻了分讨哥

AT_agc048_f总共有三个证明步骤

  1. 证明一个由两个好串拼起来的串中，拿去极大好串剩下的也是好串

我们把剩下那个串拿出来，考虑反证法，如果有这样的意味着出现了两个连在一起的1（或者 0，反正都一样）

而这两个 1 为何都没有被取走呢，这说明在匹配这两个1的过程中，前面分别都是1在做这件事，而将这些已匹配过的拿走，他中间连在一起也证明这两个1中间一定是一个奇好串。

而这样一个是极大的，是否能由两个好串拼起来呢？

考虑前面一定是一个以 0 结尾的串（实际上是为了方便，如果不是的话就到前面去搞，如果前面没有了的话，那就与题设矛盾）

而如果中间这一段想要投入使用，前面一定是一个以 1 结尾的串。

那么我们回顾一下这个串究竟能不能是好串拼起来的，在第一个 1 前面由于既有 1 又有 0 ，所以长度是奇数，一定既有 1 又有 0，这个时候你猛然发现，如果和 0 连在一起并把中间的拿下，则后面的 1 卡住了，如果和 1 连在一起，则与极大情况无异，也就是说这个串根本不是好串拼出来的。

  1. 证明两个好串拼起来的串可以把长度换成在他们之间的串

我们先取极大好串再把剩下的拿上，那么考虑从小好串的视角来看，他每一个都是一个分界点，而大的只有叉在两边的可以不与他合并，根据鸽巢原理，中间可以替换的必然有其中之差，也就是小的可以通过替换换出大的来。

  1. 证明前缀条件充分必要

我们先不断取极大把S取完，然后考虑必须前缀的0和前缀的1都是比L垃圾一点才行。

首先是必要性，因为 L 是极大所以这个显然成立。

其次是充分性，考虑我们有了这个条件之后能用L把这个东西换出来就好了。

整体思路：

  1. 为什么要倒过来？

如果不倒过来的话，就会有两种形式分别是010101和101010，很丑陋而且不方便统计

  1. 怎么做dp

考虑你有了那些性质之后就可以直接dp，由于对于每个长度序列长度L最大n/L，所以dp能够做到nnnlnn，如果实现的牛一点，可以除以一个贼jb大的常数，相当于没了ln。

  1. 想到再来写
posted @ 2024-06-26 18:01  Yanami_Anna  阅读(151)  评论(0)    收藏  举报