4005. 取石子游戏

article/2024/6/24 18:35:27

Powered by:NEFU AB-IN

Link

文章目录

  • 4005. 取石子游戏
    • 题意
    • 思路
    • 代码

4005. 取石子游戏

  • 题意

    Alice 和 Bob 正在玩一个取石子游戏。
    共有 n个石子,双方轮流采取行动。
    每当轮到一人行动时,该名玩家需要从石子堆中取走恰好 1或 2或 k个石子。
    如果轮到一人行动时,已经没有石子可取,则该名玩家失败。
    已知,双方都会采取最优策略,且 Alice 率先行动。
    请问,最终谁将获胜。

  • 思路

    具体思路可以参考这篇博客 link
    ps: 这篇博客的循环节找的不能说错,但最好是从0开始,如 0,1,2,30,1,2,30,1,2,3

    遇到这种单堆石子博弈论问题,可以通过sg函数打表的方式找规律求解
    比如这个题,就可以枚举k的取值,然后将sg值打表打出来找规律

  • 代码

    打表代码

    '''
    Author: NEFU AB-IN
    Date: 2023-03-25 18:49:28
    FilePath: \Acwing\4005\4005.py
    LastEditTime: 2023-03-25 18:54:33
    '''
    read = lambda: map(int, input().split())
    from collections import Counter, deque
    from heapq import heappop, heappush
    from itertools import permutationsN = int(1e3 + 10)
    INF = int(2e9)
    f = [-1] * N
    # 打表代码def sg(x):if f[x] != -1:return f[x]d = Counter()for i in lst:if x >= i:d[sg(x - i)] = 1for i in range(INF):if d[i] == 0:f[x] = ireturn f[x]k = int(input())lst = [1, 2, k]for i in range(0, 20):print(i, sg(i))
    

    正式代码

    '''
    Author: NEFU AB-IN
    Date: 2023-03-25 18:57:14
    FilePath: \Acwing\4005\4005.1.py
    LastEditTime: 2023-03-25 19:00:55
    '''
    read = lambda: map(int, input().split())
    from collections import Counter, deque
    from heapq import heappop, heappush
    from itertools import permutationsN = int(1e3 + 10)
    INF = int(2e9)
    # 正式代码for _ in range(int(input())):n, k = read()if k % 3:if n % 3:print("Alice")else:print("Bob")else:ys = n % (k + 1)if ys % 3 == 0 and ys != k:print("Bob")else:print("Alice")
    

http://www.ngui.cc/article/show-1007720.html

相关文章

一维与二维前缀和(蓝桥杯复习+例题讲解+模板c++)

文章目录前缀和二维前缀和总结3956. 截断数组99. 激光炸弹文章首发于: My Blog 欢迎大佬们前来逛逛前缀和 前缀和是一种常见的算法,用于快速计算数组中某一段区间的和。前缀和的思想就是预处理出数组中前缀和,然后用后缀和减去前缀和&#x…

【零基础入门SpringBoot2】—— Web开发_3

一、Web原生组件注入 如何向SpringBoot中注入Web的原生组件? 1、使用Servlet API (1)Servlet原生组件 创建一个Servlet类,让它继承原生的Servlet的实现类 HttpServlet ,使用WebServlet注解指定我们的请求,…

MobaXterm 链接Linux Ubuntu

MobaXterm 链接Linux Ubuntu 1.查看是否安装 openssh-server sudo apt-get install open-server2.开启ssh服务 sudo /etc/init.d/ssh start3.查看虚拟机的IP ifconfig5.打开MobaXterm 将ip输入即可 如果传输文件,选择SFTP,步骤和上面一样

c++加解密算法总结

不可逆加密 概述 单向加密,主要是对明文的保密和摘要提取。算法包括MD5、SHA、HMAC等。 特点 压缩性:任意长度的数据,单向加密后长度都是固定的;抗修改性:对原数据进行任何改动,哪怕只修改1个字节&…

JAVA Session会话 Thymeleaf - 视图模板技术配置步骤

JAVAWebSession会话会话跟踪技术session保存作用域Thymeleaf - 视图模板技术配置过程Session会话 HTTP是无状态的:服务器无法区分这两个请求是同一个客户端发过来的,还是不同的客户端发过来的 现实问题:第一次请求是添加商品到购物车&#x…

model.train()、model.eval()什么时候用

model.train() 在使用 pytorch 构建神经网络的时候,训练过程中会在程序上方添加一句model.train(),作用是 启用 batch normalization 和 dropout 。 如果模型中有BN层(Batch Normalization)和 Dropout ,需要在训练时…

Mac M1/Intel 芯片 Nginx+PHP开发环境配置——初探(一)

最近因为新买Mac M系列芯片笔记本,一直也没搭建过PHP的开发环境,花了一点时间特意在本机做了一次环境搭建测试具体如下。开始之前,需要安装一些工具来完成配置,工具列表如下:XcodeVS CodeHomebrewOpenSSL & wgetMySQLPostgres…

Spring《二》bean的实例化与生命周期

🍎道阻且长,行则将至。🍓 目录一、bean实例化🍍1.构造方法 ***2.静态工厂 *使用工厂创建对象实例化bean3.实例工厂 ***使用示例工厂创建对象实例工厂实例化beanFactoryBean二、生命周期🍑1.生命周期设置2.在main方法使…

Vector - CAPL - 实时时间on *

前面有简单的提到过on message的用法,但是对于整个on *家族来说,on message仅仅这是其中之一,为了能够的了解、学习这个家族的成员,因此做了专门的整理的,将囊括CALP用常用的所有的on *家族成员,并对其进行…

【JavaEE】Java设计模式-单例模式(饿汉式与懒汉式)

目录 1.设计模式是啥? 2.单例模式 2.1什么是单例模式 2.2饿汉模式 2.3懒汉模式 3.懒汉模式与饿汉模式的区别 1.设计模式是啥? 设计模式是前人经过总结,通过对不同应用场景应该运用何种方法解决问题的模式。我们可以将它看成NBA中的…