7 月 30 日模拟赛总结
A. 建筑升级
期望得分：100pts
实际得分：100pts
时间：40min
签到题都做这么久。。。依旧是没有想清楚到底要写什么才能维护需要的东西
B. 快速蜗蜗变换
期望得分：100pts
实际得分：20pts
时间：1h 35min
挂分原因：少判断了一种情况（拍子写挂了说是）
开始想的东西歪的离谱，把情况复杂化了好多，后来重新理了思路一下想明白了。最后写了个拍子结果数据生成器写挂了，恐怖的是平常都会检查生成数据合不合法，这次竟然没有去检查。
C. 互不相同
期望得分：9pts
实际得分：9pts
时间：剩余全部
硬是没有想到区间的两个端点之间的数必须两两不同，赛时想了一堆毫无意义的东西，连这么简单的性质都没发现。
D. 运货
期望得分：0pts
实际得分：0pts
看了一眼不会就没想过了
实际上通过率比 C 高一点，暴力也更多分，真是亏嘛。
Solution1：
发现如果 dp 的话从前面转移具有后效性，那么可以选择从后面往前转移
设 \(f_{i, j}\) 表示考虑后面 \(i\) 个物品，选择 \(j\) 个物品的最小负载。那么有转移 \(f_{i, j} = \min(f_{i + 1, j}, f_{i + 1, j - 1} + w_i)\)，那么 \(n^2\) 做法就出来了。这个可以用平衡树维护
Solution2：
ylx 的神仙做法。首先有结论：当 \(k\) 从大到小时，删掉的数相较于 \(k + 1\)，只删掉了一个。删掉的这个数的充要条件显然是：\(w_i\) 大于 \(i\) 之后选的 \(w_j\) 的和。注意到可选的 \(i\) 只有 \(log n\) 个，那么直接枚举删掉的最大的数，用线段树维护修改即可。好像是可以 \(log n\) 的，但是暂时还不会