Description
Bessie is playing a number game against Farmer John, and she wants you to help her achieve victory.
Game i starts with an integer N_i (1 <= N_i <= 1,000,000). Bessie goes first, and then the two players alternate turns. On each turn, a player can subtract either the largest digit or the smallest non-zero digit from the current number to obtain a new number. For example, from 3014 we may subtract either 1 or 4 to obtain either 3013 or 3010, respectively. The game continues until the number becomes 0, at which point the last player to have taken a turn is the winner.
Bessie and FJ play G (1 <= G <= 100) games. Determine, for each game, whether Bessie or FJ will win, assuming that both play perfectly (that is, on each turn, if the current player has a move that will guarantee his or her win, he or she will take it).
Consider a sample game where N_i = 13. Bessie goes first and takes 3, leaving 10. FJ is forced to take 1, leaving 9. Bessie takes the remainder and wins the game.
Input
* Line 1: A single integer: G
* Lines 2..G+1: Line i+1 contains the single integer: N_i
Output
* Lines 1..G: Line i contains "YES" if Bessie can win game i, and "NO" otherwise.
Sample Input
Sample Output
Hint
OUTPUT DETAILS:
For the first game, Bessie simply takes the number 9 and wins. For the second game, Bessie must take 1 (since she cannot take 0), and then FJ can win by taking 9.
Source
简单的博弈，sg函数
把一个数减去这个数非0的最大值或者最小值，分析其必胜
#include <stdio.h> #include <algorithm> using namespace std; const int N=1e6+10; int sg[N]; int main(){ for(int i=1;i<=1e6;i++){ int ma=0,mi=9,t=i; while(t){ int b=t%10; if(b){ ma=max(b,ma); mi=min(b,mi);} t/=10; } sg[i]=(sg[i-ma]&sg[i-mi])^1; } int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); printf("%s",sg[n]?"YES\n":"NO\n"); } return 0;}
原文：http://www.cnblogs.com/BobHuang/p/7113372.html