思路与算法

每根巧克力以盒内负长度、桌上正长度、吃完0表示。删除0并排序规范化状态，用记忆化递归求胜负；枚举非空盒内子集转上桌，或桌上一根减少到任意更短非负长度。若某后继必败则当前必胜，否则当前必败。空状态必败，按约定必胜输出NO、必败输出YES。

正确性说明

势函数为每根盒内2L+1、桌上2L之和。取上桌每根减少1，吃掉正长度至少减少2，所以所有操作严格降低非负势，状态图无环。终局无后继而必败；对势归纳，存在必败后继即可强制给对手败局，全部后继必胜则无法获胜，递归判定正确。相同位置类别和长度的巧克力互换不影响合法动作，排序仅去掉标号对称，不合并不同游戏状态。

复杂度

本地N≤5,L≤6，每根13种状态；规范化状态数至多C(17,5)=6188（补0到5根），每状态至多2^5−1+5·6个动作。排序至多5项为常数，总时间O(S(2^N+NL)NlogN)，空间O(SN+NL)，S≤6188；记忆表跨10局复用。

易错点

取上桌和吃不能同一回合完成；可吃完一根，盒内不能直接吃。YES表示先手输，NO表示先手赢。全部初始在盒内，未出现桌上历史状态；本地小域新教学样例已公开更换，不能拿矛盾原9行结果作金答案。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, bool> memo;
bool win(vector<int> a) {
    a.erase(remove(a.begin(), a.end(), 0), a.end());
    sort(a.begin(), a.end());
    if (a.empty())
        return false;
    int key = 1;
    for (int x : a)
        key = key * 13 + x + 6;
    auto it = memo.find(key);
    if (it != memo.end())
        return it->second;
    vector<int> box;
    for (int i = 0; i < (int)a.size(); i++)
        if (a[i] < 0)
            box.push_back(i);
    for (int mask = 1; mask < (1 << (int)box.size()); mask++) {
        vector<int> b = a;
        for (int j = 0; j < (int)box.size(); j++)
            if (mask >> j & 1)
                b[box[j]] = -b[box[j]];
        if (!win(b))
            return memo[key] = true;
    }
    for (int i = 0; i < (int)a.size(); i++)
        if (a[i] > 0)
            for (int left = 0; left < a[i]; left++) {
                vector<int> b = a;
                b[i] = left;
                if (!win(b))
                    return memo[key] = true;
            }
    return memo[key] = false;
}
int main() {
    for (int t = 0; t < 10; t++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int &x : a) {
            cin >> x;
            x = -x;
        }
        cout << (win(a) ? "NO" : "YES") << '\n';
    }
}