【hdu 1846】Brave Game
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11084 Accepted Submission(s): 7454
Problem Description
十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫《勇敢者的游戏》(英文名称:Zathura),一直到现在,我依然对于电影中的部分电脑特技印象深刻。
今天,大家选择上机考试,就是一种勇敢(brave)的选择;这个短学期,我们讲的是博弈(game)专题;所以,大家现在玩的也是“勇敢者的游戏”,这也是我命名这个题目的原因。
当然,除了“勇敢”,我还希望看到“诚信”,无论考试成绩如何,希望看到的都是一个真实的结果,我也相信大家一定能做到的~
各位勇敢者要玩的第一个游戏是什么呢?很简单,它是这样定义的:
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个;
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子;
5、 最先取光石子的一方为胜;
如果游戏的双方使用的都是最优策略,请输出哪个人能赢。
Input
输入数据首先包含一个正整数C(C<=100),表示有C组测试数据。
每组测试数据占一行,包含两个整数n和m(1<=n,m<=1000),n和m的含义见题目描述。
Output
如果先走的人能赢,请输出“first”,否则请输出“second”,每个实例的输出占一行。
Sample Input
2
23 2
4 3
Sample Output
first
second
【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=1846
【题解】
博弈论
1..m是先手必胜
则m+1..n这个区间里面
枚举i
看看i-m..i-1这个区间里面有没有先手比败的,如果有则可以让对方面对那个先手必败态.
则你就是先手必胜态了;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 1000+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
int n,m;
bool bo[MAXN];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
int T;
rei(T);
while (T--)
{
rei(n);rei(m);
rep1(i,1,m)
bo[i] = 1;
rep1(i,m+1,n)
{
bool fi = false;
rep1(j,i-m,i-1)
if (!bo[j])
{
fi = true;
break;
}
if (fi)
bo[i] = true;
else
bo[i] = false;
}
if (bo[n])
puts("first");
else
puts("second");
}
return 0;
}
【代码2】
总是保持给另外一个人留m+1的倍数的个数的石头;
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
//const int MAXN = x;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
int main()
{
//freopen("F:\\rush.txt","r",stdin);
int T;
rei(T);
rep1(i,1,T)
{
int n,m;
rei(n);rei(m);
if ((n%(m+1))==0)
puts("second");
else
puts("first");
}
return 0;
}
最新文章
- Android探索之AIDL实现进程间通信
- Jquery制作--焦点图淡出淡入
- 20161022 NOIP模拟赛 T1 解题报告
- nullcon HackIM 2016 -- Crypto Question 2
- Java AES加密
- Ibatis 美元符号替换为井号
- 下拉刷新--第三方开源--PullToRefresh
- lintcode : 空格替换
- 关于Eclipse的工作空间设置默认个数和配置
- .net杂记
- Floyd算法(最短路)
- 基于Android的高校饮水宝app
- 开机进入grub命令行之后。。。。
- PHP语言学习之php做图片上传功能
- 解题报告 『宝藏(Prim思想 + 访问顺序随机)』
- adb.exe已停止工作
- 个人笔记本安装多个jdk(jdk1.7,jdk1.8,jdk1.9,jdk10.0)出现的问题
- Django 学生信息 添加 功能 遇到的问题.
- Mac 安装配置nexus2.6 搭建Maven的中央仓库
- [vue]模拟移动端三级路由: router-link位置体现router的灵活性
热门文章
- amaze样例页面分析(一)
- 100.dll调用
- 为什么在AJAX里面直接return 一个值,接受不到?
- spyder结束死循环的方法
- ejs模板引擎的使用
- [React Intl] Render Content with Markup Using react-intl FormattedHTMLMessage
- 飞镖忍者 quick-cocos2d-x3.2
- 从零开始使用git第三篇:git撤销操作、分支操作和常见冲突
- OC学习篇之---Foundation框架中的NSString对象和NSMutableString对象
- 【例题 6-2 UVA - 514】Rails