分析：直接dp就好了，设f[i]表示i先手的输赢，由1-9可以推出来后面的，因为如果能从先手必赢变成先手必输，那么肯定可以转移。。当然也可以直接算出所有数的sg值。。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e6+6; int f[N]; int main() { int cas; scanf("%d\n",&cas); fo(i,1,9)f[i]=1; fo(i,10,N) { int s=i; int mx=-1,mn=10; while (s) { int x=s%10; if(x)mx=max(mx,x); if(x)mn=min(mn,x); s/=10; } if (-1!=mx)f[i]|=(!f[i-mx]); if (mn!=10)f[i]|=(!f[i-mn]); } fo(i,1,cas) { int x; scanf("%d",&x); if (f[x])printf("YES\n");else printf("NO\n"); } }