P10187 [USACO24FEB] Palindrome Game B 题解

cff_0102 · 2024-02-29 00:16:52 · 题解

不难发现所有整除 10，即以 0 结尾的正整数都不是回文数。

因为 1,2,3,4,5,6,7,8,9 都是回文数，而 10 不是，所以当 n\le9 时先手必胜，而 n=10 时先手必输。

假设 x 整除 10，且已知对于所有的 n\le x，当 n 整除 10 时先手输，否则先手赢。显然，x=10 时满足条件。接下来证明：对于任意的 x，当 x 满足条件时，x+10 也满足条件。

• 当 x<n<x+10 时，因为 1,2,3,4,5,6,7,8,9 都是回文数，所以先手可以取走任意的在 1 到 9 之间的数量的石子。此时先手必能一次将 n 变为 x。而根据假设，x 整除 10，是必输局面。所以当 x<n<x+10 时，先手可以取一次将局面变成必输局面，接下来后手怎么取都会输，所以先手赢。
• 当 n=x+10 时，因为根据假设，所有小于 n 的不整除 10 的数是必胜的，那么先手要是取完之后剩下的 n 不整除 10，后手就会有必胜策略，先手就输了。然而，因为所有整除 10 的正整数都不是回文数，所以先手不可能取走一个整除 10 的数，从而剩下的局面就必然不整除 10。因此，此时先手是必输的。

现在就成功证明了“若 x 整除 10，且对于所有的 n\le x，当 n 整除 10 时先手输，否则先手赢，那么此时对于所有的 n\le x+10，当 n 整除 10 时先手输，否则先手赢”。而我们又知道 x=10 时满足条件，所以所有的 x 都满足条件，所以只要 n 整除 10 就先手输，否则先手赢。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;while(t--){
        string s;cin>>s;
        if(s.back()=='0')cout<<"E\n";
        else cout<<"B\n";
    } 
    return 0;
}