博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[转载学习]博弈类题目小结
阅读量:4840 次
发布时间:2019-06-11

本文共 5422 字,大约阅读时间需要 18 分钟。

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

首先当然要献上一些非常好的学习资料:

基础博弈的小结:
经典翻硬币游戏小结:
经典的删边游戏小结:
五篇国家集训队论文:
张一飞: 《由感性认识到理性认识——透析一类搏弈游戏的解答过程 》
王晓珂:《 解析一类组合游戏》
方展鹏:《浅谈如何解决不平等博弈问题》
贾志豪:《组合游戏略述——浅谈SG游戏的若干拓展及变形》
曹钦翔:《从“k倍动态减法游戏”出发 探究一类组合游戏问题》
貌似还有一篇,找不到了。对于论文,看得不是很深,里面好多证明都非常详细,也没有仔细研究过。
建议从基本的NIM博弈,深入了解SG函数的意义。

=======================================================================

HDOJ1079&POJ1082&ZOJ1024 Calendar Game [找规律博弈]

根据奇偶性的变化找到规律,特殊情况特殊考虑

HDOJ1525&POJ2348 Euclid's Game [找规律博弈]

根据每一步的必然性以及可选择性决策

HDOJ1564 Play a game [找规律]

打表发现奇偶性规律

HDOJ1846 Brave Game [找规律]

简单的巴什博弈,当n为m+1的时候后者胜,否则前者胜。因为如果为m+1,不论前者怎么取,后者都能胜。

HDOJ1847 Good Luck in CET-4 Everybody! [找规律]

基本的SG函数构造

HDOJ2147 kiki's game [找规律]

可以打出PN表,不过可以直接找到规律,n和m只要有一个为偶数则必胜

HDOJ2516 取石子游戏 [找规律]

FIB博弈模型,

HDOJ2897 邂逅明下 [找规律]SG打表

类似巴什博弈找出区间[1-p]必败 [p+1,p+q]必胜(取一个q,就能进入第一个区间) [p+q+1,2*p+q]必败,[2p+q+1,2p+2*q]必胜

HDOJ3032 Nim or not Nim? [找规律]SG打表

Lasker's Nim游戏,通过打表可以发现规律

HDOJ3389 Game [找规律]

  1. 分成一个二分图
    如果可以从A拿卡片到B,连一条从A到B的边。把所有box编号x满足((x%

3==0&&x%2==1) || x%3==1)这个条件的放左边,其他放右边,不难发现

a) 只有从左边到右边的边或从右到左的边。

b) 所有不能拿卡片出去的box都在左边。

  1. 证明左边的box并不影响结果。假设当前从右边的局势来看属于输家的人为了
    摆脱这种局面,从左边的某盒子A拿了n张卡片到B,因为B肯定有出去的边,对手
    会从B再取走那n张卡片到左边,局面没有变化
  2. 于是这就相当于所有右边的box在nim游戏。

HDOJ3537 Daizhenyang's Coin [找规律]SG打表

翻硬币游戏,之Mock Turtles游戏

HDOJ3544 Alice's Game [找规律]

题目还是有点不理解,找到最优策略,每次二分。。

HDOJ3863 No Gambling [找规律]简单对偶博弈

先者必胜,容易发现,是堵不住的

HDOJ3951 Coin Game [找规律]

环形取石子,只要第一步不取完,就变成一条链,那么对手都能从中间取,将其分成相等的两堆石子利用对称性解题

HDOJ2188 悼念512汶川大地震遇难同胞——选拔志愿者

[巴什博弈]

HDOJ2149 Public Sale [巴什博弈]输出走法

明显如果能一步达到要求的话,那么解为m……n
如果n是m+1的步数的话,是必败,无论你加多少,如果 a,对方都会加m+1-a
,否则将价格控制在n%(m+1)处

HDOJ1850 Being a Good Boy in spring Festival [基础Nim博弈]

需要输出可行方案数量,表示第一步之后要使nim积为0,则一个个判断是否大于要移走的数量

HDOJ2176 取(m堆)石子游戏

[基础Nim博弈]输出第一步走法

HDOJ1527&POJ1067 取石子游戏 [威佐夫博弈]

威佐夫博奕(Wythoff Game),判断是否为a=k*(sqrt(5)+1)/2,b=a+k

HDOJ2177 取(2堆)石子游戏 [威佐夫博弈]

需要输出方案,打表,然后查找

HDOJ1517&POJ2505 A Multiplication Game [K(2~9)倍博弈]

同样的在1-9先手必胜,面是10-18,不论先手怎么办,都是后者赢。同样19-162为先手胜。可以发现规律

HDOJ2486&HDOJ2580&POJ3922 A simple stone game [K倍动态减法游戏]

神奇构造数列

HDOJ4315 Climbing the Hill [阶梯博弈]

阶梯NIM,将奇数位作NIM,偶数位不影响

HDOJ1538 A Puzzle for Pirates [海盗分金问题]

海盗分金的详细推理以及证明

HDOJ3404 Switch lights [Nim积]


HDOJ1404 Digital Deletions [SG博弈]

由于字符串长度只有6,整合成一个整数,暴力打SG表,从P态,能一步到达的是N态

HDOJ1536&HDOJ1944&POJ2960&ZOJ3084 S-Nim [SG博弈]

SG函数,对于每一个集合,求出SG函数

HDOJ1729 Stone Game [SG博弈]

SG函数,

HDOJ1730 Northcott Game [SG博弈]

转换成之间距离的NIM博弈

HDOJ1760 A New Tetris Game [SG博弈]二维状态

DFS博弈。

HDOJ1848 Fibonacci again and again [SG博弈]

SG打表

HDOJ1849 Rabbit and Grass [SG博弈]

转换成NIM

HDOJ1851 A Simple Game [SG博弈]

范围不大,直接构造SG函数,或者转化成NIM与巴什博弈的结合

HDOJ1907&&POJ3480&ZOJ3113 John [SG博弈]

ANTI-SG,见贾志豪论文

HDOJ2509 Be the Winner [SG博弈]可以分成两堆的操作

ANTI-SG,同上

HDOJ2873 Bomb Game [SG博弈]

SG函数打表,类似于NIM,最后求游戏的和

HDOJ2999 Stone Game, Why are you always there? [SG博弈]

构造SG,

HDOJ3595 GG and MM [SG博弈]

Every-SG问题,

HDOJ3980 Paint Chain [SG博弈]

原本是一个环,先染一段,便成链,而且第一步是固定的。环的状态不好处理 。
我们先不管第一步,从链开始,一个链从中间染色就可能砍成两段,便成两个子
问题。后期见http://blog.csdn.net/acm_cxlove/article/details/7840042
最后再把第一步考虑上。

HDOJ4111 Alice and Bob [SG博弈]DP+石子合并

HDOJ4155&ZOJ1827 The Game of 31 [SG博弈]记忆化搜索

搜索,5^6

HDOJ4203 Doubloon Game [找规律][SG博弈]

虽然是普通的SG博弈,不过数据太大,没办法打SG表,只能在小数据中找规律。

HDOJ1524 A Chess Game [有向无环图SG博弈]

和普通SG博弈类似,递归求出后继结点的SG值

HDOJ3094 A tree game [有向无环树形图SG博弈]

树的删边游戏http://blog.csdn.net/acm_cxlove/article/details/7842586

HDOJ3590 PP and QQ [树形SG博弈]反博弈,砍树

树的删边游戏+ANTI-SG,

HDOJ3197 Game [树形SG博弈]砍树

树的删边游戏,把多棵树的根异或起来就行了

=======================================================================

POJ1740 A New Stone Game [找规律]

POJ2484 A Funny Game [找规律]

环形取石子,只要第一步不取完,就变成一条链,那么对手都能从中间取,将其分成
相等的两堆石子

POJ2234 Matches Game [基础Nim博弈]

POJ2975&ZOJ3067 Nim [基础Nim博弈]输出方法

POJ2368 Buttons [巴士博弈变形]

巴什博弈的理解,只要找到总数的因子-1即可。不过因为不能为1,所以对于因子
从3开始,而且对于那种偶数要格外注意

POJ2311 Cutting Game [SG博弈]

对于一个状态n*m,找到后继状态,SG博弈

POJ2425 A Chess Game [SG博弈]

树形,无向无环图博弈

POJ1678 I Love this Game! [动态博弈]动归+博弈

博弈DP,记忆化搜索

POJ2068 Nim [SG博弈]双人博弈

二维博弈DP,

POJ3537 Crosses and Crosses [SG博弈]

每次选择一个位置放下后,左右邻近的4个位置,都不会主动放下棋子。长度为N
的棋盘,如果在位置I放下棋子后,则分为左边I-3个位置和右边N-I-2个位置的子游戏

POJ2599 A funny game [树形SG博弈]记忆化

搜索,N/P的状态转换

POJ3710 Christmas Game [图上博弈]无向图删边

Tarjan算法找出环,处理环之后,便是经典的删边游戏。
拥有奇数条边的环可简化为一条边,偶数条边的环可简化为一个节点。

POJ1704 Georgia and Bob [阶梯博弈]

将之间的距离作为石子堆,对于阶梯博弈,偶数堆不影响,相当于奇数堆的NIM。

POJ2931 Procrastination [不平等博弈]

跪舔,题目看不懂,论文看不懂。
有兴趣的可以看方展鹏论文,《浅谈如何解决不平等博弈问题》

POJ3533 Light Switching Game [Nim积]

三维的NIM积

POJ 1085 Triangle War (極大極小搜索+alpha_beta剪枝)

=======================================================================

ZOJ2290 Game [找规律]

FIB博弈

ZOJ2686 Cycle Game [找规律]dfs搜索

直接搜索会超时,我们做一些优化,发现如果某个方向有连续奇数个非0数,那么
先手便可以朝那个方向,每次把数全部取完,对手如果也取完,那么一直下去先
手胜,如果对手不取完,那么先手反向取完,还是先手胜

ZOJ2725 Digital Deletions [找规律]打表

同HDU 1404

ZOJ2083 Win the Game [SG博弈]

SG博弈,将长度为n的线段,分为两部分,i,n-i-2。异或之后取mex操作

ZOJ2507 Let's play a game [反Nim,SG博弈]

ANTI-SG游戏,见http://blog.csdn.net/acm_cxlove/article/details/7839276

ZOJ3513 Human or Pig [SG递推]

递推,P态的所有后继都为H态,否则则为H态

ZOJ3529 A Game Between Alice and Bob [SG博弈]

SG博弈,可以发现SG值便是质因子个数,转换成NIM

ZOJ3591 Nim [Nim博弈]+位运算

先生成序列,nim[i]表示前i个堆的异或值,如果nim[i]==nim[j],则表示
i+1,i+2……j的异或值为0,为必败。

ZOJ3057 beans game [DP博弈]

三维保存状态,博弈DP。注意卡时卡内存

ZOJ1039 Number Game [状压+博弈树]记忆化搜索

状态压缩,将19个数字压缩,充分利用位运算,每次找到后继集合,记忆化搜索

ZOJ3599 Game [K倍博弈]

与HDU 2486 类似,

ZOJ2804 Funny Games [不知道什么类型]

题目看不懂。。。。
=======================================================================

UVA12350 Queen Game [跪舔的博弈]

题目看不懂。。。。

转载于:https://www.cnblogs.com/Sunshine-tcf/p/5733776.html

你可能感兴趣的文章
GridView的RowCommand事件传两个或以上参数
查看>>
剑指Offer编程题2——替换空格
查看>>
ubuntu切换到root
查看>>
MYSQL limit用法
查看>>
Windows7下出现“不支持此接口”的解决方案
查看>>
实现dhtmlxTree树型控件单击展开收缩功能
查看>>
不能在DropDownList 中选择多个项
查看>>
【Unity渲染】Camera RenderToCubemap 渲染到立方体纹理
查看>>
n2n网络穿透内网
查看>>
让“懒惰” Linux 运维工程师事半功倍的 10 个关键技巧!
查看>>
写给自己看的小设计4 - 对象设计通用原则之扩展原则
查看>>
oem 重建
查看>>
LNMP之Nginx
查看>>
构造函数中的异常处理(转)
查看>>
SI Macro
查看>>
jquery动态调整div大小使其宽度始终为浏览器宽度
查看>>
这篇文章主要为大家详细介绍了jQuery密码强度验证控件使用详解的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...
查看>>
寒假作业
查看>>
「Vue」nrm
查看>>
[汇编语言]-第五章段前缀及使用 一段安全的空间
查看>>