CF专项训练

sad_lin / 2024-11-11 / 原文

虽然 CF 在洛谷上已死，但是有好题的话我肯定是要记录一下的啊！！!

Maximum Subsequence

很厉害的一道题，提醒我们看到数据范围非常小无非就是高复杂度的 dp 和搜索，但当dp不利于操作时就考虑搜索，搜索不仅可以考虑记忆化剪枝，还可以考虑双端搜索减少复杂度。

上面就是这题的大体思路，因为我们要用取模操作所以无非用 dp 做，考虑搜索，将数组分为前后两段，分别进行搜索，此时我们想到再对两段进行组合配对不就可以了吗，但是这样的话复杂度完全没降下去。

这时我们考虑贪心，我们要想到有这么一个性质，对于其中一个数组中的数 $q_i$ 他在 $p$ 中进行组合时在不超过 $m$ 的情况下时可以可以找到一个最大的不超过 $m$ 的 $p_i$，这比选所有小于 $p_i$ 都更优，当我们选择组合超过 $m$ 时也选择，那用最大 $q_i +$ 最大不超过也是更优的，所以我们可以排序后双指针或者二分查找即可。

总结：读题后看数据范围推测算法复杂度，搜索多考虑性质剪枝。

Yet Another Minimization Problem

不是很寻常的公式题，这种题只要操作不是很复杂都可以优先拆开。

\[\sum_{i=1}^n \sum_{j=i+1}^n{(x_i+x_j)^2} \]

\[=\sum_{i=1}^n \sum_{j=i+1}^n{x_i^2+2x_ix_j+x_j^2} \]

\[=(n-1)\sum_{i=1}^n{x_i^2}+2\sum_{i=1}^n \sum_{j=i+1}^n{x_ix_j} \]

拆到这我们现放一放，先再看一个式子，我们对他展开。

\[(\sum_{i=1}^n{x_i})^2 \]

\[=x_1^2+x_2^2+\cdots+x_n^2+2x_1x_2+2x_1x_3+\cdots+2x_1x_n+2x_2x_3+\cdots+2x_{n-1}x_n \]

\[=\sum_{i=1}^n{x_i^2}+2\sum_{i=1}^n \sum_{j=i+1}^n{x_ix_j} \]

到这我们发现这两个式子是几乎是等价的，只有前面的平方和不同，现在我们的目的就是为了求平方和与和的平方最小，因为前者是个常量不管他，我们需要去求和。

我们如果确定了 $a$ 序列的总和，那 $b$ 的总和我们就知道了，看到 $n$ 很小，和的总值域也很小，所以我们直接背包，设 $f[i][sum]$ 表示选了前 $i$ 个数总和为 $sum$ 的这个 $sum$ 值时我选了几个数得到的（应该这么形容，大概理解下），然后我们可以对 $sum$ 从 $f[i-1][sum-a[i]]+1$ 转移也可以从 $f[i-1][sum-b[i]]+1$ 转移过来，最后哪个值是由选择n个数得到的对那个 $sum$ 求值，最后的答案就是：$(n-2)\sum_{i=1}^n{x_i^2}+sum_a^2+(sum-sum_a)^2$