牛客练习赛115 解题报告 详细的题解链接
https://blog.nowcoder.net/n/e725cfc01d7b4f6baa1e328a97a64dc9
这场太难了，所以只写了4题
A. 构造解
分组排序，把最大值放中间，然后按序放置其他组，对于每个组左右侧的方案为 m+1
因此总的方案数除了山峰的组，(组大小+1)的累乘
B. 二分贪心模拟/记忆化搜索
二分的时候，右侧区间大于等于左侧，因此贪心往右侧寻找。
还可以根据数据规模，n=100000，cnt=20，设计状态，用记忆化搜索，如果你没想到贪心的话。
C. 差分题
把这个式子抽象为 斜率
这题的核心是: 最大的斜率一定在相邻的元素中
假定 最大的斜率不是相邻元素，可以结合数形来反证
剩下的事情，就简单了。
D. dfn序应用题
因为涉及树上的祖父判定，所以很自然引入dfn时间序
一种思路是基于，抓换为操作序列（按时间），然后借助树状数组，来求解。
另一种思路是基于，启发式合并，需要名次树支持。
全部评论
(1) 回帖