正睿 NOIP 二十连测
C
\(n, q, a_i \le 300\)。
这种题一般都要发现一些性质（不变量）才能做。这个题的是将 \(a\) 分成两组 \(S1, S2\) 的总和。
首先如果可以分成两组使得 \(s1 = s2\)，那么后手必胜。
\(s1 = s2 = 0\) 显然成立。
否则先手选择了 \(S1\) 的元素，后手就选一个 \(S2\) 的元素，\(s1, s2\) 都减去了 \(\min(a_i, a_j)\)。
然后猜剩下的就是先手必胜了。
若 \(s1 < s2\)，后手肯定要想办法让 \(s1\) 和 \(s2\) 变得相同。
设操作了 \(a, b(a \le b)\) 两个数组，那么操作相当于在原序列中删去 \(a, b\) 加入 \(b - a\)。
暴力枚举 \(a, b, b - a\) 在哪个集合内讨论下就行了。（可钦定 \(a\) 在 \(S1\)）
接来问题就简单了，令 \(dp_{i, s}\) 表示前 \(i\) 个数能否凑出 \(s\)，暴力转移即可。时间复杂度：\(O(qnV^2)\)。
使用 bitset 优化达到 \(O(\frac{qnV^2}{w})\) 的复杂度。
这种题就是要找性质，感觉有点碰运气的成分。