题解：AT_arc210_e [ARC210E] Subset Sum Gaps

AKCoder · 2026-10-20 15:18:26 · 题解

题意：求所有满足 A 的子序列 S，使得 S_i \times 1.01 \le S_{i+1}。

首先考虑 n \le 20 的情况，直接 DFS 计算答案，或者每次扩一倍数组排序计算。

直接做是 O(2^n)，考虑如何排除不合法的状态。

由于最后会有一段段满足，所以定义一个三元组 (l,r,x) 表示区间 [l,r] 只有一个答案 x，显然最后的答案就是把所有的 x 加起来。

显然可以在排除数组的时候统计每一个答案，如果下一个的头和这一个的尾相同，就可以新开，否则更新更大的答案。

由于最后只会保留 1.01 \times S_i \le S_{i+1}，这样肯定不会很多，大概只有 O(\log_{1.01}A)，据说可以过。

注意开 long long。