【题解】Luogu P2953 [USACO09OPEN] 牛的数字游戏 博弈论
博弈论模型：
当某种状态的后继都是必败态时，这个状态是必胜态
当某种状态的后继有一个是必胜态时，这个状态是必败态
显然$1-9$都是先手必胜态
根据这个开始往后推
因为题目中说了只能取最大的或者最小的，那么每个$n$只能从$f[n-max]$或$f[n-min]$转移过来
令$f[1-9]=1$
有 $f[i]=(!f[i-max]||!f[i-min])$
如果取最大/最小位后有一个是必败态，那该状态就为必胜态
要先预处理出$1～maxn$的$f[]$不然会T
code
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=1e6+10; 5 namespace gengyf{ 6 inline int read(){ 7 int x=0,f=1;char s=getchar(); 8 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 9 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 10 return f*x; 11 } 12 int t,n,f[maxn],minn,maxx; 13 void calc(int x){ 14 minn=10;maxx=0; 15 while(x){ 16 int k=x%10; 17 if(k)minn=min(minn,k); 18 maxx=max(maxx,k); 19 x/=10; 20 } 21 } 22 int main(){ 23 for(int i=1;i<=9;i++)f[i]=1; 24 for(int i=10;i<=maxn;i++){ 25 calc(i); 26 f[i]=(!f[i-minn]||!f[i-maxx]); 27 } 28 t=read(); 29 while(t--){ 30 n=read(); 31 if(f[n])puts("YES"); 32 else puts("NO"); 33 } 34 return 0; 35 } 36 /* 37 aggressive 有进取心的 38 alert 机敏的 39 alliance 联盟 40 alter 修改 41 */ 42 } 43 signed main(){ 44 gengyf::main(); 45 return 0; 46 }View Code 优质内容筛选与推荐>>
1、搜索二叉树的简单实现
2、win8系统下,python 2.7安装xlrd,xlutils和xlwt的方法
3、WPF控件按分类汇总
4、JAVA学长
5、又是一年查分时