首页 > 代码库 > BZOJ3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

BZOJ3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

2024-07-25 15:28:24   218人阅读

3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 47  Solved: 32
[Submit][Status]

Description

    贝茜和约翰在玩一个数字游戏．贝茜需要你帮助她．
    游戏一共进行了G(1≤G≤100)场．第i场游戏开始于一个正整数Ni(l≤Ni≤1,000,000)．游
戏规则是这样的：双方轮流操作，将当前的数字减去一个数，这个数可以是当前数字的最大数码，也可以是最小的非0数码．比如当前的数是3014，操作者可以减去1变成3013，也可以减去4变成3010．若干次操作之后，这个数字会变成0．这时候不能再操作的一方为输家．    贝茜总是先开始操作．如果贝茜和约翰都足够聪明，执行最好的策略．请你计算最后的赢家．
    比如，一场游戏开始于13.贝茜将13减去3变成10．约翰只能将10减去1变成9．贝茜再将9减去9变成0．最后贝茜赢．

Input

    第1行输入一个整数G，之后G行一行输入一个Ni．

Output

 
    对于每一场游戏，若贝茜能赢，则输出一行“YES”，否则输幽一行“NO”

Sample Input

2
9
10

Sample Output

YES
NO

HINT

 

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

Silver

题解：

把sg函数都预处理出来。。。

代码：

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1000000+514 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29     return x*f;30 }31 bool f[maxn];32 int main()33 {34     freopen("input.txt","r",stdin);35     freopen("output.txt","w",stdout);36     f[0]=0;37     for1(i,maxn)38     {39       int x=i,t,mi=10,mx=0;40       while(x){t=x%10;mx=max(mx,t);if(t)mi=min(mi,t);x/=10;}41       if(!f[i-mi]||!f[i-mx])f[i]=1;42     }43     int cs=read();44     while(cs--)45      if(f[read()])printf("YES\n");else printf("NO\n");46     return 0;47 }
View Code

 

 

BZOJ3404: [Usaco2009 Open]Cow Digit Game又见数字游戏


联系
我们