博弈论相关(巴什博弈,nim游戏)

it2022-05-05  164


巴什博奕

基本模型:有n个石子,两人轮流取,一次取1-m个,先取完者胜。

另一种描述:两人每次竞价,加价只能在1-m范围中,价格先达到或超过n元者胜。

解决方法:n%(m+1)==0,后手胜,否则先手胜。

 

       例题: hdu 2897 邂逅明下

       题目描述(简略版):有n个石子,两人轮流取,一次取p-q个,先取完者输。

       把问题转变为巴什博弈,写成n=(q+p)*k+r的形式,讨论即可

     

1 #include<bits/stdc++.h> 2 3 using namespace std; 4 int n,p,q; 5 int main() 6 { 7 ios::sync_with_stdio(false); 8 while(cin>>n>>p>>q) 9 { 10 int res=n%(p+q); 11 if(res>0&&res<=p) cout<<"LOST"<<endl; 12 else cout<<"WIN"<<endl; 13 } 14 return 0; 15 } 邂逅明下

 

     


         nim游戏

     (太熟了就不多介绍了)

 

       例题:【ZJOI2009】取石子游戏

      神仙题:题解见https://www.cnblogs.com/cjyyb/p/9756449.html

      yyb%%%

转载于:https://www.cnblogs.com/3200Pheathon/p/11181794.html


最新回复(0)