RainAir
My OI Blog
RainAir
JZOJ 2019.11.02 总结

赛时

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++

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/948
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

JZOJ 2019.11.02 总结
赛时 T1 一看暴力分是之前做过的原题,所以就粘写完了 $O(n^2logn)$ 的暴力, T2 想了想,发现每次一定要把最小值移动到左边或右边,然后可以递归成子问题去做了 T3 建出来树之后只会暴…
扫描二维码继续阅读
2019-11-03
标签
近期评论