博弈论系列

简单入门题：

（勇敢者的游戏）各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的： 1、 本游戏是一个二人游戏; 2、 有一堆石子一共有n个； 3、 两人轮流进行; 4、 每走一步可以取走1…m个石子； 5、 最先取光石子的一方为胜； 如果游戏的双方使用的都是最优策略，请输出哪个人能赢。 Input: 输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。 每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。 Output: 如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。 Sample Input: 2 23 2 4 3

Sample Output:

first second

分析：

简单的巴什博奕，根据公式：n = ( m + 1 ) * r + s ,若s 不为0，则先取者只要先取走s ,那么它就稳赢了；

如果s为0的话，那就输定了，先手如果取k,则后手只要去m+1-k，先手迟早会面对m+1个石头子，就输了。

代码：

#include<stdio.h> int main() { int c,n,m; scanf("%d",&c); while(c--) { scanf("%d%d",&n,&m); if(n%(m+1)==0) printf("second\n"); else printf("first\n"); } return 0; } View Code

 

HD2149Public Sale

Problem Description

虽然不想，但是现实总归是现实，Lele始终没有逃过退学的命运，因为他没有拿到奖学金。现在等待他的，就是像FarmJohn一样的农田生涯。 要种田得有田才行，Lele听说街上正在举行一场别开生面的拍卖会，拍卖的物品正好就是一块20亩的田地。于是，Lele带上他的全部积蓄，冲往拍卖会。 后来发现，整个拍卖会只有Lele和他的死对头Yueyue。 通过打听，Lele知道这场拍卖的规则是这样的：刚开始底价为0，两个人轮流开始加价，不过每次加价的幅度要在1～N之间，当价格大于或等于田地的成本价 M 时，主办方就把这块田地卖给这次叫价的人。 Lele和Yueyue虽然考试不行，但是对拍卖却十分精通，而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。 由于Lele字典序比Yueyue靠前，所以每次都是由Lele先开始加价，请问，第一次加价的时候， Lele要出多少才能保证自己买得到这块地呢？

Input

本题目包含多组测试，请处理到文件结束(EOF)。每组测试占一行。 每组测试包含两个整数M和N(含义见题目描述，0<N，M<1100)

Output

对于每组数据，在一行里按递增的顺序输出Lele第一次可以加的价。两个数据之间用空格隔开。 如果Lele在第一次无论如何出价都无法买到这块土地，就输出"none"。

Sample Input

4 2 3 2 3 5

Sample Output

1 none

3 4 5

/*巴什博弈基本思想：两人在限制（1~n）的条件下，谁先达到m谁胜出。则分情况讨论：1.当n>=m时，先手必胜2.当m=n+1时，先手必败；3.当m%(n+1)==0时，先手必败，因为后手只要每次保持m是n+1的倍数，就会出现情况2，4.当m%(n+1)!=0时，先手胜，因为先手只要每次保持m是n+1的倍数，就会出现情况1，

*/

代码：

#include<iostream> using namespace std; int main(){ int n,m,i; while(cin>>m>>n) { if(m%(n+1)==0) cout<<"none"<<endl; else { if(m<n) { cout<<m; for(i=m+1;i<=n;i++) cout<<" "<<i; } else cout<<m%(n+1); cout<<endl; } } return 0; } View Code

 

转载于:https://www.cnblogs.com/LZYY/p/3439662.html

相关资源：JAVA上百实例源码以及开源项目