最近总是做到有关博弈之类的题目,突然想认真的了解一下,现在将我的了解总结如下,希望对看到的人有所帮助。同时也请多多支持哈~~
巴什博弈是众多博弈种类中众多的一种,同时也是最简单的一种。它的基本模型是只有一堆物品,数量为n,两个人轮流从这堆物品中拿走x(1<=x<=m)个,拿走最后一个的人获胜。
这里有两个基本的特点:一堆物品;两个人;拿走的数量处于一个区间内。
下面我们对物品数量的组成有如下几种方式:
- 假设物品的数量有n=m+1个,那么先手一次最多拿走m个,假设先手拿走的数量处于[1,m],中,那么剩下的数量一定会处于[1,y](y处于[1,m]中),则后手一定可以一次性将剩下的物品拿走,先手必败。
- n=(m+1)*r个,同样的,先手一次最多拿走m个,假设先手拿走的数量num处于[1,m]中,那后手一定会拿走(m+1-num)个,是数量仍然满足n=(m+1)*r这个关系,这样进行若干轮后就会转换为第一种情况,此时先手必败。
- n=(m+1)*k+r。现在先手拿走的数量为r ,则剩下的数量为 n=(m+1)*k,注意此时是后手面临第二种情况,此时后手必败,先手必胜。
由此我们发现,谁面临的数量为(m+1)的整除倍,谁就必败。
入门题:
brave game
题意:模板题,题意就是两个人取石子,先去取光者获胜。
题解:巴什博弈
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; int n,a,b; int main() { cin>>n; while(n--){ cin>>a>>b; if(a%(b+1)!=0){ cout<<"first"<<endl; }else{ cout<<"second"<<endl; } } return 0; }
相同题目推荐:hdu-2188 hdu-2149
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599710.html