关键词:
Description
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
Solution
威佐夫博弈模板题
如果一个局面是 N 必败局面,那么我们称它为奇异局面
结论是,任意一个局面满足 (a_k = [kC], b_k = a_k+k),其中 (C=(1+sqrt 5)/2)
这样我们可以先用 (b-a) 求出 (k),然后判定是否合法即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int a,b;
const double c = (1+sqrt(5))/2;
signed main()
cin>>a>>b;
if(a>b) swap(a,b);
int k=b-a;
if(a==(int)(k*c)) cout<<0;
else cout<<1;
hdu1527取石子游戏(威佐夫博弈)(代码片段)
取石子游戏TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):9725 AcceptedSubmission(s):5605ProblemDescription有两堆石子,数量任 查看详情
hdu2177取(2堆)石子游戏(威佐夫博弈)(代码片段)
HDU2177取(2堆)石子游戏ProblemDescription有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石... 查看详情
题解报告:hdu1527取石子游戏(威佐夫博弈)(代码片段)
...http://acm.hdu.edu.cn/showproblem.php?pid=1527ProblemDescription有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走... 查看详情
hdu1527取石子游戏(威佐夫博弈)
TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8509 AcceptedSubmission(s):4833ProblemDescription有两堆石子,数量任意,可以不 查看详情
85-取石子-威佐夫博弈
http://poj.org/problem?id=1067 取石子游戏TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 45409 Accepted: 15533Description有两 查看详情
poj1067取石子游戏威佐夫博弈博弈论
http://poj.org/problem?id=1067有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石... 查看详情
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都非常聪明,拿石子的过程中不... 查看详情
洛谷p2252取石子游戏(威佐夫博弈)
题目背景无题目描述有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子... 查看详情
博弈论入门之威佐夫博弈(代码片段)
...这里威佐夫博弈威佐夫博弈是一类经典的博弈问题有两堆石子,两个顶尖聪明的人在玩游戏,每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子,不能取得人输,分析谁会获得胜利博弈分析威佐... 查看详情
巴仕博弈+威佐夫博弈(代码片段)
...在话下了巴什博奕:两个顶尖聪明的人在玩游戏,有n个石子,每人可以随便拿1到m个石子,不能拿的人为败者,问谁会胜利巴什博奕是博弈论问题中基础的问题它是最简单的一种情形对应一种状态的博弈博弈分析如果有m+1个石子... 查看详情
51nod1072威佐夫游戏(简单博弈)
...www.51nod.com/onlineJudge/questionCode.html#!problemId=1072题意:有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不... 查看详情
博弈论-威佐夫博弈
理论分析问题:首先有两堆石子,博弈双方每次可以取一堆石子中的任意个,不能不取,或者取两堆石子中的相同个。先取完者赢。分析:首先我们根据条件来分析博弈中的奇异局势第一个(0,0),先手输,当游戏某一方面对... 查看详情
(博弈论高精度小数)51nod1185威佐夫游戏v2(代码片段)
有2堆石子。AB两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不会出现失误。给出2堆石子的数量,问最后谁能赢得比... 查看详情
威佐夫博弈
...样威佐夫也有一个经典的例题:1.有两堆数量分别为n,m个石子的石子堆;2.两个人轮流取石子,可以在一堆石子中取任意个,或者,在两堆石子中每堆石子取相同数目的石子; 输出:如果先手赢,输出1,否则输出0。 题解... 查看详情
威佐夫博弈入门小结
...夫博弈的题型是:一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。这里提到了一个概念:奇异局势。那些证明什么的我也不会,网上也一堆。大概就是设... 查看详情
博弈论威佐夫博弈
威佐夫博弈 威佐夫博弈:有两堆石子,每次一个人可以两堆同时取相同数量的石子,也可以只取其中一堆的石子,最后谁取完谁获胜,请问先手还是后手胜? 对于学过一些博弈论基础的来说,我们需要找到... 查看详情
nim游戏,nim游戏变形,威佐夫博弈以及巴什博奕总结
经典NIM游戏: 一共有N堆石子,编号1..n,第i堆中有个a[i]个石子。每一次操作Alice和Bob可以从任意一堆石子中取出任意数量的石子,至少取一颗,至多取出这一堆剩下的所有石子。两个人轮流行动,取走最后一个的人胜利。Ali... 查看详情