摘要:无

11192020纪中培训赛

summary

T4的数据结构给我调了一下午加一晚上了,T3的矩阵优化dp还没写,马上下自习了就把总结写了吧.

刚看完题就发现T2可做,一眼发现了向两边扩展的性质,然后就做到线性了,10分钟就打完了.

然后去做T1,推了一波式子发现没什么特点,于是推了个判断删除的不等式,vector里按k单增插入进去,每次二分出删除的区间暴力删,但是发现一边枚举一边筛迭代器不好做(流下了没有语言基础的泪水),而且vectorerase函数是很慢的,于是就给删掉的元素打个删除标记,操作了根号次之后重构vector,本来觉得这么奇怪的做法拿不到多少分的,估分写的30pts,结果复杂度是对的直接过了…

T3又期望又计数我直接不怎么会,连$O(nk)$的简单dp都没写出来,写了个$O(n^2k)$的大力dp加一波性质优化常数拿了20,后来想了一想多设一维就可以做$O(nk)$了…然后把这个转移拿去写成矩阵,矩阵套矩阵乘出答案矩阵就好了,貌似很难写,明天有空来写了.

T4同样没什么思路,于是就去打部分分了,首先是发现题目相当于是在无根树上不回溯地遍历,然后如果从一个点开始,到第一个拿到钥匙的点的之前的路径都相当于是无效的,所以就从有钥匙的点开始枚举,把这些点当作根,向下面枚举出一条最大的链即可,设有钥匙的点有$k$个,那么复杂度是$O(nk)$,结合后面有特殊性质的数据可以拿到40pts,然后是$x=y$的20pts,发现很像赛道修建那道题,就维护一颗无根树上权值最大的路径,在每个点上维护子树里面的接上来的链,然后把最大和次大拼起来更新答案,并把最大的一条接到父亲去.

其实T4的正解也不难想,以前做过一道期望题的转化方式就很像,就是说要得到树上的一条路径,如果$y$出现在$x$的前面就有贡献,那么考虑每个起点和终点的位置会包含哪些贡献,这个构成了一个二维的关系,就可以用线段树做扫描线,每次在二维关系上加上贡献,取最大值即为答案,具体实现要考虑一波dfs序,而且还卡常特别恶心…应该多留心dfs序的应用的,有些地方打得很丑.