进阶数学算法-取石子(ICPC 亚洲区域赛（成都） 2011)

题目-取石子

问题分析

一共两个操作

• 从某堆中取走一个石子
• 合并某两堆石子

首先考虑简单情况, 我们假设所有堆石子数量都$>1$, 假设堆的数量是$x$, 石子的总数是$y$

那么令
$$b=x+y-1$$
当$b$是奇数先手必胜, $b$是偶数先手必败, 以下是证明过程

需要证明两点

1. 奇数状态一定存在一个偶数的后继状态
2. 偶数状态无论如何操作只能走到奇数状态

首先是奇数状态的情况, 因为$b$是奇数, 那么$x$是偶数, $y$也是偶数

• 如果合并了某两堆, 堆数减少$1$, $b$变为偶数
• 如果拿走了某个石子, 石子数减少$1$, $b$变为偶数

因此第一点成立

再证明偶数状态的情况, $b$是偶数

• $x$如果是奇数, $y$是偶数
• $x$如果是偶数, $y$是奇数

首先看$x$是奇数情况, 假设合并某两堆, 堆数量减少$1$, $b$变为奇数, 假设拿走一个石子, $b$也变为奇数

再看$x$是偶数情况, 假设合并某两堆, 堆数量减少$1$, $b$变为奇数, 假设拿走一个石子, $b$也变为奇数

因此第二点也成立

因此, 简单情况下, $b=x+y-1$如果是奇数, 先手必胜

但是存在堆的石子数量是$1$的情况, 我们将该情况设为$a$, 因为无法从一个情况推断出另一个情况, 可以将两种情况一并考虑

定义状态$f(a,b)$表示: 堆的石子个数为$1$的堆的数量$a$, 堆的石子数量$>1$的$x+y-1=b$的所有情况

$a\le 50,b\le 50\times 1000$, 总的状态数量$2.5\times 10^6$, 状态转移只有$5$种情况

• $a$集合内部和并两堆, $f(a-2,b+3)$(合并完之后多了一堆, 并且多了两个石子)
• $a$集合取出一个石子, $f(a-1,b)$
• $b$集合内部合并两堆, $f(a,b-1)$
• $b$集合取出一个石子, $f(a,b-1)$
• $a$集合和$b$集合各取出一堆, 合并, $f(a-1,b+1)$

算法步骤

记忆化搜索实现上述状态转移, 算法时间复杂度$O(NM)$

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 55, M = 50010;

int T, n;
int f[N][M];

int dp(int a, int b) {
   
    int &t = f[a][b];

    if (t != -1) return t;
    if (a == 0) return b & 1;
    // b = 1 + 1 - 1, 也就是只有一堆石子并且只有一个石子
    if (b == 1) return dp(a + 1, 0);

    if (a && !dp(a - 1, b)) return t = 1;
    if (b && !dp(a, b - 1)) return t = 1;
    // a里面和并两堆石子, 当b = 0的时候 + 2, 当b不等于0的时候 + 3
    if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return t = 1;
    // 只有a, b两种情况都有石子情况下, 才能从a中选一堆合并到b中
    if (a && b && !dp(a - 1, b + 1)) return t = 1;

    return t = 0;
}

void solve() {
   
    cin >> n;
    int a = 0, b = 0;
    for (int i = 0; i < n; ++i) {
   
        int val;
        cin >> val;
        if (val == 1) a++;
        // b是 堆数 + 石子数 - 1
        else b += b ? val + 1 : val;
    }

    int ans = dp(a, b);
    cout << (ans ? "YES" : "NO") << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(f, -1, sizeof f);

    cin >> T;
    while (T--) solve();

    return 0;
}