关键词:
HDU2177 取(2堆)石子游戏
Problem Description
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。如果你胜,你第1次怎样取子?
Input
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,且a<=b。a=b=0退出。
Output
输出也有若干行,如果最后你是败者,则为0,反之,输出1,并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜,先输出取走相同数量的石子的情况.
Sample Input
1 2
5 8
4 7
2 2
0 0
Sample Output
0
1
4 7
3 5
0
1
0 0
1 2
# 题解
题意
中文题面
思路
威佐夫博弈的标准模型,至于取法的情况,可以先行枚举都去i个,i<=a的情况进行判断;然后枚举,从较大堆取的情况,防止重复。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int T;
int main()
int a,b,m,n;
double eqa = (sqrt(5)+1)/2;
while(~scanf("%d %d",&a,&b))
if(a==0&&b==0) break;
if(a>b) swap(a,b);
int k = b-a;
if(a==(int)(k*eqa)) printf("0
");
else
printf("1
");
for(int i=1;i<=a;i++)
m = a-i,n =b-i;
k = n-m;
if((int)(k*eqa) == m) printf("%d %d
",m,n);
for(int i=1;i<=b;i++)
m = a,n = b-i;
if(m>n) swap(m,n);
k = n-m;
if((int)(k*eqa)==m) printf("%d %d
",m,n);
return 0;
hdu1527取石子游戏(威佐夫博弈)(代码片段)
取石子游戏TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8514 AcceptedSubmission(s):4837ProblemDescription有两堆石子,数量任 查看详情
hdu1527取石子游戏(威佐夫博弈)(代码片段)
取石子游戏TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):9725 AcceptedSubmission(s):5605ProblemDescription有两堆石子,数量任 查看详情
题解报告:hdu1527取石子游戏(威佐夫博弈)(代码片段)
...http://acm.hdu.edu.cn/showproblem.php?pid=1527ProblemDescription有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走... 查看详情
hdu1527取石子游戏威佐夫博弈
题目来源:HDU1527取石子游戏题意:中文思路:威佐夫博弈必败态为(a,b)ai+i=bi ai=i*(1+sqrt(5.0)+1)/2 这题就求出i然后带人i和i+1推断是否成立下面转自网上某总结有公式ak=[k(1+√5)/2],bk=ak+k (k=0。1,... 查看详情
51nod1185威佐夫游戏v2(威佐夫博弈)
...bsp;KB分值: 0 难度:基础题 收藏 关注有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不... 查看详情
51nod1072威佐夫游戏(简单博弈)
...www.51nod.com/onlineJudge/questionCode.html#!problemId=1072题意:有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不... 查看详情
hdu2177
/******************************************************************************Author:Tree**From:http://blog.csdn.net/lttree**Title:取(两堆)石子游戏**Source:hdu2177**Hint:威佐夫博弈******************* 查看详情
博弈论-威佐夫博弈
理论分析问题:首先有两堆石子,博弈双方每次可以取一堆石子中的任意个,不能不取,或者取两堆石子中的相同个。先取完者赢。分析:首先我们根据条件来分析博弈中的奇异局势第一个(0,0),先手输,当游戏某一方面对... 查看详情
[shoi2002]取石子游戏-威佐夫博弈(代码片段)
Description有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现... 查看详情
威佐夫博弈
...样威佐夫也有一个经典的例题:1.有两堆数量分别为n,m个石子的石子堆;2.两个人轮流取石子,可以在一堆石子中取任意个,或者,在两堆石子中每堆石子取相同数目的石子; 输出:如果先手赢,输出1,否则输出0。 题解... 查看详情
poj1067取石子游戏威佐夫博弈博弈论
http://poj.org/problem?id=1067有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石... 查看详情
洛谷p2252取石子游戏(威佐夫博弈)
题目背景无题目描述有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子... 查看详情
博弈论入门之威佐夫博弈(代码片段)
...这里威佐夫博弈威佐夫博弈是一类经典的博弈问题有两堆石子,两个顶尖聪明的人在玩游戏,每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子,不能取得人输,分析谁会获得胜利博弈分析威佐... 查看详情
(博弈论高精度小数)51nod1185威佐夫游戏v2(代码片段)
有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不会出现失误。给出2堆石子的数量,问最后谁能赢得比... 查看详情
博弈论威佐夫博弈
威佐夫博弈 威佐夫博弈:有两堆石子,每次一个人可以两堆同时取相同数量的石子,也可以只取其中一堆的石子,最后谁取完谁获胜,请问先手还是后手胜? 对于学过一些博弈论基础的来说,我们需要找到... 查看详情
85-取石子-威佐夫博弈
http://poj.org/problem?id=1067 取石子游戏TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 45409 Accepted: 15533Description有两 查看详情
威佐夫博弈入门小结
...夫博弈的题型是:一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。这里提到了一个概念:奇异局势。那些证明什么的我也不会,网上也一堆。大概就是设... 查看详情
1072威佐夫游戏(v1)
...限制:1秒空间限制:131072KB分值:0难度:基础题 有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不... 查看详情