我们队赛时被 J 题创死了 awa

离做出来差一个剪枝，而且赛后试了试不加剪枝甚至能过……

6 题离场。

一些题解

J 套娃

先对 \([0,n]\) 中每个数 \(k\) 分别考虑。

假设总共出现了 \(c\) 次 \(k\)，第 \(i\) 次出现的位置是 \(pos_{i}\)，（令 \(pos_0=0,pos_{c+1}=n+1\)），则只有处在 \(pos_{i-1}\) 和 \(pos_i\) 间的区间可能 mex 等于 \(k\)。假设 \(pos_{i-1}\) 和 \(pos_{i}\) 中间存在 mex 为 \(k\) 的区间，那么存在一个最短的在 \(pos_{i-1}\) 到 \(pos_{i}\) 的区间满足其 mex 等于 \(k\)，设其长度为 \(d\)。可以观察到，所有长度在 \([d,pos_i-pos_{i-1}-1]\) 中的区间都能取到至少一个 mex 为 \(k\) 的位置。

经过上面的分析，问题就变成，对所有 \(k\in [0,n+1]\) 求出 \(c+1\) 个 \([d_i,pos_{i}-pos_{i-1}-1]\) 这样的长度区间，它们的并就是 mex 能取到 \(k\) 的区间长度的集合。然后从小到大枚举 \(k\)，对 \([1,n]\) 每个长度 \(l\) 检查 \(k\) 是不是第一次覆盖不到 \(l\)，如果是，则 \(l\) 的答案就是 \(k\)。最后剩下一直被覆盖的长度答案就是 \(n+2\)。

实际实现过程中，可以把用并集覆盖转化成其补集的覆盖，然后从小到大枚举的每个 \(k\) 相当于要给补集内还没有删去的位置标记上答案 \(k\) 并删去，可以用 \(\text{set}\) 维护还没有被补集覆盖过的位置。

下面只需要想办法求出所有 \([d_i,pos_i-pos_{i-1}-1]\) 了。用 \(\text{mex}([l,r])\) 表示下标在 \([l,r]\) 中的数构成的集合的 mex。

首先是 \([pos_i-pos_{i-1}-1]\)，只需要对于每个 \(pos_i\) 检查 \(\text{mex}(pos_{i-1}+1,pos_i-1)\) 是否等于 \(k\)，如果不是，显然不会存在符合条件的 \(d_i\)。

然后考虑最难求的最短合法区间长度 \(d_i\)。

从 \(1\) 到 \(n\) 枚举右端点 \(R\)，然后维护一个指针 \(L\)，初始等于 \(R\)，然后每次找到 \(\text{mex}([L,R])=p\)。这时，\(L,R\) 一定在 \(p\) 的两个 \(pos\) 中间，二分出来在哪两个 \(pos\) 中间，然后用 \(R-L+1\) 更新最小值。因为下标在 \([L,R]\) 中的数一定不存在 \(p\)，且当前 mex 为 \(p\)，所以只有继续往左找到最靠右的 \(p\)，把 \(L\) 变成 \(p\) 才能更新答案。设对于一个 \(R\)，指针 \(L\) 跳了 \(t_R\) 次，则对于整个序列就跳了 \(\sum t_R\) 次，这个跳跃次数当然是可以卡到 \(O(n^2)\) 的，比如说 \(n=100\) 时这个数据：

50 49 48 47 ... 3 2 1 0 0 0 ... 0

这时候我们考虑去排除一些一定不是最优的区间。

如果下标在 \([L,R-1]\) 中的数出现过 \(a_R\)，则不必往前跳了，一定不是最优的。因为这时我们完全可以删去 \(a_R\) 让区间长度更短并且不影响 mex 的取值。

实际测试这么搞可以通过本题。

下面来证明按照这个规则跳指针，\(\sum t_R \leq 2n\)。

把命题抽象一下可以发现就是：

满足 \(\text{mex}(l,r-1)=a_r\) 且 \(\text{mex}(l+1,r)=a_l\) 的区间 \([l,r]\) 的数量不超过 \(2n\)。

设 \(a_l\) 是 \(a_l,a_r\) 中较大的，则 \(\text{mex}(l,r)>a_l\)。那么不存在一个 \(\text{r}\) 满足 \([l,\text{r}]\) 也是合法的区间且 \(a_{\text{r}} <a_l\)，因为 \(a_{\text{r}}\) 此时一定在下标为 \([l,r]\) 中的数中出现过。

因此，两端点中较大的数一定只会对应序列向左向右各至多一个另一个端点作为合法区间。所以这样的区间数量不超过 \(2n\)。

区间 mex 使用可持久化权值线段树维护，时间空间复杂度都是 \(O(n\log n)\)。

参考代码：#1958222 LOJ

C 前缀和

每个 \([l,r]\) 内的数出现一次对答案的贡献都是 1，所以考虑概率和。

枚举 \([l,r]\) 内每个数，再枚举它是生成的序列中的第几个数，可以得到式子：

\(\sum\limits_{i=l}^r \sum\limits_{j=1}^{i} \dbinom{i-1}{j-1}p^{j}(1-p)^{i-j}\)

推一下就是 \(p\times(r-l+1)\)。

D 多折较差验证

理解一下题意发现需要区间 dp，转移时要判断以某个点为中心，某个半径是否可以折叠。这个可以拿原串的哈希值和反串每个位置取反后对应区间的哈希值比较是否相等判断。直接做复杂度是 \(O(n^3)\) 的。

猜一下能感觉到合法的转移点的数量不会太多。可以预处理出来每个位置作为右端点和左端点分别可以从那些位置转移，然后 dp 的时候再判一下转移点是不是在合法的范围内。可以预处理的时候把转移点位置 sort 一下，dp 枚举的是否发现不合法就可以 break 掉了。

复杂度不会证。出题人也这么做，也不会证，但是可以卡到 \(O(n^2\log n)\)。

可以通过。

似乎赛时还有的队写的 \(O(n^2)\) 贪心。

参考代码：#1956813 LOJ （场上写的时候预处理脑子抽了，不知道为啥写个二分，实际没有必要，直接枚举就行，还可以避免使用字符串哈希）

游记

半个多月前给 z 和充哥说要不要一起组队参加 thupc，他们很高兴地同意了，然后他俩这半个月都寄了。

队名：队友不会强联通。z 借鉴 cy 的故事 2333

z 周末留在学校了，我回家休息，充哥请了半个月病假了，周日（比赛日）就可以回来了。

周日早上八点四十起床，吃饭，然后去买了点面包，以防中午特别饿。

九点五十多到机房，发现只有 z 和 qcf 在，上到报名网站和 oj 上看了看，又看了看 qq 群，除了 oj 地址没啥新通知。

由于不知道充哥带不带他的笔记本，所以我和 z 没有提前选座位。

过了一会儿充哥来了，他表示要用机房的电脑，于是我们选了长时间没人坐的三个相邻的位置。电脑好久开不开机。

充哥和 cy 开电脑的功夫，我和 z 去涮抹布，擦桌子。学校水管冻上了，一楼到五楼都没水，难蚌。去饮水机接的水。

喝了杯咖啡。

十一点钟比赛开始。

网速有点慢，四分钟才把 M 交上去。

然后我从前往后读题，充哥从后往前读，z 负责随机看题和看榜。

我大概读 D 的时候 z 给我说 C 过的人多，于是我俩一块儿看 C，推了一下发现是简单的推式子。最开始有个指数写错了，后来又看了遍题发现了，式子马上推出来了，我就让 z 先去看其他题了。然后过了 C。

我们把每个题都读了读。

我拿了个 E，充哥拿了个 K，z 感觉 H 很好模拟就去写 H。

最开始我以为 E 是简单贪心题，头脑有点发热，只管交，写着写着发现不对劲，有几个情况很不好处理，假的做法甚至跑到第 40 个点。罚了五六发后不敢交了，本来考虑要不要写个拍子，但是感觉只能拍 \(n=4\)，也拍不出来啥东西，只好和队友讨论贪心策略。

充哥这时候感觉 K 是个打表题，写了个很暴力的暴力跑着三个棋子的情况，趁着功夫和我看 E。越讨论越发现我的做法假，还不会修，有些慌，思考效率下降。

害怕浪费时间，去帮充哥看 K，大概四个棋子还有几种情况要搜，就开了机房几个电脑一起搜。

我好像忘了开始后一个小时十分钟到两个小时的时候我干了啥……似乎就是怼不出来 E，然后随机看其他题。感觉 A 和 I 两个构造都不太能做，B 最开始感觉会不会是 wqs 二分或者 slope trick 之类的东西，但是手玩了一下答案好像不咋凸，D 看着好像区间 dp，准备干完 E 就写这个。

然后 z 把 H 调出来了，并且卡完了常，比较顺利地 \(O(n\log^2 n)\) 过掉了这个数据范围 1e6，时限 6.0s 的题。

这时候我 E 卡得厉害，就和 z 交流了一下就扔给他了。

充哥趁搜 K 的时候想 J，过了会儿，K 只剩一个情况一直没搜出来了，充哥就编了个答案交，运气不太好，踩中了会 WA 的 \(\dfrac{1}{2}\)。改了一下再交一发就过了，在 z 过 E 之前，拜谢充哥！！！

z 把 E 写了写交，挂了好几发第 7 个点，这题我们已经罚了十几发了，不敢再交，他写了个拍子，拍 \(n=4\)，真把这题调出来了，拜谢小 z！！！

这时候 rank 106，再干出来俩题应该就进决赛了！

由于 J 是数据结构题，z 比较擅长，就去和充哥一块想，我去做 D 了。

我写了 D 的 \(O(n^3)\) 暴力，然后想优化。看起来就很不能决策单调性，于是不会优化。

坐在椅子上，突然感觉会不会转移点很少。测了一下样例和一些自己构造的极限数据和随机数据，发现似乎总和只有 \(n\) 的几倍。管它对不对，花了二十分钟糊完，交了一发直接过了，乐。然后去看大膜你。

z 和充哥那边，大概情况就是，他们（好像是充哥猜的）先猜了个答案是凸的的结论，然后照着这个做了第一步转化。变成了求一些很奇怪的东西。z 接着猜结论，编了个看上去比较靠谱的做法。

他们在我写 D 的时候写这个，一人负责前半部分，一人负责后半部分，然后俩 namespace 一拼。省了挺多时间，四十分钟左右就把这个很复杂的做法糊出来过了样例。

然后交上去 WA……

本地拍了一会儿，改了几个脑抽错误，但是还是 WA。

对着一个数据，充哥说出来这场比赛最恐怖的一句话：“诶？答案咋不凸了啊？”

确认了一下 z 的暴力没有写错后，大家陷入了几秒奇妙的沉默。

比赛还剩不到一个小时，榜上 J 过的队很多，而且大模拟我感觉实现不出来，而且写出来可能复杂度还不行，于是破釜沉舟地和两位队友一起冲 J。

由于 z 和充哥已经一起整了两个多小时了，我似乎不太能理解他们的交流，就自己去嗨思路。作为 DS 菜鸡自然没啥结果。

中间 z 想到的一个做法已经很接近解法了，加个剪枝就对了（见上面的题解）。但是充哥 hack 了一发，没接着想和写。

最后十分钟了，被迫接受现实。充哥看着 B 给我说，这看着可像树上背包加上凸包合并。z 比较沉默。

结束后解榜，我们队封榜后没过一题，掉到了一百五十五名，无缘决赛。