hdu1846巴什博弈（java）

题目链接
有一堆石子一共有 n 个，两人轮流进行,每走一步可以取走 1…m 个石子,最先取光石子的一方为胜。
对于博弈的理解，就是围绕找必胜点和必败点而解决问题，首先分析m
1：m>=n先走必赢
2：m+ 1=n先走必输，因为只能拿1-m个，那么剩下的一定可以直接拿完
3：m +1>n时候，换位思考，如果我是第二拿，我只想剩m +1一定能赢，如果我是先拿，我想让我成为可选择的第二状态，所以先取者就想取到剩（m +1）的倍数为止，因为剩下m+ 1倍数，无论第二个人怎么拿，第一个人总能拿完，总剩下m+1的倍数，所以是必胜态。但是这也不是绝对的，因为都选择最优策略，所以一旦刚开始就是m +1的倍数，那么先拿的人就凉了。状态就转移了。
附上代码，暑假写的题目，顺便复习一下

/*
 * 巴士博弈
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class hdu1846 {

	public static void main(String[] args) throws IOException {
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int k=(int)in.nval;
		for(int i=0;i<k;i ++ )
		{ in.nextToken();int n=(int)in.nval; in.nextToken();int m=(int)in.nval; if(n%(m +1)!=0) {out.println("first");} else out.println("second"); out.flush();
		}
	}
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/82825743