首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

【 HDU 2177 】取(2堆)石子游戏 (威佐夫博弈)

给定若干组数据:a,b表示两堆的石子数量,求先手还是赢,赢还要求第一步之后的两堆石子数,如果有取相同的方案,先输出。 题解 威佐夫博弈问题。...必的状态(奇异局势):(0,0),(1,2),(3,5),..(a_k,a_k+k)其中a_k是前面未出现过的最小的正整数。 有一些性质:每个正整数在必状态中出现且仅出现一次。...于是可以计算并存储下必状态(X,Y),x[k]为第k个必状态的较小的数,y[i]为必状态中是较小的数i 对应的较大的数,z[i]为必状态中较大的数i 对应的较小的数。...先手的情况就是一开始就是必态,也就是k=b-a,x[k]==a。 先手赢的情况,是将局面变成必态: 取走两个相同的数后,差k不变,若a>x[k],则可变成(x[k],y[x[k]])。...只取第一堆: 若b在它所在的必态中是较大的数(z[b]!=0),且a>z[b],则可变成(z[b],b)。 只取第二堆: 第二堆仍更大:若a在必态中是较小的数(y[a]!

45130

【PAT520 钻石争霸赛】7-6 随机一次 (20分)

为了不让对方意识到你在控制结果,你需要隔 K 次一次,其中 K 是系统设定的随机数。...输入格式:输入首先在第一行给出正整数 N(≤10),随后给出 N 个系统产生的不超过 10 的正随机数 { K​1​​,K​2​​,⋯,K​N​​ },数字间以空格分隔。...这意味着第 i(i=0,1,⋯,N−1)次局之后应该隔 K​i+1​​ 次再让下一个局。如果对方出招太多,则随机数按顺序循环使用。...例如在样例中,系统产生了 3 个随机数 {2, 4, 1},则你需要:赢 2 次, 1 次;赢 4 次, 1 次;赢 1 次, 1 次;然后再次回到第 1 个随机数,赢 2 次, 1 次。...输出格式:对每一个输入的出招,按要求输出赢或局的招式。每招占一行。

31910

博弈论入门之威佐夫博弈

威佐夫博弈 威佐夫博弈是一类经典的博弈问题 有两堆石子,两个顶尖聪明的人在玩游戏,每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子,不能取得人,分析谁会获得胜利 博弈分析...前辈们在对该博弈游戏做了大量的探索之后最终找到了一些非常有意思的性质 下面的内容不想看的可以跳过直接看结论,其实也没啥乱用233,这部分就是为了拓宽视野的 定义先手必的局势为奇异局势,前几个奇异局势为...假设(x,y)为第k个奇异局势 性质: x为前 个奇异局势中没有出现过的最小正整数,y=x+k 打表找规律 任何一个自热数都包含在一个且仅有一个奇异局势中 感觉网上证的都不靠谱,那只好让本蒟蒻亲自下手喽...2)任意自然数仅出现一次 对于(1):反证法,设v这个数没有出现过,那么v可以做一个新的奇异局势的x 对于(2): 反证法 假设数v出现了两次,那么v一定不是所在奇异局势的xx必须之前未出现) 那么v只能同时是两个奇异局势的

1.2K40
领券