别样的 PKUWC 游记

· · 生活·游记

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

\text{Day ?}

得甲流了。

\text{Day 1}

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

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

试机。

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

开题。

然后脑海中突然闪过 $ \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 $ 和我同复杂度但是通过的？这就是高贵的小常数选手吗。 晚上吃了十万片润喉片，让咳嗽好了一点。 ## $ \text{Day 2}

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

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

开题。

分讨到一半，突然想到能不能选 $ 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 $ 了，并且到最后都没调出来。 出考场发现身份证又丢了。回考场找前台去拿。