省选 VP 游寄

· · 个人记录

前言

太菜了，只能 VP

Day 1

把题目都看了一眼。

T1 可以把询问排序后扫一遍，复杂度 O(n) （桶排），样例全过，应该没锅。

中间修修补补写了 1h ？？？

T2 看了一眼，一眼不可做。

T3 一看就是数据结构。

考虑合并答案，对于点 x 假设它的所有子树已经处理好，那么在 x 上的人如果要替换一定会优先替换最小的，因此在树上从下往上处理，子树内最小值用一个线段树就可以解决（编号连续）。

修改我不会，只能暴力。

复杂度 O(m \times n \log n) 貌似可以骗到不少分。

中间又修修补补了好久，直到还剩 10 min 才冲过大样例。

也希望没有锅

最后估计 [100,100] + [0,0] + [40,54] 再次祈祷无锅

Day 2

看了眼 T1，因为情况只有 10^6 种，所以一眼 SG 函数上 DAG dp ，具体来说给每个状态记录最大/最小步数以及谁赢谁输或者平局，开始写。

写了 3h 发现不会处理环。

打了个 55 的暴力跑路。

考后机房大佬说：T1 algha-beta 剪枝，T2 dinic ？

估分 [0,55]

总结

感觉 Day 1 不算很差（？），Day 2 确确实实打崩了，主要原因是死磕 T1。

菜，滚回去卷 whk 了好像没停课，一直在搞 whk ？

end

出分了，挂到了 183 （虽然很菜但是好像是系初一 rk1 ？）