PKUWC2024 游记

· · 生活·游记

打成勾吧了。虽然烂完了但还是选择性写一下自己是怎么寄的。当然躲在酒店破大防的事情肯定是不会写的（

Day 1

顺序开题。不会 T1。不会 T2。不会 T3。爆。

然后就开始随机枚举 T1 看上去比较优的策略，不记得交了多少发反正是在 1.5h 时过了。

开 T2。继续想了想发现只有相同深度的点 k 级祖先才可能冲突，而相同深度的点可以按 dfs 序排序后，搞出 \le n 个“合并事件”以及发生时间，按时间轴扫描然后启发式合并，那么只有 n\log n 次合并。现在就是单点改区间数颜色数，对每个颜色维护出现位置后就是矩形加单点查，按时间轴 cdq 即可。

看了看时间还剩 1h 啊。好像是 O(n\log n\log^2 m)，但是看上去常数很小很能跑啊，这不开冲？先写了个暴力数颜色数过了 sub 1,2，现在只需要把暴力部分换成三维偏序即可！

不知不觉写了 5k 左右 开始大战小样例。看了一下时间还剩 0.5h，感觉很能调。刷新比赛页面。16:52。

啊？？？你这时钟还要手动刷新的？？

急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急，调你吗调你吗调你吗调你吗调你吗调你吗调你吗调你吗调你吗调你吗调你吗调你吗调你吗

甚至没有发现 3-side 矩形写成了 2-side。

按照正常剧本急急急的后果当然是没调出来遗憾离场，喜提 100+24+0 低于大众分。

蛤蛤。

Day 2

Day1 已经打成傻逼了所以打算拿脚打，结果不重要。

还是决定想 T1。直径肯定是要用每次找到距离最远点那个求法的，关键是如何确定每个点到这个点的距离。进一步撕烤发现只需要找到根的一个儿子就做完了。然后花了很长时间知道了怎么找儿子。好像是 5n 次操作。不管了先写吧，大概在 2h 左右提交并获得 70 分。加了一个小优化就是 4n 次了，获得一个 83。

开 T3。暴力启动。36。

开 T2。特殊性质启动。发掘性质。猜结论。11+17=28。这个时候感觉用这个性质可以拿很多分。撕烤了一下 DP 相关。这时候突然想起了 Day1 的事情于是刷新了一下时钟。

16:50。DP 启动不了一点，退场。

于是是 83+28+36=147。

翻不了一点，似了。虽然好像没 D1 那么傻逼就是了。

我是低水平选手。