赛时

T1 一看暴力分是之前做过的原题,所以就写完了 $O(n^2logn)$ 的暴力,
T2 想了想,发现每次一定要把最小值移动到左边或右边,然后可以递归成子问题去做了
T3 建出来树之后只会暴力 dp。
最后 40+100+25 第三题挂了 20 分完美省三。

题解

A. Game

$O(n^2logn)$ 的做法是显然的:我们先贪心找出得分最高是多少,然后二分每一位放什么,贪心 check 就好了。
我们想如何快速维护这个贪心:我们可以用一棵权值线段树,记录答案,$a$ 的剩余数和 $b$ 的剩余数,合并用左边的 $a$ 去匹配右边的 $b$ 就好了。
时间复杂度 $O(nlog^2n)$
代码

B. Time

发现每次操作一定要先把最小值移动到边界上,然后就变成了一个规模为 $n-1$ 的子问题。
直接模拟就好了。
时间复杂度 $O(nlogn)$
代码

C. Cover

我们可以利用区间的包含关系建出一棵树,限制实际上就是每一条从根开始的链的节点数量不超过 $k$,考虑暴力 dp:设 $f_{i,j}$ 表示 $i$ 子树内到根选点最多的链的点数是 $j$,转移先合并子树,再考虑根对答案的贡献:
$$f_{i,j} = \max \{f_{i,j},f_{i,j-1}+a_i\}$$
然后优化有点神仙...我们考虑对每一个 $f_i$ 进行差分,那么发现这个差分序列 $g_i$ 一定是单调递减的(差分序列的意思是在原有的情况下选出最大的 $k=1$ 的情况)。我们的合并变成了直接按位相加,用根更新变成了在合适的位置插入 $a_i$。(对应了最优情况下差分表是递减的性质)
然后我们可以对于每个点开一个 set,长链剖分后直接暴力合并就可以了。
时间复杂度 $O(nlogn)$
代码

总结

T1 对于线段树的应用的理解还不是很到位。。其实某些结构在线段树上通过合并就能考虑到所有的情况。。比较神奇
T2 中间调了一会,要重点考虑有相同数的情况!(如果数据范围里没有提示估计我就挂了)
T3 有时候一种最优方案的性质(比如差分表单调递减) 可以变成构造这种最优方案的最优选择策略(每次新点加入到 set 的对应位置),感觉比较神奇
CSP.rp++


版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/948/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏