ARC150F

ZSH_ZSH · 2023-10-09 11:11:00 · 题解

我是乱搞哥。

对于一个序列，显然是把它贪心地放进 a 里。一个朴素的想法，是对于 a 中的下标 i，设 f_i 表示所有以 i 结尾的序列中 sum 最小的那个序列的 sum。

显然 f_i = a_i + \min_{lst_{i} \leq j < i} f_j。其中 lst_i 是 a_i 上一次出现的位置。答案就是最大的 i 满足 f_i \leq s。

我们声称 f 数组满足很好的性质。具体地，当 i 很大的时候，f_{i+n} - f_i = f_i - f_{i-n}。不太会证，但是一看就很对！（如果有老哥会证可以评论区踢我一下）。

所以我们可以取一个阈值 B，暴力计算前 Bn 个 f。然后就可以模 n 单独做了。

发现 B \geq 3 的时候，都可以过掉这个题。