观前须知

Sugar_Cube的博客园主页

背景介绍

本文记录了笔者在刷题或比赛中运用到的一些做题思路
可以适当参考

正文

Luogu P2048 超级钢琴

首先显然有 \(\mathcal {O}(n^2)\) 的暴力枚举每个子段，然后选择其中前k大的
那么可以发现有贪心策略：
选择k次最大值
那么考虑怎样求最大值
想到可以枚举每个起始位置，想办法计算从该位置开始符合要求的字段最大值
将字段长度符合要求转换为终止位置在区间内
由于连续，记前缀和 \(sum_i\)
则对于一个三元组 \((lx,l,r)\) 表示从 \(lx\) 起始，合法终止位置在 \([l,r]\) 区间内
它的最优答案是 \(max\{sum_t-sum_{lx-1} | t\in [l,r] \}\)
即 \(max\{sum_t | t\in [l,r] \} – sum_{lx-1}\)
发现求最大的 \(sum_t\) 是一个RMQ问题
注意到，一个起始位置算完后，仍然有别的终止位置可以使用
则分裂原三元组为 \((lx,l,t-1)\) 与 \((lx,t+1,r)\)
并将新的三元组放到堆中继续维护最大值

细节：
为了计算 \(t\) 要在st表中维护最大值对应的下标
注意判新的三元组的合法性

一句话思路：
暴力->贪心->求最大值->计算子段和->RMQ->分裂三元组用堆维护

P2680 【NOIP2015 提高组】 运输计划

首先容易想到可二分
提前预处理出每条道路的权值并排序
因为路径问题顺便预处理一个lca
检查当前的答案是否合法
对于原本权值就小于等于mid的道路显然合法
对于所有大于mid的道路，必须有一条边能被所有路径覆盖，且最长道路权值-这条边的权值小于等于mid
也就转换成了
路径覆盖问题
那么树上差分显然可做

细节：
因为某ybtoj卡了一个点T，所以学习了 \(\mathcal {O}(n\log n) – \mathcal {O}(1)\) 的lca求法
但是仍然被卡住了
最后在二分的时候记忆化一下冲过去了

一句话思路：
二分->路径覆盖问题->树上差分