Day11 - J - Brave Game HDU - 1846
2024-10-08 14:11:39
十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫《勇敢者的游戏》(英文名称: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的含义见题目描述。
Output如果先走的人能赢,请输出“first”,否则请输出“second”,每个实例的输出占一行。Sample Input
2
23 2
4 3
Sample Output
first
second 经典的Bash博弈问题,0是P状态,1~m是N状态,则m+1是P状态,m+2~2m+1又是N状态,2(m+1)就是P状态以此类推,当(m+1)|n的时候,就是P状态,先手必败,换句话说,当(m+1)|n时,先手每次只能选择1~m,后手一定能取m+1的剩下个,后手一定赢,否则,先手就取n%(m+1),相当于后手进入先手状态
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL; void run_case() {
int n, m;
cin >> n >> m;
if(n%(m+)==) cout << "second\n";
else cout << "first\n";
} int main() {
ios::sync_with_stdio(false), cin.tie();
int t; cin >> t;
while(t--)
run_case();
cout.flush();
return ;
}
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL; const int maxm = ; int sg[maxm];
bool vis[maxm]; void run_case() {
int n, m; cin >> n >> m;
sg[] = ;
for(int i = ; i <= n; ++i) {
memset(vis, false, sizeof(vis));
for(int j = ; j <= m; ++j) {
if(j > i) break;
vis[sg[i-j]] = true;
}
for(int j = ;; ++j)
if(!vis[j]) {
sg[i] = j;
break;
}
}
if(sg[n]) cout << "first\n";
else cout << "second\n";
} int main() {
ios::sync_with_stdio(false), cin.tie();
int t; cin >> t;
while(t--)
run_case();
cout.flush();
return ;
}
SG函数
最新文章
- java读取属性文件propertie中文乱码问题
- PEM (Privacy Enhanced Mail) Encoding
- centos配置yum源
- IntelliJ IDEA快捷键和常用设置
- POJ 3278 经典BFS
- shell语句记录-awk
- UVALive 6533
- python 在调用时计算默认值
- keil采用C语言模块化编程时全局变量、结构体的定义、声明以及头文件包含的处理方法
- matlab取整
- autoprefixer安装或者里sass的$mixin处理浏览器前缀
- windows 2003 server 安装 .NET Framework 2.0环境
- gzip解压压缩的字符串数据
- qt新进程工作目录的设置(工作目录确实是被子进程继承的,但也可以设置)
- 制作类似ThinkPHP框架中的PATHINFO模式功能(二)
- Dev控件treeList
- repo 用法
- c++两个类相互调用
- 基于快速排序思想partition查找第K大的数或者第K小的数。
- Oracle_spatial的常见错误与注意事项
热门文章
- Go 语言 fmt.Sprintf (格式化输出)
- Tomcat,Jboss,Weblogic通过jndi连接数据库
- as(android studio)的初次使用
- Python MySQLdb中执行SQL语句传入的参数应该要加上引号如果该字段是str类型的
- 公用技术——面向对象领域——UML图——《The Unified Modeling Language User Guide》V2读书笔记——第一章节(建模的意义)
- 【CSS属性#1】
- LVS、Tomcat、Nginx、PHP优化项
- android界面布局
- JDK8源码解析 -- HashMap(二)
- Python:列表类型