四种基本组合博弈POJ1067/HDU1846
2024-10-08 01:02:00
取石子游戏
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 43466 | Accepted: 14760 |
Description
有 两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆 中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是 败者。
Input
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。
Output
输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0
Source
威佐夫博弈(Wythoff's Game)
结论:设a < b,若a = [((√5 + 1)/2 * (b - a))],则为必败局面,否则为必胜局面
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
inline void swap(int &a, int &b)
{
int tmp = a;a = b;b = tmp;
}
inline void read(int &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '') c = ch, ch = getchar();
while(ch <= '' && ch >= '') x = x * + ch - '', ch = getchar();
if(c == '-') x = -x;
} const int INF = 0x3f3f3f3f; int a,b; int main()
{
while(scanf("%d %d", &a, &b) != EOF)
{
if(a > b) swap(a, b);
if((int)(((sqrt() + 1.0)/) * (b - a)) == a) printf("0\n");
else printf("1\n");
}
return ;
}
POJ1067
Brave Game
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13313 Accepted Submission(s): 8997
Problem Description
十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫《勇敢者的游戏》(英文名称:Zathura),一直到现在,我依然对于电影中的部分电脑特技印象深刻。
今天,大家选择上机考试,就是一种勇敢(brave)的选择;这个短学期,我们讲的是博弈(game)专题;所以,大家现在玩的也是“勇敢者的游戏”,这也是我命名这个题目的原因。
当然,除了“勇敢”,我还希望看到“诚信”,无论考试成绩如何,希望看到的都是一个真实的结果,我也相信大家一定能做到的~
今天,大家选择上机考试,就是一种勇敢(brave)的选择;这个短学期,我们讲的是博弈(game)专题;所以,大家现在玩的也是“勇敢者的游戏”,这也是我命名这个题目的原因。
当然,除了“勇敢”,我还希望看到“诚信”,无论考试成绩如何,希望看到的都是一个真实的结果,我也相信大家一定能做到的~
各位勇敢者要玩的第一个游戏是什么呢?很简单,它是这样定义的:
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个;
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子;
5、 最先取光石子的一方为胜;
如果游戏的双方使用的都是最优策略,请输出哪个人能赢。
Input
输入数据首先包含一个正整数C(C<=100),表示有C组测试数据。
每组测试数据占一行,包含两个整数n和m(1<=n,m<=1000),n和m的含义见题目描述。
每组测试数据占一行,包含两个整数n和m(1<=n,m<=1000),n和m的含义见题目描述。
Output
如果先走的人能赢,请输出“first”,否则请输出“second”,每个实例的输出占一行。
Sample Input
2
23 2
4 3
23 2
4 3
Sample Output
first
second
second
Author
lcy
Source
Recommend
巴什博奕(Bash Game)
若局面为(m+1)x + r,先手取r,无论后手怎么取,先手总能取成(m+1)x的局面,等到了m + 1,后手最多取m,先手必胜
若局面为(m+1)x,无论先手怎么取,后手总能取成(m+1)x的局面,同上理,后手必胜
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
inline void swap(int &a, int &b)
{
int tmp = a;a = b;b = tmp;
}
inline void read(int &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '') c = ch, ch = getchar();
while(ch <= '' && ch >= '') x = x * + ch - '', ch = getchar();
if(c == '-') x = -x;
} const int INF = 0x3f3f3f3f; int t,n,m; int main()
{
read(t);
for(;t;--t)
{
read(n), read(m);
if(n % (m + ) == ) printf("second\n");
else printf("first\n");
}
return ;
}
HDU1846
尼姆博弈(Nimm Game) 略
斐波那契博弈(Fibonacci Game) 一堆物品,两人轮流去,第一个人不能把物品全取完,以后每个人可以去至少一个至多前面的人取的个数的两倍个
结论:先手胜当且仅当n不是Fibnocci数
最新文章
- android学习笔记27——Activity
- UVa 1103 (利用连通块来判断字符) Ancient Messages
- 如何在eclipse里使用git
- HW2.6
- APUE习题5.x
- PL/SQL 程序块
- 201521123018 《Java程序设计》第3周学习总结
- asp.net core权限模块的快速构建
- Extensions in UWP Community Toolkit - Visual Extensions
- An universal algorithm design of fixed length substring locating
- Redis之实战篇(与Mybatis整合)
- Linux内存管理 (14)匿名页面生命周期
- Redis数据结构之intset(2)
- 在Eclipse中创建maven项目出现的环境警告 j2se-1.5
- bzoj 1112 poi 2008 砖块
- 【中间件安全】Apache 安全加固规范
- C语言终极面试及答案分析
- 兼容安卓和ios实现一键复制内容到剪切板
- Linux系统下C语言程序的构建过程
- <;yii 框架学习>; yii 框架改为中文提示