20251107

· · 个人记录

T1

考试开始想了半个小时，后面又追加了半个多小时，但还是没想出来。

AI题解没看懂，用户题解yyds。

说实话，在要求最高位最大的时候从低位到高位枚举不容易想到，因为高位的价值远大于低位。

但题解使用一种类似反悔的做法，在可以加入高位的时候，把低位的那些反悔掉（从堆里面清出去），这是不常见的。

T2

\max_{1 \le l \le p \le r \le n} {\sum_{i=l}^{r}a_i} \rightarrow \max_{p \le r \le n} {\sum_{i=1}^{r}a_i} - \min_{1 \le l < p} {\sum_{i=1}^{l}a_i}

感觉这个trick会很有用，就写这了。

a_i-k \times b_i \rightarrow y=-b_ix+a

这个trick可以想到李超线段树，毕竟都有直线了。

这样这道题就变成了李超线段树的模板题。离线下来，扫一遍前缀，扫一遍后缀就做完了。

写了1h,调了0.5h。李超线段树本身没错，前面的坐标轴平移写错了。

T3

被 CF *3100 吓哭了

观察到测试点8专门给个 n \le 2000,m \le 20 肯定跟 2^m 有点关系,就想到状压了。

发现按照剩余时间可能能多打点表创更多数据。就写打表程序。

思路并不复杂，细节多得要死，写了1h才写完。一测样例错了。

这时候时间不太多了，赶紧去补 T1 暴力。然后T1暴力 \dfrac{2^n\times n^2}{8} 没创过 n \le 20。但是没有更多时间了。我赶紧回来调代码，无果。最后把错的表拼了个样例交上去了。

我是不是该先写个 O(2^{nm}) 来着？

T4

发现操作2与【单调队列/滑动窗口】有大大的联系。思考数据结构维护单调队列，偏到哪里去了都不知道。

题解只看懂 O(n\log^2 n)，单 \log 正解神秘。