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

博弈论

博弈论

赶紧证明一下取石子游戏的必胜条件。

\(S=a_1 \oplus a_2 \oplus a_3...\oplus a_n=0\) 时,先手必败,反之必胜

首先当 \(a_1=a_2=...=a_n=0\) 时,先手必败,此时 \(S=0\)

\(S\ne0\) 时,必然能让 \(S=0\)

证明当 \(S\ne0\) 时,必然能让 \(S=0\)

  • 首先对于 \(a_1 \oplus a_2 \oplus a_3...\oplus a_n=S\) ,只要 \(S\oplus S\) 即可变为 \(0\)
  • 证明一定存在 \(a_i\) 通过减法可以变成 \(a_i\oplus S\) 即可。

也就是证明存在 \(a_i\) 使得 \(a_i>a_i\oplus S\)

找出一个最高位与 \(S\) 相等的数 \(a_i\) 即可。

\(S=0\) ,只能让 \(S\) 变成非 \(0\) ,因为此时此刻每次减法都会改变每一位的个数,只要有一位 \(1\) 的个数变成了奇数,那么便是 \(S\ne 0\)

因为必胜状态一定是 \(S =0\) 的,所以证毕。

阶梯博弈

考虑在一个有 \(n\) 层的阶梯上,每个阶梯上有很多个小球,每次可以把一个阶梯上的若干个小球放到下一个阶梯,地面上的小球不可触碰,无法移动

首先考虑全部都在偶数层阶梯上的情况,注意到如果我是先手,每次都只能把偶数层放到奇数层,如你所见,最底下是偶数,也就是第 \(0\) 层,而后手只要把所有奇数层转移到偶数层即可,最后肯定是他把东西都放到地面,此时先手必败。

那么当奇数层有的情况,其实就是看谁能把状态变成全部偶数的情况,此时此刻如果是我就考虑把奇数都移到偶数位置,此时此刻就相当于把奇数层的小球取出来,谁先取完即可。

http://www.hskmm.com/?act=detail&tid=19118

相关文章:

  • [CEOI 2025] theseus 做题记录
  • 2025 年钣金加工厂家最新推荐排行榜发布:江门,珠三角钣金加工厂选择指南
  • 全文 -- Vortex: Extending the RISC-V ISA for GPGPU and 3D-Graphics Research - 指南
  • 2025.9.26 - 9.30
  • Codeforces Round 1053 (Div. 1) D. Attraction Theory
  • 通过AWS SSO设备代码认证进行AWS凭证钓鱼攻击(2024年更新)
  • 解码数据结构栈
  • 第七章 手写数字识别V4
  • 什么?你的蓝牙用不了了?
  • 模板库
  • 30.Linux DHCP 服务器 - 详解
  • [K230学习笔记] 前言
  • 集训队作业3——qoj#11723
  • 2025 年推拉门品牌推荐排行榜发布:聚焦玻璃推拉门,钛镁合金推拉门,厨房推拉门,阳台推拉门,淋浴隔断推拉门选择指南!
  • 2025.9.27比赛总结
  • [K230学习笔记] 目录
  • 116.飞行员兄弟
  • 2025系统门窗品牌推荐榜单发布,吉缘等一线品质品牌隔音节能实力解析
  • 课程总结(作业2)
  • 旅游管理虚拟仿真实训室:打通理论与实践壁垒 - 详解
  • 【光照】[PBR][漫反射]实现方法对比
  • Xpath 提取数据
  • Java异常以及处理
  • 复习计划
  • RTC
  • 卡特兰数与反射容斥
  • 题解:QOJ9619/洛谷13568 [CCPC 2024 重庆站] 乘积,欧拉函数,求和(数论+状压DP)
  • Momentum Gradient Descent(动量梯度下降)
  • README
  • Halcon算子——2D几何变换