直接把所有数的sg值算出来就行了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int maxn=1002333; 7 int sg[maxn]; 8 int st[8]; 9 int i,j,k,n,m;10  11 int ra;char rx;12 inline int read(){13     rx=getchar(),ra=0;14     while(rx<'0'||rx>'9')rx=getchar();15     while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra;16 }17 int main(){18     sg[0]=0;int mx,mn;19     for(i=1;i<=1000000;i++){20         mx=0,mn=10;21         for(k=i;k;k/=10){22             j=k%10;23             if(j>0&&j
          
           mx)mx=j;25         }26         if(mx==mn)sg[i]=!sg[i-mx];27         else if(sg[i-mx]&&sg[i-mn])sg[i]=0;28         else if(sg[i-mx]!=1&&sg[i-mn]!=1)sg[i]=1;29         else sg[i]=2;30     }31     for(int T=read();T;T--)32         puts(sg[read()]?"YES":"NO");33 }