当前位置: 首页 > 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;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...