APIO2020

就呆机房考试了一上午，写个屁游记啊。

边打 APIO 边写游记，这感觉很妙啊。

考试

Painting Walls

被题意卡了一小会，搞懂题目后发现就只要对于每个位置暴力枚举如果从该位置开始染色，第一个工人是谁，然后 DP 一下。一开始用了 map 去 DP ，被卡了。然后换滚动数组去 DP ，结果发现还是被卡了。查了好久才发现我用了一个 set 在每次更新 DP 值后都会执行 insert 操作。。。我因为它的大小是 \(O(n)\) 就莫名其妙的地以为这个 set 带来的时间复杂度始终是 \(O(n\log n)\) 。。。

Swapping Cities

有理有据的分析可以发现一个子图中 \(x\) 到 \(y\) 是合法的当且仅当有度数为三的点或者有环。然后这就是大家所熟知的 Kruskal 重构树了。

Fun Tour

一开始打了一个基于重心的贪心，交上去只过了 \(n \le 7\) 的分，疯狂对拍 冷静分析后发现贪心假了。

然后就打了暴力 dfs 的 26 分，继续想，想了个有理有据的动态换根 DP ，由于 subtask3 的树高是 \(O(\log)\) 的，可以暴力修改 DP 值。于是写写写写写写写，越写发现细节越多，写着写着突然发现比赛结束了。。。

结果

226 分垫底水平，居然还有金牌，可喜可贺。