USACO09OPEN Cow Digit Game

题目地址

题解

很标准的博弈论递推。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
bool sg[1000005];
void init(){
    sg[0]=0;
    int bit[9]={0},maxi,mini,len=1;
    for(int i=1;i<=1000000;i++){
        bit[0]++;
        for(int j=0;bit[j]==10&&j<len;j++)
            bit[j]=0,bit[j+1]++;
        if(bit[len])len++;
        mini=10,maxi=0;
        for(int j=0;j<len;j++){
            if(bit[j]>maxi)maxi=bit[j];
            if(bit[j]<mini&&bit[j])mini=bit[j];
        }
        if(!sg[i-maxi]||!sg[i-mini])sg[i]=1;
    }
}
void solve(){
    int T=read(),n;
    while(T--)
        n=read(),printf("%s\n",sg[n]?"YES":"NO");
}
int main(){
    init();
    solve();
    return 0;
}