The 2023 ICPC Asia Hefei Regional Contest-526互联

写在前面
赛时
- F
- E
- J
- G
- C
补题
写在最后

写在前面

赛时题目按照过题顺序排序，赛后补题按照个人向难度排序。

省流版：要寄了吗？没寄。

赛时

F

开局我正开，过了五分钟发现已经有人手刹了 F 了，几分钟之内大屏幕上一车提交，看了一下发现是超级签到于是 Nebulyu 上机开写。冲完之后发现 T 了？？？？\(10^5\) 单 log 怎么几把 T 的我草？？？然后 map 改成 unorder_map 还是 T。

已经在最傻逼的签到上挂了两发了，因为挂一发 20min 所以完敢再乱改了，但下机思考了十分钟还是不能理解。期间 dztle 上去写了 E，但还是不知道怎么改 F，明明是超级签到。dztle 提议因为直接字符串比较太慢了换成哈希于是我上去改了发但还是 T，这个时候心态有点崩了。

这时候看到了发的公告，原来是评测机炸了，处理不了高并发，所有题的绝大部分 AC 全都变 TLE 了，说是修好马上会安排 rejudge。

？我草

这个时候心态有点崩了，之前看着榜上八十万个比较幸运没被高并发限制的队疯狂过 F 但这么傻逼的签到就是死活出不来，就算看到了公告也不太能确定到底是真 T 了还是真被评测机坑了，虽说这个复杂度绝对不可能有问题、、、、

然后亲眼看到半个小时前第一发的 T 突然变成 pending 然后 A 了呃呃呃呃

纯签到。

E

在 Nebulyu 上去写 F 的时候 dztle 发现 E 是超级套路之拆曼哈顿距离，离散化完之后对每一维每一种权值分别前缀和统计即可。然后在 F 因为评测机挂掉的时候上去写了 E。过完样例之后我去陪着改了改，怕爆 LL 于是直接无脑 define int long long 了，然后第一发 RE 了？？？加下数组改了一发又 RE 了我草。

然后把代码打印下来慢慢看，这个时候 F 还是过不了，于是决定放一放，Nebulyu 就上机去开了 J。期间出现了上面 T 变 A 的的戏剧性一幕呃呃

然后在 dztle 和我盯着代码不思其解时我突然脑子一抽看了一眼桌子上的选手须知，我草原来 MLE 是会显示 RE 的，然后瞬间难绷了

于是大力开搞直接删了一半的空间，直接过了。

顺带一提这个时候因为在大量 rejudge，评测机奇慢无比，第一发 E 和第二发 E 直接隔了十分钟才测出来，因此花费了很多时间在静态调错上，非常不值。

签到。

J

在 dztle 写 E 的时候 Nebulyu 和我讨论了下，我口胡了一个假做法，Nebulyu 口胡了一个半真做法，但是比我那个真多了，在第一发 E 挂了第二发 E pending 的时候开写。过了样例之后我随时造了一组数据卡掉了呃呃，然后开始调。调了挺久都过了然后交了一发挂了。现在距离比赛开始已经过去了 01:24:38，我们现在还只过了 F，排名 280+，属于是超级劣势的开局呃呃。

然后 Nebulyu 下机和我讨论，彻底把我那个假算法叉掉了，然后脑子一抽好像出了真算法，然后继续上机。过了半个小时我看了一眼桌子上的选手须知，然后把 dztle 拉过来把 E 过了。现在距离比赛开始已经过去了 02:01:54，我们以两发罚时代价过了 E，排名 270+，属于是超级劣势的中期呃呃。

这个时候 Nebulyu 把真做法改出来了，然后交了一发挂了。然后看了几分钟原来是复制代码块出的锅呃呃，改了发过了，yes。现在距离比赛开始已经过去了 02:13:56，我们以两发罚时代价过了 J，排名 110+，属于是难铜的水平呃呃。

顺带一提这个时候评测机还是奇慢无比，大概要五分钟才能测一发。

那么之后呢？

难道真的要寄了吗？

这题的数据似乎比较弱的样子，Zhihu 上有老哥说用过不了对拍的程序跑了过去，笑烂了。我也不太能证明 Nebulyu 的这个算法，总之过了就先扔在这里。

考虑先做 Kruscal 直到 1 和 \(n\) 即将连通，然后枚举所有边检查加入此边后是否可以使 1 和 \(n\) 连通，对于所有满足条件的边计算此时路径 \(1\rightarrow n\) 对答案的贡献并取最小值即可。

G

答案是没有寄，寄了的话我直接在开头谢罪了。

时间回到 Nebulyu 在大战 J 的时候，dztle 先把 E 放了下和我一块开了 G。首先考虑了一个数学意义上的抽象，把操作看做合并相邻两个数，然而这东西屁用没有，遗憾离场。然后回到一眼的二分答案上。

这个时候午餐麦当劳来了就花了三分钟把饭吃了。手玩样例的时候我发现我题读错了呃呃，是求第 \(k\) 大的数不是第 \(k\) 大的权值，于是脑子一抽想到一个 DP 设 \(f_{i, j}\) 表示对于 \(1\sim i\) 修改得到 \(j\) 个大于等于二分量 \(\operatorname{len}\) 的全 1 段的最小代价，然后发现不会转移。突然又脑子一抽发现这东西转移的时候仅需考虑从 \(f_{i - \operatorname{len}, j-1}\) 转移过来就行，转移的代价即 \([i - \operatorname{len} + 1, i]\) 中 0 的个数。为了方便再修改下状态加一维 \(0/1\) 表示将第 \(i\) 位改成 0/1 就做完了。

芜湖！现在 Nebulyu 还在大战 J，但是有希望了这下。

然后又去开了别的题，看了 K 但赛时肯定是读错题了，口胡了一个树形 DP 觉得能做。

这个时候 Nebulyu 写完 J 交了开始 pending 了，我立刻上机开写。本来还想先写 K 的，文件建好了发现 K 到现在一个都没过，觉得有诈于是立马转去写 G。写了半个小时调了调过了，写的过程中 J 也过了，芜湖！现在距离比赛开始已经过去了 02:13:56，排名 70+，属于是有银的可能但还不太稳的水平。

但是半小时内连过两题把排名狂刷回来相当令人振奋，心态回来了，于是继续开题。

先二分答案检验是否可以使答案 \(\ge \operatorname{len}\)，check 时设 \(f_{i, j, 0/1}\) 表示将 \(1\sim i\) 修改至含有 \(j\) 个不小于 \(\operatorname{len}\) 的全 1 段，且第 \(i\) 位钦定为 0/1 所需的最小操作次数。设 \(\operatorname{cnt}(l, r)\) 为 \([l, r]\) 中 0 的个数，然后有如下三种转移：

\[\begin{aligned} &\begin{cases} &f_{i, j, 0} \leftarrow \min{( f_{i-1,j,0}, f_{i -1,j,1} )} &(s_i=0)\\ &f_{i, j, 1} \leftarrow \min{( f_{i-1,j,0}, f_{i -1,j,1} )} &(s_i=1)\\ \end{cases}\\ &f_{i, j,1} \leftarrow f_{i - \operatorname{len}, j - 1,0} + \operatorname{cnt}(i - \operatorname{len} + 1, i) \end{aligned}\]

然后检查是否有 \(\operatorname{min}(f_{n, k, 0}, f_{n, k, 1})\le m\) 即可，时间复杂度 \(O(n\log n)\) 级别。

C

在我写 G 的时候两个人又去开新题。看 BC 过的比较多就都去看了，因为 B 过得多而且认为 C 是个牛逼计数于是看了看放下了主攻 B 去了。

然后我写完 G 了之后就暂时没能写的题了，就加入其中看了看 C，一看这不他妈 PAM 板题吗，复制一份扔后面就做完了我草，笑烂了，然后又马上上机开写，搬出 oi-wiki 出来开抄，写完之后发现过不了样例于是开始输出调试，然后发现一倍串中的回文串会被统计两次，然后想了下就发现建两次 PAM 并把信息作差就做完了，于是立刻改，过了样例检查下没问题就交了，交完就马上赶去去上厕所了。

顺带一提早在两个多小时前就想上了，但是厕所排长队索性直接不上了。这下连写两题才能去上，又成代码黑奴了。

上完厕所回来发现一发过了，当场叫了一声，把隔壁吓着了。

现在距离比赛开始已经过去了 03:24:25，排名 52，纯种的 5 题尾。但是银估计是很稳了。

在我当代码黑奴时候 Nebulyu 和 dztle 出了 B 的 \(O(n^3)\) 做法，感觉有戏于是上机开写。但是写着写着发现原来以为可以推出来的信息不得不再加一维状态来维护，而且到最后也没想到优化方法，遗憾离场。

封榜时我们是 74 名，最后几分钟统计了一下底下四题队的 frozen 题数，虽然我们罚时烂掉了但也就 20 多队有希望能踩到我们头上，感觉还是相当稳的。

PAM 板题，考虑把字符串复制一份扔到后面构成二倍串。因为 PAM 中的个状态都对应原串的一个本质不同回文子串，直接遍历 PAM 即可得到所有种类的回文子串的出现次数。

但直接这样做会把一倍串中的回文子串统计两次，于是考虑先对一倍串建 PAM，对其中每种回文子串出现次数记录下来，然后再建二倍串的 PAM 然后对记录的出现次数作差即得题目所需的出现次数。因为建 PAM 时用的也是增量法，所以一倍串中所有状态和二倍串种对应回文子串的状态也是完全相同的，于是记录一倍串信息时直接记录每个状态的出现次数即可。

总复杂度 \(O(n)\) 级别。