首页 > 代码库 > 51nod_1831: 小C的游戏(Bash博弈 找规律)
51nod_1831: 小C的游戏(Bash博弈 找规律)
题目链接
此类博弈不需要考虑sg函数,只需要确定必胜态和必败态,解题思路一般为打败先打表找规律,而后找规律给出统一的公式。打表方式:给定初始条件(此题中为ok[0]=ok[1]=0),然后从低到高枚举某一状态的所有次态,若有存在必败次态,则当前状态为必胜态,否则当前状态必败。
题意:对单独一堆石子,支持两种操作:1、石子数-1;2、石子数变为原来石子数的某一因数。取走走后一堆或无法操作(面对n==0,坑啊。。)者为负。
先打表找下规律
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 int ok[1010]; 6 7 void init() 8 { 9 ok[0]=ok[1]=0; 10 for(int i=2; i<=1000; i++) 11 { 12 if(!ok[i-1]) 13 { 14 ok[i]=1; 15 continue; 16 } 17 for(int j=2; j<=i/2; j++) //分成等量j份,每份i/j个 18 if(i%j==0 && !ok[i/j]) 19 { 20 ok[i]=1; 21 break; 22 } 23 } 24 } 25 26 void print() 27 { 28 for(int i=0; i<=1000; i++) 29 printf("i=%d\tok[%d]=%d\n",i,i,ok[i]); 30 } 31 32 int main() 33 { 34 init(); 35 system("pause"); 36 print(); 37 }
发现质数除了2和17都是败的,合数除了16,34和289都是赢的。我们发现2,4,8都是赢的(都可以通过-1到达必败态,而16的后继状态都是赢的,所以它是败的,而2^n(n>4)都能转化到16。同样的我们能说明17,34和2^n,17^m。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 bool is_prime(LL x) 6 { 7 if(x<2) return false; 8 for(LL i=2;i*i<=x;i++) 9 if(x%i==0) return false; 10 return true; 11 } 12 13 int T; 14 LL n; 15 16 int main() 17 { 18 cin>>T; 19 while(T--) 20 { 21 cin>>n; 22 bool flag; 23 if(is_prime(n)) 24 { 25 if(n==2||n==17) flag=true; 26 else flag=false; 27 } 28 else 29 { 30 if(n<2||n==16||n==34||n==289) flag=false; 31 else flag=true; 32 } 33 puts(flag? "TAK":"NIE"); 34 } 35 }
51nod_1831: 小C的游戏(Bash博弈 找规律)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。