- 第20场 （为了完整把前天的一部分粘贴过来了
- T1 秒了
- T2 我不行了，啥性质都分析出来了，就是没有想到把第 \(i\) 个物品合并放到第 \(i+1\) 里去，那我能说啥呢
- 见过的套路不够多加上当时的脑袋比较混沌，加上自己比较蠢没有想到可以这样子做，实际上我是想到了可以合并变成第 \(i+1\) 大的大小的但是我没有想到可以给它放到后面去处理，我是直接想用背包处理的，我太蠢了深刻反思
- T3 根号分治求拆分数
- 很天才的trick，之前从未见过/kx
- 考虑加入的数 \(x <= \sqrt{N}\)
- 那么直接背包，时间复杂度是 \(O(N \sqrt{N})\) 的
- \(x > \sqrt{N}\)
- 那么考虑它们加入的次数一定会小于等于 \(\sqrt{N}\) 故我们可以枚举次数，然后加入一个 \(\sqrt{N}\)，可以任意地把前面的数都加上一个数 \(c >= 0\)
- 甜菜！！！这样就是 \(O(N \sqrt{N})\) 的了
- 考虑怎么反悔，这里有两种方法
- 对于完全背包可以使用 退背包的操作
- 或者考虑容斥，如不能选 \(a_1, a_2, …… a_k\) 这几个数，则考虑选了几个违法的数（不能重复选）若是 \(x\) 个则系数为 \((-1)^x\) 用背包每次加数改为加上这个数的相反数即可
s[0] = 1;for (long long i = 1; i <= k; i++) {for (long long j = n; j >= a[i]; j--) {s[j] += (mod - s[j - a[i]]);s[j] %= mod;}} - T4
- 看了提示之后有了点思路
- 因为要左右两边都有比自己高的自己才能增高，所以可以得出最终序列的最大值等于原来序列的最大值
- 然后考虑最大值所在的位置 \(x\) （任意一个）则 \(i<x\) 的 \(i\) 都要是 \(1-i\) 的前缀最大值，任意一个 \(i > x\) 的 \(i\) 都要是后缀最大值
- 故我们可以确定每一个数所最终要变成的数
- 考虑从小往大提升这座山，如第一小的提升到次小或它们最终需要变成的数，这一定是不劣的因为它们在这个阶段无法成为别人提高的媒介
- 考虑我们维护一个集合表示最小的，且需要加到次小的数的集合，我们考虑 \(pl\) 为这些数最靠左的节点，\(pr\) 为这些数最靠右的节点，\(mxll\) 为 \(pl\) 左边大于 \(pl\) 的最小的数，\(mxlr\) 为 \(pl\) 右边大于 \(pl\) 的最小的数，\(mxrl\) 为 \(pr\) 左边大于 \(pr\) 的最小的数，\(mxrr\) 为 \(pr\) 右边大于 \(pr\) 的最小的数。
- 我们肯定是更希望是 \((x+1,x,x+1)\) 这种形式的出现次数多，我们会想到可以把 \(pl\) ，\(pr\) 的值加1然后再让序列中间的元素加1，重复这个步骤直到它们和次小的数一样大
- 考虑这样做一次的答案就是 \(\min(mxlr,mxrl) + mxll + mxrr\) 可以发现这样一定是最优的，因为 \(mxll\) 和 \(mxrr\) 是一定要选的，\(\min(mxlr,mxrl)\) 是全局大于 \(pl,pr\) 的最小的值是最优的选择方案，然后计算一下其他的贡献即可
- 然后直接上主席树求解即可。
- 感觉很简单啊，还是不要惧怕题目，在NOIP考场上也要做到每道题都分配一些思考时间而不是碰到T4下意识觉得自己做不出来
