当前位置: 首页 > news >正文

丢石子

I

一堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

思路:

任何正整数都可以表示为不连续斐波那契博数之和。

引理:如果m是斐波那契数,那么不超过m的所有斐波那契数中,选出若干个不连续的,能够得到的最大的和刚好就是m-1。

比如说,在1,2,3,5,8,里面,最大的和就是1+3+8=12,刚好是13-1。

--------------------------------------------------------------------------------------

当n=2时,后手必赢;

当n=3时,后手必赢;

当n=4时,只要先手取1个,剩下3个,无论后手取多少个,先手必赢;

当n=5时,①若先手先取1个,剩下4个,此时后手掌握n=4这种局面,则后手必赢;②若先手取2个,根据规则,后手可以一次性取完剩下的3个,则后手必赢;所以先手无论怎么取,此时后手必赢。

当n=6时,先手只要取1个,先手就掌握了n=5这种局面,即先手必赢;

当n=7时,先手只要取2个,先手就掌握了n=5这种局面,即先手必赢;

当n=8时,①若先手取1个时,后手就掌握了n=7这种局面,即后手必赢;②若先手取2个时,后手就掌握了n=6这种局面,即后手必赢;③若先手取3个,根据规则,后手可以一次性取走剩下的5个,剩下的情况都是后手必赢;所以无论先手怎么取,此时后手必赢。

......

继续推导下去,我们可以发现,只要n满足斐波那契数列2,3,5,8,13......,则后手必赢,否则先手必赢。相关证明看这:斐波那契博弈

public boolean helper(int n){ int f1=1;int f2=2;int f3=3;while(n>=f3){f3=f1+f2;if(f3==n) return false;f1=f2;f2=f3;}return true;
}

II

一堆石子有n个,两人轮流取.每次取最少取1个,最多取m个。取完者胜.先取者负输出"Second win".先取者胜输出"First win"

思路:

基础的巴什博奕
巴什博奕的重点是只有一堆,
如果n % (m + 1) != 0 则先手赢,如果用普通的数组会TLE。
证明:如果n = m + 1,先手最多拿m个,肯定有剩下的,所以先手必输,所以碰到k(m + 1)的局面的人必输。那么如果n = k(m + 1) + s,这个k 就是系数,s < m + 1,那么只要先手拿掉s个,这样后手面对的就是k(m + 1)局面,所以先手在n % (m + 1) != 0时必输。
 

#include <stdio.h>
#include <stdlib.h>int main()
{int m=0,n=0;while(~scanf("%d %d",&n,&m)){if(n%(m+1)==0){printf("Second win\n");}else{printf("First win\n");}}return 0;
}

相关文章:

丢石子

I 一堆石子有n个,两人轮流取.先取者第1次可以取任意多个&#xff0c;但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win". 思路&#xff1a; 任何正整数都可以表示为不连续斐波那契…...

skywalking手动上报一些指标信息

skywalking的相关概念我就不介绍了&#xff0c;有兴趣可以参看官网文档 以下提供以下简单示例手工上报一些对问题排查比较有用的一些信息。当然这些内容你也可以写成探针插件的形式&#xff0c;怎么开发探针插件也自行参考官方文档。此处仅在项目框架层面提供一些简单的示例&am…...

NUMA详解

目录 NUMA简介 NUMA开启与关闭 查看系统是否支持 关闭方法 numactl --hardware介绍 没有安装numactl工具下查看NUMA架构节点数&#xff1a; 查看每个NUMA节点的CPU使用情况&#xff1a; 看每个NUMA节点的内存使用情况&#xff1a; 查看NUMA下指定进程的运行情况 创建…...

H68K在Armbina系统下开AP

背景需求替代路由器,网上找了一大堆都不行 最后成功开启了AP 参考了两篇文章, 一篇是如何创建热点, 一篇是如何开启5G 树莓派4B创建5Ghz WiFi热点 – 风声 https://www.hncldz.com/2020/02/01/%e6%a0%91%e8%8e%93%e6%b4%be4b%e5%88%9b%e5%bb%ba5ghz-wifi%e7%83%ad%e7%82%b…...

还不懂Redis?看完这个故事就明白了!

还不懂Redis?看完这个故事就明白了! 我是Redis 你好,我是Redis,一个叫Antirez的男人把我带到了这个世界上。 说起我的诞生,跟关系数据库MySQL还挺有渊源的。 在我还没来到这个世界上的时候,MySQL过的很辛苦,互联网发展的越来越快,它容纳的数据也越来越多,用户请求也…...

Haproxy负载均衡集群

1.Haproxy支持四层和七层 2.haproxy常用的调度算法&#xff1f; 3.LSV/NGINX/HAPROXT的区别&#xff1f; 4. 5.Haproy负载均衡部署 实验需求 利用Haproxy的运用配置出负载均衡调度器&#xff0c;以此来调用两台Nginx服务器进行工作 实验所需组件 Haproxy服务器&#xff1a;192…...

17.计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度

说明书 MATLAB代码&#xff1a;计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度 关键词&#xff1a;碳捕集 虚拟电厂 需求响应 优化调度 电转气协同调度 参考文档&#xff1a;《计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度》完全复现 仿真平台&#xff1a…...

企业数字化管理中,数据治理到底怎么“治”

随着信息化、数字化的理念、技术及其应用在社会的方方面面进行扩散&#xff0c;数据的规模和丰富程度已经达到了一个新的高度&#xff0c;所以当下如何更进一步利用好数据&#xff0c;充分发挥数据的价值&#xff0c;将其真正变为高质量的数据资产成为了企业要面对的重要问题&a…...

《HelloGitHub》第 85 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 https://github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 …...

自动驾驶人机交互HMI产品技术方案

1. 概述 1.1 目的 本文档描述集卡自动驾驶系统中HMI产品的技术方案,设计人员遵循本方案进行设计,为项目开发实施提供技术方案保障。 1.2 范围 本文档适用于HMI产品项目。本文档用于指导HMI产品项目的UI、前端开发过程。 1.3 术语与缩写 术语/缩写 描述 HMI...

开发感悟20230426

一、element-ui样式设置 1. 可以直接在css中写个样式文件&#xff0c;把对应的类名改写样式&#xff0c;然后在main.js中引用&#xff0c;可以覆盖上面的&#xff0c;如果想给element-ui设置样式&#xff0c;不用设置deep了 2.可以直接修改引入的element-ui的样式&#xff0c…...

C和C++的区别

C和C的区别 1、面向对象编程&#xff1a;C是面向对象的语言&#xff0c;而C语言则不支持面向对象编程。C提供了类、对象、封装、继承、多态等面向对象的特性&#xff0c;使得程序结构更加清晰、可读性更强。2、模板&#xff1a;C提供了模板的特性&#xff0c;使得程序员可以通…...

【力扣-141】 环形链表 + 【力扣-142】 环形链表 II

&#x1f58a;作者 : Djx_hmbb &#x1f4d8;专栏 : 数据结构 &#x1f606;今日分享 : 霍桑效应(霍索恩效应) : 是指那些意识到自己正在被别人观察的个人具有改变自己行为的倾向。 霍桑效应告诉我们&#xff1a;从旁人的角度&#xff0c;善意的谎言和夸奖真的可以造就一个人&a…...

云计算:优势与未来趋势

文章目录 前言一、云计算的优势1. 降低IT成本2. 提高工作效率3. 提高业务的可靠性和稳定性4. 提升安全性 二、未来发展趋势1. AI与云计算的融合2. 边缘计算的发展3. 多云的趋势4. 服务器和存储的创新 三、 行业应用案例1.金融行业2.医疗保健行业3.教育行业4.零售和物流行业 四、…...

Linux namespace

​ 前言 从《initrd&init进程》可知&#xff0c;我们通过ssh连接linux服务器&#xff0c;其实主是linux启动一shell进程与我们做交互。而Linux又是多租户的&#xff0c;这使用得用户与用户间产生了&#xff0c;资源的争抢。 如何隔离资源&#xff0c;且让用户都无法察觉&…...

第十三章 移动和旋转(上)

移动和旋转是游戏对象最频繁地操作。我们上个章节简单介绍了Cube的移动和旋转。移动是修改transform的position属性&#xff0c;旋转是修改transform的eulerAngles&#xff08;欧拉角&#xff09;属性&#xff0c;两者属性值均可以使用Vector3向量来实现。需要大家注意的是&…...

视频文件切片

1.为什么网络点播系统使用m3u8更有优势?为何点播要用M3U8来搞&#xff1f;存成一个文件不更好吗&#xff1f; 一个MP4文件可能几百M或几个G&#xff0c;如果读取整个MP4文件的信息并且需要下载一段内容&#xff0c;首次打开播放超慢&#xff08;加载时间长&#xff09;。如果把…...

维生素的缺乏与生理功能,是否需要补充维生素【持续学习】

health & nutrition 学习自河南大学丁勇老师&#xff1a;https://space.bilibili.com/510028707 去医院查体内维生素缺啥&#xff1a;营养科或内科开单子 直接门诊查个维生素就可以。9项不到600块 正常吃饭&#xff0c;保湿和防晒 伤口愈合慢——蛋白质&#xff0c;vc 干燥…...

CUDA下载,以及下载GPU版本的pytorch

一、下载anaconda 因为这步我之前就下好了&#xff0c;主要参考这个链接&#xff1a;史上最全最详细的Anaconda安装教程 二、下载CUDA 1.首先观察自己需要什么版本的CUDA&#xff0c;以及是否安装过CUDA 先cmd&#xff0c;输入命令 nvidia-smi结果如下&#xff0c;所以我们…...

学习笔记:c存储类

✨博文作者&#xff1a;烟雨孤舟 &#x1f496; 喜欢的可以 点赞 收藏 关注哦~~ ✍️ 作者简介: 一个热爱大数据的学习者 文章目录 目录 文章目录 简介 auto 存储类 register 存储类 static 存储类 extern 存储类 总结 简介 存储类定义 C 程序中变量/函数的的存储位置…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...