1896D
CF1896D Ones and Twos 题解
来自机房大佬 FFT 的简单解法。 思路 首先有个结论:如果 \(a\) 中存在一个子串的和为 \(x\) (\(x>2\)),那么也就一定存在一个子串之和为 \(x-2\)。怎么证明?其实和为 \(x\) 的子串有 \(3\) 种情况: \(\text{1}\dots \text{1}\) 两边都 ......
CF1896D Ones and Twos 题解
CF1896D 如果只有单次询问其实可以双指针,但是这个难以进行拓展。 考虑找点性质。 发现 \(a_i,v\in\{1,2\}\),从值域上下手。发现若存在和为 \(S\) 的方案,则一定有和为 \(S-2\) 的方案,因为可以直接 \(-2\) 或 \(-1-1\)。 然后就变为找最大的和为奇/ ......