PKUWC2025游记

luuia · 2025-01-16 08:46:28 · 生活·游记

Day 1

没带笔，没办法用草稿纸。

开 T1，先胡乱猜了个奇偶性都不对的结论 \dfrac{(a+b)(b+1)}{2}，然后发现过了 a=2 的点，想了一下当 a > b + 1 的时候可以两两分组测，答案是 b+1。

然后开始想 a=3，考虑了分成两组单独两两测的策略，过了前 30 分。发现改一改分成 a-1 份就是正解。写了一下，在 14:00 过了。

看了一下 T2，发现只会 n^2\log n，具体倍增维护一下祖先然后加到 set 里面就行了，结果冲过了 10^4，可能是数据没卡满。

睡觉 3h。100+24+0=124。

Day 2

又忘带笔了。

开 T1，很快发现可以通过 10 次询问解出五个点间两两的距离，那么就得到了一个 5n+\operatorname{eps} 的做法，因为边角要多几次询问，过不了 6 \times 10^4。还因为 n=4 的 corner case 调了好久。生气，喝掉了免费给的 6 瓶水，上了 8 次厕所，这下真是 wc 了。

然后看到 T2 的 c=1 是容易的，打了 T2 和 T3 的暴力。

尝试去想 T1 但无果，最后罚坐到结束。56+11+6=73。

赛后出来发现如果只关心一些点到一个点的距离，可以用更少的询问做到。这个好像是正解。

D2T1 正解？

因为 \binom{5}{2} = \binom{5}{3} = 10，因此可以通过 10 次询问解出五个点间两两的距离。

求直径可以用 grader.cpp 里面的做法，需要 2 次询问每个点到点 w 距离的 \max。

对于每次查询，先解出 5 个点两两的距离 a_1,a_2,a_3,a_4,w。考虑询问 (w,x,a_1),(w,y,a_1),(w,x,y)，就可以通过 3 次询问得到 \operatorname{dis}(w,x),\operatorname{dis}(w,y)。

因为 \operatorname{dis}(w,a_{1 \sim 4}) 已经询问过了，那么共需要 3n+\operatorname{eps} 次询问 1。注意要特判 n \le 4。