TZOJ 2703 Cow Digit Game(sg博弈)

描述

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.

输入

* Line 1: A single integer: G

* Lines 2..G+1: Line i+1 contains the single integer: N_i

输出

* Lines 1..G: Line i contains "YES" if Bessie can win game i, and "NO" otherwise.

样例输入

2
9
10

样例输出

YES
NO

提示

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.

题意

A和B在玩游戏,给一个数a,轮到A,可以把数变成a-最大的数,a-最小的非零数,B同理,谁把值变成0谁赢

题解

观察一下可以发现,只要知道a-最大的数的sg值和a-最小的非零数的sg值,再异或1就是答案

因为先手只可以选最大或最小,后面不管怎么拿都是定死了

代码

 #include<bits/stdc++.h>
using namespace std; int sg[],n,a,t,mx,mi;
void m(int x)
{
mx=-,mi=;
do{
t=x%;
if(t)mx=max(mx,t);
if(t)mi=min(mi,t);
x/=;
}while(x);
}
int main()
{
sg[]=;
for(int i=;i<=;i++)m(i),sg[i]=(sg[i-mx]^)|(sg[i-mi]^);
scanf("%d",&n);
while(n--)
{
scanf("%d",&a);
printf("%s\n",sg[a]?"YES":"NO");
}
return ;
}
上一篇:Html,Css,Javascript及其他的注释方法详解


下一篇:[noip模拟题]科技节 - 搜索 - 位运算优化