题解
很标准的博弈论递推。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}