OI题解｜おはよう学弟

浙理工2023新生赛｜おはよう学弟

---

🚀 题目浏览

【题目描述】

小 A 和小 B 正在玩一个游戏，游戏规则如下：

盒子中初始有 $n$ 个小球，两人轮流从中取出小球。若在当前回合开始时，有 $a$ 个小球，令 $a$ 在十进制表示下每位数字和为 $x$，则当前回合的玩家可以取出小球的个数在 $1$ 到 $\min(a, x)$ 之间。若当前回合的玩家进行操作后盒为空，则此玩家胜利。例如，当前盒

中有 $365$ 个小球，则能够被取出 $1$ 到 $14$ ($14 = 3 + 6 + 5$) 之间个数的小球。

由于比赛的奖品是印有 “おはよう学妹” 字样的限量款 T 恤，小 A 和小 B 非常想赢得这场比赛，所以他们都会做出对自己最优的操作。

现给出盒中初始小球的个数 $n$，请你预测谁能赢下这场惊险的比赛，小 A 先手进行操作。

【输入】

输入第一行包含一个正整数 $T$ $(1 \leq T \leq 10^6)$，代表测试组数。

随后 $T$ 行，每行包含一个正整数 $n$ $(1 \leq n \leq 10^6)$，代表盒中初始的小球个数。

【输出】

输出 $T$ 行，其中第 $i$ 行代表第 $i$ 个测试的胜方，如果是小 A 则输出 A，如果是小 B 胜出则输出 B。

【输入样例】

2
1331
70

【输出样例】

A
B

【原题链接】

https://acm.zstu.edu.cn/problem.php?id=4870

---

☘️ 题解分析

简单博弈

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int a[N], s[N], n;

int d(int x) {
    string str = to_string(x);
    int res = 0;
    for (int i = 0; i < str.size(); i++) {
        res += str[i] - '0';
    }
    return res;
}

int main() {
    for (int i = 1; i <= 9; i++) {
        a[i] = 1;
        s[i] += s[i - 1] + a[i];
    }

    for (int i = 10; i <= 1e6; i++) {
        int t = min(i, d(i));
        if (s[i - 1] - s[i - t - 1] == t)
            a[i] = 0;
        else
            a[i] = 1;
        s[i] += s[i - 1] + a[i];
    }

    int _ = 1;
    scanf("%d", &_);
    while (_--) {
        scanf("%d", &n);
        if (a[n]) printf("A\n");
        else printf("B\n");
    }

    return 0;
}