HDU 1846 Brave Game 巴什博奕
2024-08-27 02:52:56
解题报告:Alice和Bob在做一个取石子游戏,有一堆n个石子,然后规定每个人每次最少要去1个石子,最多可以取m个石子,最后一次取完石子的人为胜。
巴什博奕,关键是找到必胜点和必败点,我们可以先列举出当n和m都比较小的情况,下面 以1代表第一个取的人为胜,0表示第一个取的人为负:
n <= m 1
n == m+1 0
n == m+2 1
..............
n == 2*m+1 1
n == 2*m+2 0
下面解释一下:当n小于m的时候,很显然,是第一个人胜利,当n 等于m+1的时候,由于第一个人至少都要取一个,取完一个之后,只剩下m个,第二个人可以一次取完,输了。于是我们可以确定,不管是谁到达这个m+1这个点,则可以判断,这个人一定会输。而当 m+1 < n < 2*m+ 2 时 ,由于第一个人可以一次取掉,从而可以使剩余的石子数为m+1所以当 m+1 < n < 2*m+ 2 时,第一个取的人一定会赢,然而,当n == 2*m + 2 时,不管第一个人是拿一个也好,拿2到m个也好,剩余的石子数一定会在 m+1 < n < 2*m+ 2 之间,这就直接导致了第二个人处于这个有利的地位,所以第一个人就输了。。。。。以此类推,可以总结出,当n 等于i个m+i的时候(i为正整数),第一个取的人一定是输的。
#include<cstdio>
#include<iostream>
using namespace std; int main()
{
int n,m,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
if(m != )
{
int i;
for(i = ;(m+)*i<=n;++i)
if((m + ) * i == n)
break;
printf((i == n/(m+)+)? "first\n":"second\n");
}
else printf( n & ? "first\n":"second\n");
}
return ;
}
最新文章
- 当年只会C# 所以写C++就成这样了!
- 快速入门系列--WCF--02消息、会话与服务寄宿
- jquery 基础教程[温故而知新二]
- hibernate 实现多表连接查询(转载)
- 使用 Aircrack-ng 破解 WEP 和 WPA/WPA2 加密的 Wi-Fi 密码。(转)
- 使用的 SQL Server 版本不支持数据类型“datetime2”的错误解决方法
- C#学习笔记---修饰符,this关键字和static关键字
- 为benchmarksql的PostgreSQL java驱动进行升级
- 一个在mac上编译c++程序的低级失误
- 自己动手搭建苹果推送Push服务器
- css自适应
- Spring3.x企业应用开发实战-Spring+Hibernat架构分析
- 阿里云 Windows 2012 如果安装IIS
- 弹性盒子模型属性之flex-grow
- java程序的三种结构
- wget(转)
- day58
- xheditor-文件上传-java-支持html5-application/octet-stream
- bash if 表达式含义
- Call removeView() on the child&#39;s parent first