首页 > 其他分享 >博弈论

博弈论

时间:2023-08-14 20:33:19浏览次数:36  
标签:必败 博弈论 Alice 异或 枚举 Bob

博弈论

%%happyguy

img
笔记
img

nim游戏
堆异或和
取最大的一堆后异或和为零,变为先手必败。

枚举所有可能情况作为有向无环图,直到全为0,必败。全败,必败。有胜,必胜。

img

img

此例子,123为一个环,平局,尽头为先手必败(已经败了),可以向上递推。

arc143c

img

两个人都在一堆取,此堆至少(x+y)个。

必胜的一方在最优策略上模仿必败一方。

arc131_c

猜简单结论。

img

确保后手不能通过一步操作赢,所以不能取 $a_i \oplus a_j = s $ 偶数不能一步操作使序列变成0,转换为奇数情况。

agc056d

img

img

Alice模仿Bob,取比Bob大的最小数。这样配对为 \(b\) 数组。

img

答案的区间为 \(b\) 和。此时总和最小。

若 x 不为零,设 x 为 0,添加一个 x+p 的数 ,p 任取,抵消掉 x 影响。

img

img

Alice 两个 \(a_i\) 可以抵消。?

img

v(s) 最小匹配。

img

场上做法???

枚举两个数,在看剩余 \(n-2\) 个数。

总结

img

类似贪心?

标签:必败,博弈论,Alice,异或,枚举,Bob
From: https://www.cnblogs.com/muzqingt/p/17629626.html

相关文章

  • [数论第四节]容斥原理/博弈论/NIM游戏
    容斥原理\(|A\cupB\cupC|=|A|+|B|+|C|-|A\capB|-|A\capC|-|B\capC|+|A\capB\capC|\)\(|\displaystyle\cup_{i=1}^nA_i|=\sum_{i}|A_i|-\sum_{i,j}|A_i\capA_j|+\ldots+(-1)^{n+1}|\cap_{i=1}^nA_i|\)时间复杂度:\(C_n^1+C_n^2+C_n^3···+C_n^n=2......
  • 博弈论——完全信息静态博弈(二)
    完全信息静态博弈是指参与者在做出决策之前拥有所有可能的信息,包括对手的策略和利益。因此,每位参与者可以准确地评估各种选择对自己和对手的影响。这种情况下,决策的结果是确定性的,不受随机因素影响。参与者通过理性分析和预测对手的行为,以最大化自身利益。完全信息静态博弈广泛应......
  • 博弈论:移棋子游戏
    给定一个有 N 个节点的有向无环图,图中某些节点上有棋子,两名玩家交替移动棋子。玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点,无法移动者输掉游戏。对于给定的图和棋子初始位置,双方都会采取最优的行动,询问先手必胜还是先手必败。输入格式第一行,三个整数N,M,K,N 表示......
  • 博弈论:台阶-Nim游戏
    现在,有一个 nn 级台阶的楼梯,每级台阶上都有若干个石子,其中第i 级台阶上有 ai 个石子(i≥1)。两位玩家轮流操作,每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中(不能不拿)。已经拿到地面上的石子不能再拿,最后无法进行操作的人视为失败。问如果两人都采用最优策略,......
  • 博弈论笔记
    博弈论公平组合游戏公平组合游戏(ImpartialGame)的定义如下:\(\bullet\)游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息;\(\bullet\)任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关;\(\bullet\)游戏中的同一个状态不可能多次......
  • 博弈论
    Nim游戏基础模型例题:CSES1730有\(n\)堆石子,第\(i\)堆石子有\(a_i\)颗,每个人一次可以从一堆里那任意个石子(至少拿一个),不能操作的人输掉。\(1\len\le2\times10^5,1\lea_i\le10^9\)。暴力打表后发现没有什么规律,那就直接上结论吧。若\(a_1\oplusa_2......
  • 学不会的博弈论——进阶篇
    前言浅浅复习(我想说,国家队论文yyds......
  • 【学习笔记】博弈论
    SG函数与SG定理公平组合游戏公平组合游戏满足以下条件:两个玩家参与游戏,轮流操作。游戏以某个玩家不能操作未结束,且不能操作的玩家失败,游戏不含平局。游戏的操作与玩家无关,只与当前的状态有关。游戏状态不会重复出现,若将状态设为点,将一次操作对状态的改变设为有向......
  • 博弈论学习笔记
    Nim游戏给定\(n\)堆石子,第\(i\)堆石子有\(A_i\)个石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。若两人均为巨佬,采用最优策略,先手是否必胜。这种游戏被称作Nim博弈。游戏过程中面临的状态叫做......
  • 博弈论们:
    博弈论们:Nim博弈:先手,后手:第一个,第二个行动者。必胜,必败:指先手必胜或必败。定理:Nim博弈先手必胜,当且仅当:$$\bigoplus_{i=1}^nA_i\ne0$$证明:反证法假设\(A_i'=A_i\)得出矛盾。(懒,咕了,有机会再说)SG函数mex运算:对于一个非空数集:\(S\)我们将$$mex{S}$$定义为......