牛客练习赛115 解题报告 弱化版

牛客练习赛115 解题报告 详细的题解链接

https://blog.nowcoder.net/n/e725cfc01d7b4f6baa1e328a97a64dc9

这场太难了，所以只写了4题

A. 构造解

分组排序，把最大值放中间，然后按序放置其他组，对于每个组左右侧的方案为 m+1

因此总的方案数除了山峰的组，(组大小+1)的累乘

B. 二分贪心模拟/记忆化搜索

二分的时候，右侧区间大于等于左侧，因此贪心往右侧寻找。

还可以根据数据规模，n=100000，cnt=20，设计状态，用记忆化搜索，如果你没想到贪心的话。

C. 差分题

把这个式子抽象为 斜率

这题的核心是: 最大的斜率一定在相邻的元素中

假定 最大的斜率不是相邻元素，可以结合数形来反证

剩下的事情，就简单了。

D. dfn序应用题

因为涉及树上的祖父判定，所以很自然引入dfn时间序

一种思路是基于，抓换为操作序列（按时间），然后借助树状数组，来求解。

另一种思路是基于，启发式合并，需要名次树支持。