【巴什博弈】取石子_woshi_momomo的博客-程序员秘密

技术标签: 博弈  小比赛例题  错题  

关于巴什博弈的一个例题:
描述 一天,TT在寝室闲着无聊,和同寝的人玩起了取石子游戏,而由于条件有限,他/她们是用旺仔小馒头当作石子。游戏的规则是这样的。设有一堆石子,数量为N(1<=N<=1000000),两个人轮番取出其中的若干个,每次最多取M个(1<=M<=1000000),最先把石子取完者胜利。我们知道,TT和他/她的室友都十分的聪明,那么如果是TT先取,他/她会取得游戏的胜利么?
输入
第一行是一个正整数n表示有n组测试数据
输入有不到1000组数据,每组数据一行,有两个数N和M,之间用空格分隔。
输出
对于每组数据,输出一行。如果先取的TT可以赢得游戏,则输出“Win”,否则输出“Lose”(引号不用输出)
样例输入
2
1000 1
1 100
样例输出
Lose
Win

这个题目意思很明显就是输出TT是否会赢,赢输出Win,输输出Lose。
首先我们来了解这个赢得条件,就可以判定TT是否会赢了。

这时就用到了巴什博弈:是用来表示取东西的时间,判断第一个人能不能取完所有的东西。
我们来过一下这个思路:有n个石子,每次最多取 1 到 m 个石子,轮到某人取石子时,可以选择取的数量。
设第一个人取的数量为k,当第二个人取的时候还剩(n-k)个石子,若这个(n-k)为m+1的倍数的时候,第一个取得人就可以以绝对的胜利去玩所有的东西。这样说课能大家会有点不明白。

那我们就好好的来讲述一下问什么绝对胜利。 这是我们可以将过程忽略,直接看最后在还剩多少东西的时候第二个取得人一定胜利。就是在(m+1)的时候,在这个时候无论第一个取多少第二个人都能取完。那我们可以这样思考如果TT再取第一次的时间就将剩余的(n-k)为(m+1)的倍数是不是就一定赢了。所以这就是胜利的条件。
好了  ,话不多说了,来看一下代码吧!!

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
	int m, k, t, i, j, n;
	cin >> t;
	while (t--) {
		j = 0;
		cin >> n >> m;
			for (i = 1; i <= m; i++) {
				if ((n - i) % (m + 1) == 0) {
					printf("Win\n");
					j = 1;
				}
			}
			if (j == 0) printf("Lose\n");
	}
	return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/woshi_momomo/article/details/79781047

智能推荐

5G UE — USIM Card — 5G 的 USIM 卡_范桂飓的博客-程序员秘密

目录文章目录目录5G 网络需要换 USIM 卡吗?5G 网络需要换 USIM 卡吗?目前三大运营商主要使用的 5G 网络架构是 NSA 架构,这种架构下,5G 网络需要依靠 4G 网络作为锚点才可以连接用户,鉴权的核心网依然是 4G 核心网,鉴权算法完全没变,当然就不需要更换 USIM卡了。那么未来如果 NSA 组网演进到 SA 组网,就需要更换 USIM 卡吗?现阶段用户通过使用运营商已发行的 4G 卡接入 5G 网络,现有的 4G 卡缺少 5G 标准中定义的新功能和新增的卡文件与服务,用户身

快速学习-Apollo配置中心搭建_remoteconfigrepository, reason: get config service_cwl_java的博客-程序员秘密

Apollo文章目录1. 什么是Apollo?2. 特点3. 设计(官方文档参考地址)3.1 基础模型3.2 界面概览3.3 添加/修改配置项3.4 发布配置3.5 客户端获取配置(Java API样例)3.6 客户端监听配置变化3.7 Spring集成样例4. 客户端集成Apollo4.1 开发环境4.1.1 java4.1.2 mysql4.1.3 下载Quick Start安装包4.2 安装部署4.2.1 创建数据库4.2.2 配置数.

关于react引入 sass , node-sass 加载不进来的坑_HURRICANE_FAST的博客-程序员秘密

关于引入sass ,node-sass加载不进来的坑1 npm install sass 做个不多说 官网文档有2 npm installnode-sass 是用来吧cssc文件编译成 css 文件的 要想使用sass 必须加载cacc 编译插件3 node-sass 插件安装 必须严格按照 node 版本按个匹配 这个规则可以看https://www.npmjs.com/package/node-sass...

进口食品供应链_weixin_30693183的博客-程序员秘密

跨境物流解决方案有两种:转运和直邮,而转运又分为海外仓转运和保税仓转运。其中,通过海外仓集货再转运回国的方式时间周期长且不可控+错单/丢单。而直邮点对点+运输快+清关效率低+物流成本非常高。目前最“炙手可热”的物流解决方案是将货品邮寄至国内保税仓,再由保税仓清关入境,并通过国内物流送至用户手中。目前,跨境电商在境外物流环节有几种做法:电商平台与第三方物流服务提...

OAuth2接入第三方认证平台实战(登录,注销,当前用户,自定义异常,白名单)_oauth接入第三方_鬼灭之刃的博客-程序员秘密

1 演示先演示一波(1)不携带token访问资源(2)登录(3)携带token访问资源(4)注销(5)注销后访问资源(6)登录后再次访问资源演示完毕,开始讲解2 授权模式选择本项目选择密码模式,原因如下, 同一个企业内部的不同产品要使用本企业的 oAuth2.0 体系。在有些情况下,产品希望能够定制化授权页面。由于是同个企业,不需要向用户展示“xxx将获取以下权限”等字样并询问用户的授权意向,而只需进行用户的身份认证即可。这个时候,由具体的产品团队开发定制化的授权界面,接收用

有个Java程序员写过一篇很有趣的blog_ZyxIp的博客-程序员秘密

有个Java程序员写过一篇很有趣的blog。大意说,有个人要钉个钉子挂画框,于是去工具店买个锤子。店主说,No,我们已经不卖锤子了。锤子有很多种,大锤、拔钉锤、圆头锤等等,如果你买了一个,之后又发现你还需要另一个怎么办?多数人只想要一把锤子,所以我们推出了万能锤,可以当各种锤子使

随便推点

UART寄存器详解_控制寄存器uconn的作用_duhengqi的博客-程序员秘密

1.UART行控制寄存器ULCONn(ULCON0, R/W, Address = 0xEC00_0000)ULCONn的含义如表8-2所示。表8-2  ULCONn的含义ULCONn位描述初始状态Reserved[7] 0Infra-Red Mode[6]是否使

TLS1.3---数据加密和完整性保护_tls1.3算法_Stride Max Zz的博客-程序员秘密

AEAD(authenticated encryption with associated data)在TLS1.3中,只保留了一种加密和保护完整性的方法就是AEAD(具有关联数据的加密认证)定义关联数据的认证加密,顾名思义,除可提供对密文数据的隐私、完整性和真实性保证外,还可提供对未加密的关联数据的完整性保证。常用的关联数据通常包括消息的长度和消息的编码方式。可让receiver验证所收到消息中已加密和未加密信息的完整性。任何企图将有效加密信息与不同上下文结合的篡改都可通过AEAD发现。背景

nand&nbsp;flash读写&nbsp;(二)&nbsp;(转)_WenguoHou的博客-程序员秘密

1)      根据2410寄存器定义如下的命令宏#define NF_CMD(cmd) {rNFCMD=cmd;}#define NF_ADDR(addr)   {rNFADDR=addr;}#define NF_nFCE_L() {rNFCONF&=~(1#define NF_nFCE_H() {rNFCONF|=(1#define NF_RSTECC() {rNFCONF

oracle11g archive,oracle11g flashback archive feature新特性_Nakano qm的博客-程序员秘密

/******flashback archive*****//***示例*****/SQL&gt; create flashback archive test_flashback tablespace tbs_16k quota 100 M retention 1 day;DoneSQL&gt; create table t_flashback(a int);Table createdSQL&gt...

字符数组初始化_字符数组的初始化_8UG的博客-程序员秘密

字符数组的初始化字符数组的初始化与数值型数组初始化没有本质区别。但它除了可以逐个给数组元素赋予字符外,也可以直接用字符串对其初始化。(1)用字符常量逐个初始化数组。例如:char a[8]={'i','l','o','v','e','y','o','u'};用逐个初始化的方法与数值型数组初始化本质上是一样的,同样也可以进行完全赋初值及不完全赋初值,但是不完全赋值时没有赋值的元素被赋

微信小程序--亲戚称呼计算_weixin_34117211的博客-程序员秘密

关于微信一词,相信有很多人都挺喜欢。方便,简洁等特点更是让它成为家户喻晓的产品。对于程序员来说,相信更是好奇它的技术与开发吧。一年前的小程序刷遍朋友圈,大约一月前的小游戏(跳一跳)亦是如此。考试前的那段时间实在无聊,于是了解了一下微信小程序的开发...

推荐文章

热门文章

相关标签