【BZOJ】【3404】【USACO2009 Open】Cow Digit Game又见数字游戏

博弈论

  Orz ZYF

  从前往后递推……反正最大才10^6,完全可以暴力预处理每个数的状态是必胜还是必败(反正才两个后继状态),然后O(1)查询……我是SB

 /**************************************************************
Problem: 3404
User: Tunix
Language: C++
Result: Accepted
Time:880 ms
Memory:5180 kb
****************************************************************/ //BZOJ 3404
#include<cstdio>
#include<iostream>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;++i)
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e6+,INF=~0u>>;
/*******************template********************/
int f[N+];
int main(){
f[]=;
F(i,,N){
int x=i,mx=,mn=,t=;
while(x){ t=x%; mx=max(mx,t); if (t)mn=min(mn,t); x/=;}
if (!f[i-mx] || !f[i-mn]) f[i]=;
}
int T=getint();
while(T--)
printf( f[getint()] ? "YES\n" : "NO\n");
return ;
}
上一篇:spring 数据校验之Hibernate validation


下一篇:JavaScript算法描述(一)