正睿 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})\) 的復雜度。

這種題就是要找性質，感覺有點碰運氣的成分。