【博弈】【HDU】取石子游戏
2024-09-18 00:13:42
取石子游戏
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7192 Accepted Submission(s): 4313
Problem Description
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
Output
先取者负输出"Second win". 先取者胜输出"First win".
参看Sample Output.
参看Sample Output.
Sample Input
2
13
10000
0
13
10000
0
Sample Output
Second win
Second win
First win
Second win
First win
Source
Recommend
寻找规律可以知道,必败的情况下都是斐波那契数,所以做一匹配就可以了,使用离线和二分法搜索来提高效率。
#include<bits/stdc++.h>
using namespace std; long long fs[]; void init() {
fs[] = ;
fs[] = ; for(int i = ; i <= ;i ++) {
fs[i] = fs[i-] + fs[i-];
}
} bool find(long long n) {
int l = ;
int r = ;
int mid = (l+r) >> ; // (l+r)/2
while(l <= r) {
if(fs[mid] == n) return true;
else if(fs[mid] < n) l = mid + ;
else r = mid - ;
mid = (l+r) >> ;
}
return false;
} int main() { init();
long long n;
while(~scanf("%lld",&n)&&n) {
if(find(n)) puts("Second win");
else puts("First win");
}
return ;
}
最新文章
- sql server 常用的扩展存储过程
- win php nginx 配置小细节
- Java对MySQL数据库进行连接、查询和修改【转载】
- MINA源码阅读之ACP
- Tomcat的server.xml(中文版)
- substr(dirname(__FILE__))
- Hibernate由model类自动同步数据库表结构
- 浏览器中显示PPT的展示效果
- 2019-04-16 SpringMVC 学习笔记
- 在Kubernetes中部署GlusterFS+Heketi
- Linux学习笔记之Centos7安装GNOME桌面环境
- [翻译] EnterTheMatrix
- 使用开源库 EasyTimeline 操作定时器 NSTimer
- eAccelerator 配置参数详解
- phpcms开启在线编辑模版 方法
- Mycat实战之离散分片
- 【C#】 RBAC 权限框架
- Selenium3 Python3 Web自动化测试从基础到项目实战之二浏览器的不同设置
- C#复习总结6 (需要进一步复习)
- Oracle imp exp命令具体解释
热门文章
- [洛谷P1196][NOI2002]银河英雄传说 - 带偏移量的并查集(1)
- Spark:将RDD[List[String,List[Person]]]中的List[Person]通过spark api保存为hdfs文件时一直出现not serializable task,没办法找到";spark自定义Kryo序列化输入输出API";
- 框架学习之Struts2(三)---OGNL和值栈
- 目标检测算法YOLO算法介绍
- tkinter打招呼
- MySQL &#183; 引擎特性 &#183; InnoDB 数据页解析
- Linear Regression with Scikit Learn
- 洛谷P2405 non天平
- bzoj 2555: SubString
- ●UOJ 131 [NOI2015] 品酒大会