Palindrome Game

题意

有一堆 $S$ 个石子，Bessie 先手。

每次行动必须取走一个正整数回文数个石子。如果轮到某头牛行动时没有石子可取，那么这头牛输。

给定若干个很大的 $S$ ，判断双方最优时谁会获胜。

思路

暴力想法

小数据可以用博弈 DP。

设 win[s] 表示还剩 s 个石子时，当前行动者是否必胜。如果存在一个回文数 p，满足 win[s-p] = false，那么 win[s] = true。

这个暴力适合小数据和对拍：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:45
 * update_at: 2026-07-11 12:46
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXS = 100000;

int t;
int query_value[20];
bool is_pal[MAXS + 5];
bool win_pos[MAXS + 5]; // win_pos[i] 表示还剩 i 个石子时先手是否必胜

bool check_pal(int x) {
    string s = to_string(x);
    int l = 0;
    int r = (int)s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

void build_dp(int max_s) {
    for (int i = 1; i <= max_s; i++) {
        is_pal[i] = check_pal(i);
    }

    win_pos[0] = false;
    for (int i = 1; i <= max_s; i++) {
        win_pos[i] = false;
        for (int take = 1; take <= i; take++) {
            if (is_pal[take] && !win_pos[i - take]) {
                win_pos[i] = true;
                break;
            }
        }
    }
}

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

    cin >> t;
    int max_s = 0;
    for (int i = 1; i <= t; i++) {
        string s;
        cin >> s;
        query_value[i] = stoi(s);
        if (max_s < query_value[i]) {
            max_s = query_value[i];
        }
    }

    build_dp(max_s);

    for (int i = 1; i <= t; i++) {
        cout << (win_pos[query_value[i]] ? 'B' : 'E') << '\n';
    }

    return 0;
}

但题目中的 $S$ 可能非常长，不能转成整数做 DP。

关键性质

$1,2,\ldots,9$ 都是回文数。

如果 $S$ 不是 $10$ 的倍数，设它的末位是 d，其中 $1 \dots 9$ 。 Bessie 可以取走 d 个石子，把剩余石子数变成 $10$ 的倍数。

而任意正整数回文数都不可能是 $10$ 的倍数。因为如果末位是 0，回文要求首位也是 0，这会产生前导零，不合法。

所以：

text

1
210 的倍数：必败
不是 10 的倍数：必胜

最终判断

由于 $S$ 很大，直接按字符串读入。

只看最后一个字符：

是 0，输出 E；
否则输出 B。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:45
 * update_at: 2026-07-11 12:46
 */
#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        if (s[(int)s.size() - 1] == '0') {
            cout << "E\n";
        } else {
            cout << "B\n";
        }
    }

    return 0;
}

复杂度

每组数据读入字符串需要 $O(|S|)$ 。判断末位是 $O(1)$ 。

空间复杂度 $O(|S|)$ 。

总结

这题的关键是把取回文数的游戏转化成模 $10$ 的必胜必败判断。

非 $10$ 的倍数可以一步走到 $10$ 的倍数，而 $10$ 的倍数无法一步走到另一个 $10$ 的倍数。因此只需要检查输入字符串的最后一位。

目录

题意

思路

暴力想法

关键性质

最终判断

代码

复杂度

总结