ZR NOIP二十连测

Day 1

匹配

把命题加强一下，那么就是 \(n\) 个数里面选 \(n/2\) 个正的，\(n/2\) 个负的，求最大值，排序后贪心即可。

狼人

一个暴力 \(\mathcal O(n^3)\) 做法是对每一种颜色 \(x\)，令 \(b_x=\begin{cases}1, &a_i=x\\-1,&a_i\neq x\end{cases}\) 做一遍 \(\mathcal O(n^2)\) 背包，结合部分分能够拿到 \(70pts\) 的高分。

假设颜色 \(x\) 的数量是 \(c_x\)，那么背包的第二维不可能 \(>c_x\)，并且如果 \(<-c_x\) 那么一定没救，所以说有用值域其实是 \(\mathcal O(c_x)\) 的，调整一下 dp 上下界即可做到 \(\mathcal O(n\sum c_x)=\mathcal O(n^2)\)。