首页 > 其他分享 >威佐夫博奕

威佐夫博奕

时间:2024-02-25 19:47:26浏览次数:23  
标签:一个 Bn 然后 佐夫 博奕 mex qwq

这里。

暴力做一个后手必败局面列表是一个是一个这样的列表,然后 \((a,b)\) 等价于 \((b,a)\)。

(0,0)(1,2)(3,5)(4,7)(6,10)(8,13)

然后 \(a_i\) 是前面的 \(a_x,b_x\) 的 mex,\(b_i=a_i+i\)。

为什么是一个取 mex 的 \(+i\) 形式捏 qwq

如果先手缩小差,后手两边减就可以得到必胜局面。

如果先手扩大差,后手把可能没出现过的那一边弄成对应的就可以了。

如果先手不变差,后手把可能没出现过的那一边弄成对应的就可以了。

然后有一个 beautiful 的 beauty 定理。

对于 \(A^{-1}+B^{-1}=1\),\(n\) 为任意自然数,\(\{⌊An⌋\}\) 和 \(\{⌊Bn⌋\}\) 是自然数集合的一个划分。

然后这个地方假设显然 \(\{a_i\}\) 和 \(\{b_i\}\) 是正整数集合的一个划分,那么左边其实就是 \(\{⌊An⌋\}\),右边就是 \(\{⌊Bn⌋\}\)。

然后对于每一个 \(a_i=⌊Ai⌋\),有 \(b_i=⌊Bi⌋=⌊(A+1)i⌋\),然后就可以解出 \(A=(\sqrt 5+1)/2\) 黄金分割比了 qwq

cin >> a >> b, d=abs(a-b);
if(a>b) swap(a,b);
cout << (a!=(int)(lor*d));

标签:一个,Bn,然后,佐夫,博奕,mex,qwq
From: https://www.cnblogs.com/chelsyqwq/p/18032792

相关文章

  • 威佐夫博弈
    洛谷P2252[SHOI2002]取石子游戏|【模板】威佐夫博弈题目背景无题目描述有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在......
  • 三个博弈-巴什博奕、威佐夫博弈、尼姆博弈。acm博弈算法笔记HDU 2149,1850,1527
    博弈论(一)、acm博弈基础算法BashGame,NimGame和WythoffGame(即巴什博奕、尼姆博弈、威佐夫博弈)Bash  Game: 同余理论Nim   Game: 异或理论WythoffGame: 黄金分割(二)、三个博弈。1、巴什博奕。只有一堆n个物品,两个人轮流从这堆物品中取物, 规定每次至少取一个,......
  • 威佐夫博弈探索纪实。
    由于是纪实,所以看起来可能很下饭,请勿嘲讽——水平低的人也是有自尊的。有两堆石子,各有\(n,m\)个。双方每轮可以从任意一堆拿任意个,或从两堆分别拿\(x,y\)个,满足\(|x-y|\leqk\),不能不拿。无法操作者败,问先手必胜关于\(n,m,k\)的充要条件。考虑P/N态DP,打个表先。打......
  • 【ACM博弈论】SG函数入门(1):从巴什博奕到尼姆游戏
    在我小时候以前做题的时候,遇到博弈题往往都是漫无目的地打表找规律,或者找一些特殊情况但是没有很好的分析方法。其实博弈题是有比较套路的解题方法的,那就是利用SG函数,第一节不会讲到SG函数的具体用法,我们先来博弈入个门,学习一下最基本的博弈类型:Nim游戏。......
  • 【2023.02.16】威佐夫博弈详解
    威佐夫博弈详解威佐夫博弈(Wythoff'sgame):有两堆各若干个物品,两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。—......
  • 博奕类算法
    京东笔试,总体难度比较低,但是最后一道我做不来这题如果有思路应该不难,我觉得应该是动态规划相关的题目题目长这样我又看到力扣有这种博弈类型的题目,我觉得这是我的盲区......