关键词:
题目来源:HDU 1527 取石子游戏
题意:中文
思路:威佐夫博弈 必败态为 (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,2,…,n 方括号表示取整函数)
当中出现了黄金切割数(1+√5)/2 = 1。618…,因此,由ak,bk组成的矩形近似为黄金矩形
因为2/(1+√5)=(√5-1)/2,能够先求出j=[a(√5-1)/2]
若a=[j(1+√5)/2]。那么a = aj,bj = aj + j
若不等于。那么a = aj+1,bj+1 = aj+1+ j + 1
若都不是,那么就不是神秘势
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int main() { int a, b; while(scanf("%d %d", &a, &b) != EOF) { if(a > b) swap(a, b); int k = (sqrt(5.0)-1)/2*(double)a; double t = (double)(sqrt(5.0)+1)/2; if((int)(t*k) == a && (int)(a+k) == b) puts("0"); else if((int)(t*(k+1)) == a && (int)(a+1+k) == b) puts("0"); else puts("1"); } 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有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走... 查看详情
hdu2177取(2堆)石子游戏(威佐夫博弈)(代码片段)
HDU2177取(2堆)石子游戏ProblemDescription有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石... 查看详情
85-取石子-威佐夫博弈
http://poj.org/problem?id=1067 取石子游戏TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 45409 Accepted: 15533Description有两 查看详情
[shoi2002]取石子游戏-威佐夫博弈(代码片段)
Description有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现... 查看详情
poj1067取石子游戏威佐夫博弈博弈论
http://poj.org/problem?id=1067有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石... 查看详情
51nod1185威佐夫游戏v2(威佐夫博弈)
...bsp;KB分值: 0 难度:基础题 收藏 关注有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不... 查看详情
洛谷p2252取石子游戏(威佐夫博弈)
题目背景无题目描述有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子... 查看详情
51nod1072威佐夫游戏(简单博弈)
...www.51nod.com/onlineJudge/questionCode.html#!problemId=1072题意:有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不... 查看详情
博弈论-威佐夫博弈
理论分析问题:首先有两堆石子,博弈双方每次可以取一堆石子中的任意个,不能不取,或者取两堆石子中的相同个。先取完者赢。分析:首先我们根据条件来分析博弈中的奇异局势第一个(0,0),先手输,当游戏某一方面对... 查看详情
博弈论入门之威佐夫博弈(代码片段)
...这里威佐夫博弈威佐夫博弈是一类经典的博弈问题有两堆石子,两个顶尖聪明的人在玩游戏,每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子,不能取得人输,分析谁会获得胜利博弈分析威佐... 查看详情
巴仕博弈+威佐夫博弈(代码片段)
...在话下了巴什博奕:两个顶尖聪明的人在玩游戏,有n个石子,每人可以随便拿1到m个石子,不能拿的人为败者,问谁会胜利巴什博奕是博弈论问题中基础的问题它是最简单的一种情形对应一种状态的博弈博弈分析如果有m+1个石子... 查看详情
威佐夫博弈
...样威佐夫也有一个经典的例题:1.有两堆数量分别为n,m个石子的石子堆;2.两个人轮流取石子,可以在一堆石子中取任意个,或者,在两堆石子中每堆石子取相同数目的石子; 输出:如果先手赢,输出1,否则输出0。 题解... 查看详情
(hdu-1527)取石子游戏(斐波那契博弈)(代码片段)
题目链接:取石子游戏-HDU1527-VirtualJudge(ppsucxtt.cn)这道题目显然是一道斐波那契博弈的裸题,我在这里只给出代码,如果有对斐波那契博弈题目的做法不理解的小伙伴可以看下我之前的博客,我在这里给出博客地址... 查看详情
威佐夫博弈入门小结
...夫博弈的题型是:一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。这里提到了一个概念:奇异局势。那些证明什么的我也不会,网上也一堆。大概就是设... 查看详情
博弈论威佐夫博弈
威佐夫博弈 威佐夫博弈:有两堆石子,每次一个人可以两堆同时取相同数量的石子,也可以只取其中一堆的石子,最后谁取完谁获胜,请问先手还是后手胜? 对于学过一些博弈论基础的来说,我们需要找到... 查看详情
(博弈论高精度小数)51nod1185威佐夫游戏v2(代码片段)
有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不会出现失误。给出2堆石子的数量,问最后谁能赢得比... 查看详情