PKUWC2025 游记
Bingxiu2
·
·
算法·理论
为什么文章分类 生活·游记 不能申请全站推荐
Day 0
还没放假。
Day 1
考试前 6 小时
还没睡醒。
考试前 4 小时
报到，但是找不到在哪里报到。
Day 1
T1 似乎很难。
T2 似乎特别难。
T3 似乎特别难。
感觉 T1 可做？
然后用草稿纸画了个图，发现条件等价于 a+b 个点的图，最小点覆盖 \ge b+1，求最少的边数。
写了一下，过了。
T2 似乎特别难。
T3 似乎特别难。
感觉 T3 只能 SG 函数硬算，写了一下，拿了 20。
性质 AB 完全不会。
T2 似乎特别难。
最后还是想不出 T2 比暴力更优的解，打了暴力。
100+24+20=144
唐。
Day 2
T1 交互题，一看就不好做，直接跳过。
T2 性质看上去很好做，写了倒推的 dfs，搜过了。
T2 O(n^2 \log n) 看起来可做，dp 过了。
总共 73 分。
T3 暴力 36 分，条了很久。
还剩两个小时左右，开始看 T1。
先用 abc+abd-acd-bcd=2(ab-cd) 和 abd+abe+cde-acd-ace-bde=2(ab-ac) 找到离一个点最远点暴力算直径做了 n \le 6 \times 10^4。
然后不会做，乱搞试了好几发，没用。
快结束的时候想到可以用 2xab+acd+bcd-abc-abd=2(xb+xa+cd)，在 a,x,c,d 固定的时候可以只额外用 1 次询问计算直径的另一端。
调到 16:56，交上去，评测的特别慢，评测到 16:59 才评完，评测的过程中怕自己挂先对拍了 400 组 n \le 7 \times 10^4 的数据，都过了，然后看到 83 分过了 n \le 7 \times 10^4。
83+73+36=192
唐。
总分 144+192=336
唐。