NOI VP记

· · 生活·游记

退役选手记录一下。

Day 1

T1 没什么好说的，秒了。

T2 看完题发现以终点为根所有深度相同的点本质相同，所以变成序列问题，然后发现深度大于某个值时决策必然是随机走，感受一下觉得能二分，然后就变成了求邻域内点数和距离和，简单点分树维护一下即可 2\log，严肃开写。

稍微卡卡常就通过了，此时过去 1.5h。

发现 T3 是神秘 ad-hoc，浪费了 1h 思考进制相关的东西发现无果，然后开始拼包并且没拼完，3.5h 怒拿 29 分。

Day 1 赛后

重新调了下 T3，突然意识到可以分等价类，然后随便写了点暴力就拿了 51，给暴力调调参数就 100 了。这也太神秘了。

Day 2

先开 T1。感觉是简单题啊，写写写。

不对怎么这么多 case，不管了直接分讨。

也是赤到史了啊噶人们，1.5h 终于通过。

然后开 T2，prufer 序列吗，这么神秘。

花费 20 min 思考刻画删叶子序列无果，然后考虑直接求 x, y 中更早被删的叶子的删除时间，不妨设其为 x，发现只需要考虑比 x 小的节点的信息，并且会影响 x 的必然构成一段删叶子的前缀，于是可以扫描线+树套树上二分维护，大概花费 1.5h 通过。

此时过去 3h，去开 T3。

T3 看完题发现序列的刻画子孙相对不影响祖先，可以考虑 DP 所有序列在哪几种集合内可能出现，然后考虑从儿子转移过来时只需考虑每个色块内部是否包含仍有对祖先限制的点（下称特殊点），且色块本质相同，所以只需记录 i, j 表示有/无特殊点的色块个数，由于只关心序列内容，所以儿子间如何组合并不重要，只需关心能组合出怎样的序列元素，且 i+j 相同时显然 i 越小越优，简单分析可得有/无特殊点的色块个数的限制几乎独立且是一个区间，所以只需记录有/无特殊点色块的上下界相关信息即可，于是在每个节点处进行一个四维 DP 即可求得。

求出界以后考虑哪些方案是最优的，由上文分析不难得出所有方案构成一个矩形，而我们取的是一个 L 型的边界，所以利用二维前缀和即可贡献到 DP 数组。

整体复杂度可能是 O(n^6) 左右，因为树形 DP 常数太小了，交了一发通过了 n=100，拼上特殊性质获得了 52 pts。

此时还有 0.5h，但是因为我发现上队线了就比较摆。

Day 2 赛后

尝试优化 T3，发现最后从过渡 DP 转移到每个点最终的 DP 数组使用的是二维前缀和，那么对每个点的贡献实际只和两个界有关而非四个界，所以对于每两个界单独进行一个过渡 DP 转移即可将 O(n^6) 优化至 O(n^4)，这一部分是平凡的。

总结

今年 NOI 的题都是可做题，T3 难度相对去年简单不少，除了 d1t3 相对神秘外其他题在保持训练状态下场切问题都不大。