Palindrome Game (USACO Bronze 2024 February)

题目要求我们判断B是否存在必胜策略，是一个博弈论game theory的题目。

B先行，每次B或E都可以拿走回文数颗石子，轮到时石子数为0的人输。

青铜组的博弈论题目不会难，所以我们可以努力去找规律，此题考查一定的思维能力，没想出来前可能会觉得复杂。但要相信game theory题目坚持找规律都能找到，所以不要放弃。

我们一般从小的数往大的找，看是否有明显的规律。

• 1-9都是回文数，所以如果开始时是1-9，则B胜。
• 10不是回文数，B取任何数之后就变成回文数，E直接拿完，所以B负。
• 11是回文数，B胜。
• 12不是回文数，B有必胜办法吗？答案是有的，B取走2个，变成10个就回到了上面的E必负的情况，所以取2个是B的必胜走法。
• 不仅如此，11-19都可以这么办，B取走个位数，变成10个石子后，E都必败。
• 这个办法继续推广，就会发现，只要个位是0的数，都不是回文数，所以当石头数个位是0时，取任何回文数，都会变成个位不是0。而这时对手将个位数取走，就又回到个位为0。 这样走下去，我们看到个位为0的情况，是必负情况。
• 继续也就容易看到，个位非0的情况，是必胜的。因为只要取走个位数，就成为对手必败的个位为0的情况。

所以答案非常简单，如果个位数为0，输出"E"，否则输出"B"。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T;
char s[100005];
 
int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%s", s);
        int n = strlen(s);
        if (s[n-1] == '0') {
            printf("E\n");
        } else {
            printf("B\n");
        }
    }
 
    return 0;
}