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

基础

这里将简要介绍一下 Bash Game,Wythoff Game,Nimm Game。

Bash Game

  • 问题模型:有一堆物品,数量为 \(n\),两个人轮流取,每次至少取 \(1\) 个,最多取 \(m\) 个。最后取光者胜。
  • 结论:如果 \(n\bmod(m+1)=0\),则先手必败,否则先手必胜。
  • 解释:如果 \(n\)\(m+1\) 的倍数,那么无论先手取多少(比如 \(k\) 个),后手都可以取 \(m+1-k\) 个,使得剩下的物品数仍然是 \(m+1\) 的倍数。这样后手总能取走最后一个。如果不是倍数,先手可以取走一些使得剩下的是 \(m+1\) 的倍数,然后变成后手面对必败局面。

Wythoff Game

  • 问题模型:有两堆物品,每堆分别有 \(a\)\(b\) 个。两个人轮流取,每次可以从一堆中取任意个(至少 \(1\) 个),或者从两堆中同时取相同个数的物品(至少 \(1\) 个)。最后取光者胜。
  • 结论:我们记局势为 \((a,b)\)(假设 \(a\le b\))。如果满足 \(a=\lfloor(b-a)\times\frac{sqrt(5)+1}{2}\rfloor\) 则先手必败,否则先手必胜。
  • 解释:这个结论涉及黄金分割比。必败局势按照第一个坐标排序,第二个坐标是第一个坐标加上序号乘以黄金分割比。这些必败局势有规律地分布。

Nimm Game

  • 问题模型:有 \(n\) 堆物品,每堆分别有 \(a_1,a_2,\cdots,a_n\) 个。两个人轮流从某一堆中取任意个物品(至少 \(1\) 个)。最后取光者胜。
  • 结论:如果 \(a_1\oplus a_2\oplus\cdots\oplus a_n=0\),则先手必败,否则先手必胜。
  • 解释:异或和为 \(0\) 的状态为必败状态。因为如果当前异或和不为 \(0\),先手总可以取走一些物品使得异或和变为 \(0\);而如果当前异或和为 \(0\),那么无论怎么取,都会使得异或和不为 \(0\)。这样,后手总是面临非 \(0\) 状态,先手总是面临 \(0\) 状态,直到最后先手取光。
http://www.hskmm.com/?act=detail&tid=35788

相关文章:

  • yorg 到此一游
  • Vue技术之Vxe-Table的虚拟滚动
  • 实用指南:一次借助ChatGPT抵御恶意攻击的经历,为个人服务器添加自动防御系统Fail2ban
  • EasyCVR视频汇聚平台GB28181级联异常排查:上级订阅信息无响应的根源解析
  • SecureCRT 批量创建会话-cnblog
  • 2025干燥设备厂家权威推荐:常州亿干专业定制实验室喷雾与真空耙式干燥机
  • 草稿
  • 2025机电安装厂家推荐:太仓华芃专注工业设备安装,实力厂家可靠之选
  • Docker补充
  • 【QNX】Socket ServerClient 源代码
  • arp 断网小实验
  • 2025 年箱变压器厂家最新推荐榜单:涵盖非晶合金铁心、三相、矿用等多类型设备,助力采购方精准筛选优质合作企业
  • 从“人防”到“智防”:EasyCVR+煤矿AI智能分析一体机重塑矿山安全监管模式
  • 从Java工程师到AI工程师,我花了6个月的转型经验分享
  • 2025 年最新推荐配电柜源头厂家口碑排行榜:聚焦高压智能防爆等多类型产品,精选实力品牌助企业采购高压/智能/抽屉式/照明/防爆配电柜厂家推荐
  • 2025南京鑫铭机械厂家推荐:精密钣金加工与天文台圆顶定制专家
  • 2025年氢氧化镁厂家推荐排行榜,矿石氢氧化镁,水镁石氢氧化镁,阻燃剂氢氧化镁,改性氢氧化镁源头企业实力解析
  • vue控制页面不能复制
  • 开源能源管理系统 MyEMS:赋能企业降本增效,加速能源数字化转型
  • 2025工业臭氧检测仪实力厂家推荐,逸云天电子专业提供多场景精准监测方案
  • FMC学习笔记
  • MyEMS:赋能高效能源管理的核心工具
  • 2025 年最新推荐!国内优质充电桩厂家排行榜,助您精准挑选适配性强、安全高效的充电设备电车/智能/新能源/电动车充电桩厂家推荐
  • 优惠券测试用例
  • 2025工装定制实力厂家推荐:贵格服饰专注防静电工装与POLO衫定制
  • 2025 年物流公司最新推荐排行榜:覆盖多线路运输,精选优质品牌助您高效选择
  • 2025潮流服饰实力厂家推荐,COVERNAT乐酷天打造品质穿搭新选择
  • 2025 年太阳能厂家最新推荐:企业综合实力测评榜单,含热水 / 发电 / 光伏系统等全品类服务商彩图发电系统 / 分户储水系统 / 分户计量系统公司推荐
  • 2025铝单板厂家推荐杰兰斯装饰,专注异形冲孔雕花定制!
  • vscode(Visual Studio Code) 下载安装及简单使用