这是一道关于博弈的问题,希望以后考试中不会遇见:
题目:
P1290 欧几里德的游戏
下面直接上代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll c;
cin>>c;
while(c--)
{
ll x,y;
cin>>x>>y;
if(x<y) swap(x,y);
bool m=true;
while(true)
{
if(x==y||x-y>=y) break;//后续证明△
else
{
m=!m;//交换身份
ll t=x-y;//只取一个并不影响?
x=y;y=t;continue;//变量赋值
}
}
if(m)cout << "Stan wins" << endl;
else cout << "Ollie wins" << endl;
}
}
下面我们来对打有△标记的地方进行讲解:
首先,我们要确定的一点就是只要一个人能够掌控全局,那么他一定赢了,这话怎么讲呢?我们举几个例子吧!(首先我们还是要假设大家都是绝顶聪明的)
例一:
16 5
那么首先若A先取:
6 5 取2个5
这时B没法只能取一个5
1 5
这时明显A赢了!
例二
17 5
若B先取:
7 5
A没法:
2 5
B再取:
2 3
A没法
2 1
B赢了
例三
5 5
谁要是先取谁就赢了
这里我们已经把所有的可以赢得情况枚举了一遍(前两个例子可以归为一类,而后面的例子单独为一类)我们先设两个要取的数分别为x,y(默认x>y),如果x-y>y即A至少可以有两种情况,一种是把x取到小于y另一种就是把x取到大于y,而这两种一定对应A的两种生死,要么赢,要么输,而另一种即x==y则如图中所说可以肯定,先取的人必胜,所以这道题就很快的被我们解决了,对了!还有其余的情况那就安分守己的一个一个取,因为如果一下取两个一定会取得小于0的!所以综上,只有这两种情况可以判断当局者是否控制局面即胜利,其他情况都不可以!
谢谢采纳!!!
原文链接: https://www.cnblogs.com/mudrobot/p/13331008.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/367639
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!