NOIP 总结

· · 生活·游记

T1 的历程不算曲折，首先想到了能选 x+y 的一定选最小的 x+y，那么剩下的只有 x。那首先选到不能再选 x+y，然后考虑排序这些 x，然后从小到大选直到不能选为止。敲完发现过不了。

简单思考了以下发现选太多 x+y 不一定优，于是考虑枚举选前 i 个 x，然后将剩下的 m-\sum x 全部用来选最小的 x+y。加上敲缺省源用了 30mins？

接着去看了眼 T2 发现题面有点晦涩难懂于是去开 T3。

观察样例发现答案一定大于以 1 为端点的重链上的点的子树大小之和，观察样例二发现如果树的儿子的子树大小分布的比较均匀的话，以 1 为端点的重链上的点的子树大小之和就会比较劣，于是考虑一个点，不是让整个子树将答案构造成以当前点为端点的重链上的点的子树大小之和，就是从儿子中选出答案最大的转移。

但这很显然伪了，思考过后断定任意一个子树内的点的权值，一定不大于整颗子树的 \operatorname{mex}，于是考虑设出状态 f_{i,j}，表示以 i 为根的子树权值的最大值为 j，很显然最大值 < n 一定不劣。

考虑如何转移，每次枚举一个 j，那么 f_{u,j}=\max (\max f_{v,0\sim j} +f_{u,j},\max f_{u,0\sim j} + f_{v,j})。然后想了大概 2.5h（是的，我在有一点点思路的题上总是会浪费很多时间，得赶紧调整这种策略），发现可能会有一大堆情况，很难维护，大约又想了 30mins 就去写 T2 暴力了。

然后又花了 45mins 把 T2 24 分暴力加 A 性质写和调完。剩下 15mins 猛攻 T4 O(qn^2\log n)暴力，但不知道为什么失败了。

很显然，这次我败在了写题策略上，虽然运气略优于 CSP-S，但是策略却不如 CSP-S。果然，题面越复杂的题目往往象征着题目思维难度较简单，为什么学长说的我没听进去啊？！