别样的 PKUWC 游记

本文又名：身份证丢失记，突发恶疾记。

得甲流了。

上午 $9:30$ 出发，打车花 $10 \rm min$ 去 $\rm sxyz$，然后发现走错校区了。又花了 $10 \rm min$ 回去，卡着点领了身份牌。

下午去试机，考场外发现身份证没了。让教练回酒店找，结果是掉马路上了。还好有交警相助，感谢交警！

试机。

诶 $\rm T2$ 不是我们 $\rm THUSC$ 的试机题吗。

开题。

$\rm T1$ 有一个很 $\rm naive$ 的想法，就是维护一个点集，然后每次加入一个点，并查询和点集中每个点的联系，这样做最坏是 $\frac{(b+1)(b+2)}{2}$ 的，显然不对。

然后脑海中突然闪过 $\text{NOI D1T2}$，尝试套公式。考虑将所有电池平均分成 $a-1$ 组，那么至少有 $1$ 组包含至少 $2$ 个有电的电池，每组内部两两查询即可。第一发为了卡满复杂度特意枚举了一些奇奇怪怪的东西，但是第二发把枚举删了任然是对的。虽然不会证明最优性，但是代码好写，而且是高贵的 $\rm IOI$ 赛制。

$13:10$ 开 $\rm T2$。一个感觉很好的想法是：显然只有相同层之间会互相干涉，因此考虑把每层分开考虑。用莫队维护，每次加入一个点时考虑他会对哪些 $x$ 产生贡献。显然这只和他与目前最优已经被加入的相同层的所有点的最深的 $\rm LCA$ 的深度有关，而最深的 $\rm LCA$ 只会与他在 $\rm dfs$ 序上的前后驱有关，删除同理。求 $\rm LCA$ 可以用欧拉序做到 $O(n \log n)$ 预处理，$O(1)$ 在线查询。注意到每次产生的贡献肯定是一个前缀，因此可以用 $\rm BIT$ 维护。由于有 $O(n \sqrt{m})$ 次修改，$O(m)$ 次查询，因此用分块平衡复杂度。那么难点就是查询前后驱了！有一坨做法可以做到 $O(\log n)$，可以用 $\rm veb$ 做到 $O(\log \log n)$，但是我不会写。因此先写了发 $\rm BIT$ 上二分的，过不去第 $4,6$ 个包。然后发现这玩意可以用二次离线维护，因此可以做到 $O(n \sqrt{n} + n \sqrt{m} + m \sqrt{n})$，任然没有通过第 $6$ 个包。

然后去开 $\rm T3$，发现只想出了 $10 \rm pts$ 的暴力，似乎 $20 \rm pts$ 的部分分可以用 $\rm bitset$ 硬草过去？但是分值都不如去卡 $\rm T2$ 啊！于是去拼尽全力卡常了。

$16:50$ 拼尽全力无法通过。去写 $\rm T3$ 的 $10 \rm pts$ 暴力。

$17:00$ 暴力没过样例。

最后 $100 + 77 + 0$ 遗憾离场。

赛后看 $\rm LA$ 群似乎有 $\rm T2$ 和我同复杂度但是通过的？这就是高贵的小常数选手吗。

晚上吃了十万片润喉片，让咳嗽好了一点。

甲流恶化了。一个晚上都没睡好，直接把讲座咕了。

中午有点头疼，下午去上机的时候发现一说话就会喉咙痒，因此让教练帮我带了口罩和药过来。感觉当天我说话就像快咽气了一样。不会阳了吧。

开题。

$\rm T1$ 一开始的想法是和求直径类似的做法，一开始选定两个点 $a,b$，然后再找到使得 $dis(a,b,c)$ 最大的 $c$，然后继续做下去。假设 $a,b,c$ 都不是直径端点，那么再找到让 $dis(b,c,d)$ 最大的 $d$，则 $d$ 肯定是直径端点。然后再找到让 $dis(c,d,e)$ 最大的 $e$，则 $de$ 就是直径。这么看来这个做法很对啊！于是开始讨论 $a,b,c$ 中某些是直径端点的情况。

分讨到一半，突然想到能不能选 $4$ 个点，然后三三查询，并保留最大的两个点。写了一发，一分没有。然后发现直径可能是最大点和第三大的点。那可以只删除最小的一个吧！然后记录一下之前的查询就能做到 $3n$，但是最后会剩下 $3$ 个点，发现似乎只能再花 $n$ 步去找出直径。

然后回去分讨。分讨了一年证明了直径一定在 $c,d,e$ 中。那么只需要在第三轮查询时顺便记录一下 $cd$ 中间的某个点 $f$ 就行了。然后还要特判 $cd$ 相邻的情况。然后写了一发，全 $\rm WA$。发现没判 $f=e$ 的情况。然后又交了一发，只过了第 $1$ 的包。发现没判 $cdfe$ 共链的情况。然后过了，耗时 $\rm 2.5h$。

说句题外话，如果在考场上想依赖 $\rm IOI$ 赛制来规避证明，需要第一发就想到所有的 $\text{corner case}$，或者在全 $\rm WA$ 时坚信自己的直觉。

$\rm T2$ 开了一眼没什么头绪，于是就去开 $\rm T3$ 了。发现 $\rm 36pts$ 的部分分很好拿，就打了这一档，然后回去看 $\rm T2$ 了。

发现 $\rm T2$ 可以从前往后删，每次进行操作 $2$ 时尽可能的删前面的。那么就能通过特殊性质的 $\rm 11pts$。

由于可能某次删不满 $k$ 个，会导致代价更劣，因此这时我们可以选择用操作 $1$ 删完最前面的。这种情况下，根据上面的做法，后面的一定没有没操作过，因此可以设 $f_i$ 表示从第 $i$ 位开始删的最小代价，然后模拟往后删就行了。这样能拿到整整 $\rm 71pts$！然而我全 $\rm WA$ 了，并且到最后都没调出来。

出考场发现身份证又丢了。回考场找前台去拿。