首页 > 其他分享 >牛客小白月赛65D题 牛牛取石头 题解

牛客小白月赛65D题 牛牛取石头 题解

时间:2023-01-09 20:12:34浏览次数:70  
标签:65D 博弈论 堆取 先手 题解 牛牛取 long 必胜 这道题

原题链接

第一眼看到这道题,其实很容易会联想到经典的bash game问题
这道题并没有巴什博弈那么复杂,但也算一道比较新颖的博弈论题吧
还是很适合作为一道博弈论入门题的


题目大意
有A/B两堆石子,两名玩家进行取石子比赛,玩法很朴素,就两种取法:
①在A堆取1颗,在B堆取2颗
②在A堆取2颗,在B堆取1颗
谁先无法取石子,谁就输了。
对于每组数据A B,问:
先手必胜,还是后手必胜
(A B 都在long long的数据范围内)


保姆级思路解析

一般来说,如果题目中有类似游戏双方都很聪明这种字眼,
那一定是一道博弈论题,而不是模拟题
那就一定要往先手必胜or后手必胜的角度考虑
那我们再来看看这个游戏过程:
不难发现,每过一个回合相当于:A-3 B-3
然后,两名玩家是不是好像又回到了游戏最开始的状态
此时的状态就等价于开始了一场初始石子数为A-3B-3的游戏
换句话说,对于一组数据(a,b),它的结果和(a-3,b-3)是一样的
这样一想,思维就流淌出来了:这道题肯定和3有关!
接下去我们要考虑,在什么状态下,游戏会结束?
既然要取到不能取为止,玩家就应该把策略聚焦到更少的那一堆上,就会跟容易kill对手
那么取完之后,如果能让更少的一堆数量变为0,就获胜了
(不需要考虑1、1这种终止情况。为什么呢?因为倘若结束时的状态是1、1,那么上一状态换一种取法的结果一定是2、0)
再考虑到:每过一个回合相当于:A-3 B-3
后手必胜的策略就很清晰了,只要较小的数是三的倍数,那么后手必胜
这种情况下,只要先手选①后手选②,先手选②后手选①,那么就能坐等先手完蛋
而当较小数不是3的倍数
先手想要获胜也很简单,如果较小数%3==1,那我先就在这堆取1,
如果%3等于2,那么我就在这堆取2
接下来,此前的先手就变为了较小的数是三的倍数情况下的后手,就坐等。。。
很简单对吧?

标签:65D,博弈论,堆取,先手,题解,牛牛取,long,必胜,这道题
From: https://www.cnblogs.com/zhouzhihao/p/17038414.html

相关文章

  • P8932 [JRKSJ R7] Clock Paradox 题解
    在洛谷上阅读Part0题意简述原题这场月赛我唯一AC的题给出一个字符串\(S\),令\(T=S\),求使用\(S\)的子串插入\(T\),将\(T\)变形的最少的操作次数。且字符串\(S\)......
  • Educational Codeforces Round 141 (Rated for Div. 2) A-C题解
    比赛链接A、MakeitBeautiful一种构造方法:按照从大到小的顺序构造,可以发现前缀和永远大于当前值。但是需要特判存在两个最大值的情况。只需要将最小值与第二位交换位置......
  • P5999 [CEOI2016] kangaroo 题解
    分析一个妙妙的trick。首先原题可以转化成求有多少\(1\simn\)的排列\(p\)满足\(\foralli\in(1,n)\),\(p_i\)两边的数同时小于或大于\(p_i\),且\(p_1=s,p_n=t\)......
  • WC 2018 题解
    A若干套路拼起来的胖题。设这三棵树分别是\(T_1,T_2,T_3\)。沿用“CTSC2017暴力写挂”的思路,对第一棵树点分治,此时要处理的是以\(u\)为中心的一块在\(T_1\)上的连......
  • CF652F 题解
    题意传送门在一个长度为\(m\)的圆环上有\(n\)只初始位置互不相同的蚂蚁,每只蚂蚁的速度都为\(1\),初始方向为顺时针或逆时针;两只运动方向不同的蚂蚁相遇时会调转方向,......
  • Codeforces 1671 F Permutation Counting 题解
    题目链接把\(p_i>p_{i+1}\)的位置个数称为间隔数首先想到一个暴力做法。从小到大挨个添加1-n中的每个数,注意到添加数i时,只能添加到当前序列的最后11个位置中,否则逆序对数......
  • 2018年各大赛事题解
    大多数题解都是口胡,不保证正确性,有错请指出,谢谢。CQOI2018除了“交错序列”和“九连环”两道数学题以外,全是板子题,遭不住了。破解D-H协议BSGS板子题,时间复杂度\(\m......
  • 牛客小白月赛65 D-牛牛取石子(博弈论)
    https://ac.nowcoder.com/acm/contest/49888/D题目大意:一共有两堆石子,第一堆a个,第二堆b个,牛牛(先手)和牛妹轮流取石子:2种方案种挑一种1.第一堆取1个,第二堆取2个2......
  • Atcoder ABC284 前五题题解
    ABC284A-SequenceofStrings题意:有n个字符串\(s_1,s_2,s_3,...,s_n\),要求按\(n,n-1,n-2,...,1\)的顺序输出样例:输入3TakahashiAokiSnuke输出......
  • Codeforces 1305 F Kuroni and the Punishment 题解 (随机算法)
    题目链接首先注意到每个数最多操作1次就能让他变成2的倍数,所以答案\(\len\)。如果我们能枚举[1,1e12]中所有的质数,并对每个质数p求出把数组中所有数都变成它的倍数的最少......