hdu1846巴什博弈(java)

简介: 有一堆石子一共有 n 个,两人轮流进行,每走一步可以取走 1…m 个石子,最先取光石子的一方为胜。对于博弈的理解,就是围绕找必胜点和必败点而解决问题,首先分析m

有一堆石子一共有 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();
    }
  }
}


目录
相关文章
|
消息中间件 RocketMQ
Centos7.6安装RocketMQ4.9.2并配置开机自启
Centos7.6安装RocketMQ4.9.2并配置开机自启
938 0
|
网络协议 安全 网络安全
你了解计算机网络的发展历史吗?
你了解计算机网络的发展历史吗?
|
架构师 Java 开发者
阿里最新丰碑:国内第一本凤凰架构,全面构建可靠大型分布式系统
周志明老师的《深入理解Java虚拟机》想必大家都不陌生,这本书凭借着生动易懂的文风、系统实用的知识点、成为原创计算机图书经典中的经典。周老师凭借一己之力拉高了Java开发者内功水平,把JVM带到了初级面试题环节。
|
Arthas 监控 Java
【Java虚拟机】JVM诊断神器Arthas入门实操
【Java虚拟机】JVM诊断神器Arthas入门实操
【Java虚拟机】JVM诊断神器Arthas入门实操
|
前端开发 C++
qt 如何设计好布局和漂亮的界面。
qt 如何设计好布局和漂亮的界面。
1808 2
qt 如何设计好布局和漂亮的界面。
|
Python
Python 再说勾股树,这次整一棵五彩的任意“生长”的分形树!
Python 再说勾股树,这次整一棵五彩的任意“生长”的分形树!
646 0
|
SQL 存储 算法
彻底掌握 MySQL InnoDB 的锁机制
彻底掌握 MySQL InnoDB 的锁机制
ERROR: Could not install packages due to an Oserror: [Errno 13] Permission denied: RECORD Consider
ERROR: Could not install packages due to an Oserror: [Errno 13] Permission denied: RECORD Consider
1935 0
ERROR: Could not install packages due to an Oserror: [Errno 13] Permission denied: RECORD Consider
|
分布式计算 搜索推荐 NoSQL
|
存储 JSON NoSQL
暂缓MongoDB 4.4.2 、4.4.3、 4.4.4版本升级: 存在严重Bug
暂缓MongoDB 4.4.2 、4.4.3、 4.4.4版本升级: 存在严重Bug
478 0
暂缓MongoDB 4.4.2 、4.4.3、 4.4.4版本升级: 存在严重Bug