首页 > 其他 > 详细

巴什博奕

时间:2021-09-21 01:00:47      阅读:11      评论:0      收藏:0      [点我收藏+]

定每次至少取一个,最多取m个。最后取光者得胜。

    显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果n=(m+1)*r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。
    这个游戏还可以有一种变相的玩法:两个人轮流报数,每次至少报一个,最多报十
个,谁能报到100者胜。

 

HDU 1846

各位勇敢者要玩的第一个游戏是什么呢?很简单,它是这样定义的:
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个;
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子;
5、 最先取光石子的一方为胜;

如果游戏的双方使用的都是最优策略,请输出哪个人能赢。

 

Sample Input
2
23 2
4 3

Sample Output
first
second

 

技术分享图片
技术分享图片
 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std ;
 4 
 5 int a[110] ;
 6 
 7 int main ()
 8 {
 9     int T ;
10     scanf("%d" , &T) ;
11     while (T--)
12     {
13         int n , m ;
14         scanf("%d %d" , &n , &m) ;
15         if (n % (m+1) == 0)
16           printf("second\n") ;
17         else
18           printf("first\n") ;
19     }
20     
21     
22     
23 }
技术分享图片

 

HDU 2149 拍卖

刚开始底价为0,两个人轮流开始加价,不过每次加价的幅度要在1~N之间,当价格大于或等于田地的成本价 M 时,主办方就把这块田地卖给这次叫价的人。第一次加价的时候,
Lele要出多少才能保证自己买得到这块地呢?

思路:一堆数量为M的石子,每次只能拿1-N ,当N >= M 先手可以一次拿完

Sample Input
4 2 // m n
3 2
3 5

Sample Output
1
none
3 4 5

技术分享图片 View Code

 

HDU 2188 捐款

选拔规则如下:
1、最初的捐款箱是空的;
2、两人轮流捐款,每次捐款额必须为正整数,并且每人每次捐款最多不超过m元(1<=m<=10)。
3、最先使得总捐款额达到或者超过n元(0<n<10000)的一方为胜者,则其可以亲赴灾区服务。
我们知道,两人都很想入选志愿者名单,并且都是非常聪明的人,假设林队先捐,请你判断谁能入选最后的名单?

如果林队能入选,请输出字符串"Grass", 如果徐队能入选,请输出字符串"Rabbit"

Sample Input
2
8 10 // n m
11 10

Sample Output
Grass
Rabbit

技术分享图片 View Code

HDU 2147 走棋盘

题目的意思是从棋盘的最右上角到左下角,其中只可以走三个方向, 左边, 下边,左下边,不能移动着失败,问先手是否胜利

Sample Input
5 3
5 4
6 6
0 0

Sample Output
What a pity!
Wonderful!
Wonderful!

//一切博弈都是找规律
//题目的意思是从棋盘的最右上角到左下角,其中只可以走三个方向, 左边, 下边,左下边,不能移动着失败,问先手是否胜利
//根据博弈论的理论,先从左下角开始分析
/*
* 博弈论:组合博弈
* 必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。
* 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。
* 必败(必胜)点的属性:
* (1) 所有终结点是必败点(P点);
* (2) 从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点);
* (3)无论如何操作, 从必败点(P点)都只能进入必胜点(N点).
* 由上面的属性得到该题的算法:
* 步骤1:将所有终结位置标记为必败点(P点);
* 步骤2: 将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)
* 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;
* 步骤4: 如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。
* 由上面的算法计算一个例子:
* 我们可以把问题转换成从(1,1)走到(n,m) (方便等下得出结论)
* 但n=8,m=9的情况
* NNNNNNNNN
* PNPNPNPNP
* NNNNNNNNN
* PNPNPNPNP
* NNNNNNNNN
* PNPNPNPNP
* NNNNNNNNN
* PNPNPNPNP
*初始点(1,1)为N所以输出Wonderful!
*从这里例子就可以很清楚得看出当n和m都为奇数时,初始点(1,1)才会是P。
*因此该题只需判断n,m是否同时为奇数即可。
*/

技术分享图片 View Code

 

HUD 2897 变形BASH

大意:一堆石子共有n个,A,B两人轮流从中取,每次取的石子数必须
在[p,q]区间内,若剩下的石子数少于p个,当前取者必须全部取完。
最后取石子的人输。给出n,p,q,问先取者是否有必胜策略?

Bash博弈的变形
假设先取者为A,后取者为B,初始状态下有石子n个,除最后一次每次取的石子个数必须在[p,q]区间内,则:
1.若当前石子共有n = (p+q)*r个,则A必胜,必胜策略为:
A第一次取q个,以后每次若B取k个,A取(p+q-k)个,如此最后必剩下p个给B,A胜
2.若n = (p+q)*r+left,(1<left<=p),则B必胜,必胜策略为:
每次取石子活动中,若A取k个,则B取(p+q-k)个,那么最后必剩下left个给A,
此时left<=p,A只能一次取完,B胜
3.若n = (p+q)*r+left,(p<left<p+q),则A必胜,必胜策略为:
A第一次取t(1<left-t<=p)个,以后每次若B取k个,A取(p+q-k)个,
那么最后必剩下1<left-t<=p个给B,A胜

 

Sample Input
7 2 4
6 2 4

Sample Output
LOST
WIN

 

技术分享图片 View Code

 

HDU 1847 拿牌的时候只能2的幂次(找规律法 也可用SG大法)

作为计算机学院的学生,Kiki和Cici打牌的时候可没忘记专业,她们打牌的规则是这样的:
1、 总共n张牌;
2、 双方轮流抓牌;
3、 每人每次抓牌的个数只能是2的幂次(即:1,2,4,8,16…)
4、 抓完牌,胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设,哪有不聪明的学生~),并且每次都是Kiki先抓牌,请问谁能赢呢?


Sample Input
1 //n
3

Sample Output
Kiki
Cici

这题如果你是先手,考虑你的必胜态。注意,因为任何正整数都能写成若干个2的整数次方幂之和。由于规定只能取2的某个整数次方幂,只要你留给对手的牌数为3的倍数时,那么你就必赢,因为留下3的倍数时,对手有两种情况:
1:如果轮到对方抓牌时只剩3张牌,对方要么取1张,要么取2张,剩下的你全取走,win!
2:如果轮到对方抓牌时还剩3*k张牌,对手不管取多少,剩下的牌数是3*x+1或者3*x+2。轮到你时,你又可以构造一个3的倍数。 所以无论哪种情况,当你留给对手为3*k的时候,你是必胜的。
题目说Kiki先抓牌,那么当牌数为3的倍数时,Kiki就输了。否则Kiki就能利用先手优势将留给对方的牌数变成3的倍数,就必胜。

技术分享图片 View Code

 

HDU 4764 写数字

题意:
两个人写数字,要求当前个写的数字Y与前一个写的数字X满足:
1. 1 <= Y - X <= k
2. Y要求小于N(第一次取只需满足1<=Y<=k);
不都满足则输。
思路:
可将题目意思理解为取石子(题目有提示),取的石子是有规定的,谁能取到第N-1个,那么就能赢得比赛。
写的数字>=N就输了 所以总石子数为N-1

Sample Input
1 1
30 3
10 2
0 0

Sample Output
Jiang
Tang

Jiang

技术分享图片 View Code

巴什博奕

原文:https://www.cnblogs.com/yf2196717/p/15307324.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!