题目大意

爱丽丝和鲍勃玩一个石头游戏，有 $n$ 块石头，游戏分为三个阶段：

1. 声明阶段：进行 $n+1$ 次声明，每次声明给出两个石头选项
2. 选择阶段：克莱尔为每个声明选择一个选项，共 $2^{n+1}$ 种场景
3. 执行阶段：按克莱尔的选择拿石头，第一个无法拿石的玩家输

给定前 $k$ 次声明，求在双方最优策略下，爱丽丝和鲍勃各赢多少场景。

算法思路

核心观察

1. 图论建模：将游戏建模为图论问题，石头是节点，声明是边
2. 连通分量：游戏的胜负取决于连通分量的结构
3. 三种操作类型：
   • 类型0：在连通分量内形成环
   • 类型1：环与树连接
   • 类型2：两棵树合并

状态表示

使用整数划分来表示连通分量的分布状态。例如状态 [3,2,1] 表示有三个连通分量，大小分别为 3、2、1。

动态规划

定义 f[S] 表示在状态 $S$ 下，当前玩家能获得的最大优势值。

状态转移考虑三种操作：

// 类型0：形成环
f[id] = max(f[id], (w << (n-i+1)) - (nxt.F << (n-i)) - (f[idx[nxt.S]] << 1));

// 类型1：环与树连接  
f[id] = max(f[id], (w << (n-i+1)) - (nxt.F << (n-i)) - f[idx[nxt.S]]);

// 类型2：两棵树合并
f[id] = max(f[id], (w << (n-i+1)) - (nxt.F << (n-i)) - f[idx[nxt.S]]);

代码实现详解

状态生成

void dfs(int s, ll w, int x, vector<int> v) {
    idx[v] = cnt;                    // 给状态分配唯一编号
    sts[cnt] = v, val[cnt] = w;      // 记录状态和对应的乘积值
    isall[cnt] = (s == n);           // 标记是否使用了所有n个石头
    hvs[n - v.size()].push_back(cnt++); // 按剩余石头数分组
    
    // 递归生成所有整数划分
    for (int i = x; i + ps <= n; i++) {
        s = ps, w = pw, v = pv;
        while (s + i <= n) {
            v.push_back(i);          // 添加大小为i的组件
            s += i, w *= i;
            dfs(s, w, i + 1, v);     // 递归生成
        }
    }
}

三种操作的处理

// 类型0：在连通分量内形成环（移除大小为s的组件）
pair<ll, vector<int>> getnxt0(vector<int> v, int s) {
    ll tot = 1;
    for (auto &x : v) tot *= x;      // 计算当前状态的总场景数
    tot = tot / s * (s - 1) * 2;     // 更新场景数：移除环的影响
    
    // 从状态中移除大小为s的组件
    for (int i = 0; i < v.size(); i++)
        if (v[i] == s) {
            v.erase(v.begin() + i);
            break;
        }
    return make_pair(tot, v);
}

// 类型1：环与树连接
pair<ll, vector<int>> getnxt1(vector<int> v, int s) {
    ll tot = 1;
    for (auto &x : v) tot *= x;
    tot += tot / s * (s - 1);        // 场景数计算：环与树连接
    
    for (int i = 0; i < v.size(); i++)
        if (v[i] == s) {
            v.erase(v.begin() + i);
            break;
        }
    return make_pair(tot, v);
}

// 类型2：两棵树合并
pair<ll, vector<int>> getnxt2(vector<int> v, int sx, int sy) {
    ll tot = 1;
    for (auto &x : v) tot *= x;
    tot = tot * 2 - tot / sx - tot / sy; // 场景数计算：合并两棵树
    
    // 移除两个组件sx和sy
    for (int i = 0; i < v.size(); i++)
        if (v[i] == sx) {
            v.erase(v.begin() + i);
            break;
        }
    for (int i = 0; i < v.size(); i++)
        if (v[i] == sy) {
            v.erase(v.begin() + i);
            break;
        }
    
    // 添加合并后的新组件sx+sy
    for (int i = 0; i <= v.size(); i++)
        if (i == v.size() || v[i] > sx + sy) {
            v.insert(v.begin() + i, sx + sy);
            break;
        }
    return make_pair(tot, v);
}

主算法流程

int main() {
    // 1. 读入和预处理
    cin >> n >> m;
    dfs(0, 1, 1, vector<int> {});    // 生成所有整数划分状态
    
    // 2. 处理已知声明
    for (int i = 0; i < n; i++) fa[i] = i;  // 初始化并查集
    vector<int> cur(n, 1);           // 初始状态：n个大小为1的连通分量

    for (int i = 0; i < m; i++) {
        int x = p[i].F, y = p[i].S;
        
        // 特殊情况：形成环导致立即结束
        if ((iscyc[x] && iscyc[y]) || (getf(x) == getf(y) && iscyc[x])) {
            qwq[(i & 1) ^ 1] += val[idx[cur]] << (num + n - i + 1);
            cout << qwq[0] << " " << qwq[1] << '\n';
            return 0;
        }
        
        if (getf(x) == getf(y)) {
            // 类型0：在连通分量内形成环
            int sz = 0;
            for (int j = 0; j < n; j++)
                if (getf(j) == getf(x)) {
                    sz++;
                    iscyc[j] = true;  // 标记为包含环
                }
            auto v = getnxt0(cur, sz);
            qwq[(i & 1) ^ 1] += v.F << (num + n - i);
            num++;
            cur = v.S;
        } else {
            // 合并两个连通分量
            if (iscyc[y]) swap(x, y);
            // 更新并查集和环标记
            fa[getf(x)] = getf(y);
            
            if (iscyc[x]) {
                // 类型1：环与树连接
                auto v = getnxt1(cur, szy);
                qwq[(i & 1) ^ 1] += v.F << (num + n - i);
                cur = v.S;
            } else {
                // 类型2：两棵树合并  
                auto v = getnxt2(cur, szx, szy);
                qwq[(i & 1) ^ 1] += v.F << (num + n - i);
                cur = v.S;
            }
        }
    }
    
    // 3. 动态规划求解剩余游戏
    memset(f, -63, sizeof(f));
    f[0] = 0;  // 空状态的初始值
    
    // 从剩余石头多的情况开始DP
    for (int i = n - 1; i >= m; i--)
        for (auto &id : hvs[i]) {    // 遍历所有剩余i个石头的状态
            ll w = val[id];
            auto v = sts[id];
            
            // 尝试所有可能的移动
            for (int j = 0; j < v.size(); j++)
                if (j == 0 || v[j] != v[j - 1]) {  // 避免重复
                    // 类型0移动：形成环
                    auto nxt = getnxt0(v, v[j]);
                    f[id] = max(f[id], (w << (n - i + 1)) - (nxt.F << (n - i)) - (f[idx[nxt.S]] << 1));
                    
                    // 类型1移动：环与树连接
                    if (!isall[id]) {
                        auto nxt = getnxt1(v, v[j]);
                        f[id] = max(f[id], (w << (n - i + 1)) - (nxt.F << (n - i)) - f[idx[nxt.S]]);
                    }
                    
                    // 类型2移动：两棵树合并
                    for (int k = j + 1; k < v.size(); k++)
                        if (k == j + 1 || v[k] != v[k - 1]) {
                            auto nxt = getnxt2(v, v[j], v[k]);
                            f[id] = max(f[id], (w << (n - i + 1)) - (nxt.F << (n - i)) - f[idx[nxt.S]]);
                        }
                }
        }
    
    // 4. 计算并输出最终结果
    f[idx[cur]] <<= num;
    ll x = f[idx[cur]] + qwq[m & 1], y = (1ll << (n + 1)) - x;
    
    if (m & 1) swap(x, y);  // 根据最后一步的玩家调整结果
    cout << x << " " << y << '\n';
    return 0;
}

关键点解释

1. 状态表示：使用整数划分来压缩状态空间，避免状态爆炸
2. 场景计数：val[id] 存储每个状态对应的场景数乘积，通过位运算快速计算
3. 最优策略：DP状态 f[id] 表示当前玩家在状态 id 下的最大优势
4. 三种操作：对应图连通分量的三种变化情况，每种操作影响场景数和状态转移

复杂度分析

• 状态数：$n$ 的整数划分数，当 $n=35$ 时约为数千
• 时间复杂度：$O(\text{状态数} \times n^2)$
• 空间复杂度：$O(\text{状态数} \times n)$