【蓝桥杯集训·每日一题】AcWing 4005. 取石子游戏
创始人
2025-05-30 01:56:48
0次

文章目录

  • 一、题目
    • 1、原题链接
    • 2、题目描述
  • 二、解题报告
    • 1、思路分析
      • 1. 正解
      • 2. 打表找规律
    • 2、时间复杂度
    • 3、代码详解
  • 三、知识风暴
  • 博弈论

一、题目

1、原题链接

4005. 取石子游戏

2、题目描述

Alice 和 Bob 正在玩一个取石子游戏。

共有 n 个石子，双方轮流采取行动。

每当轮到一人行动时，该名玩家需要从石子堆中取走恰好 1 或 2 或 k 个石子。

如果轮到一人行动时，已经没有石子可取，则该名玩家失败。

已知，双方都会采取最优策略，且 Alice 率先行动。

请问，最终谁将获胜。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含两个整数 n,k。

输出格式

每组数据输出一行结果，如果 Alice 获胜，则输出 Alice，否则输出 Bob。

数据范围

前三个测试点满足，1≤T≤10。
所有测试点满足，1≤T≤100，0≤n≤109，3≤k≤109。

输入样例：

4
0 3
3 3
3 4
4 4

输出样例：

Bob
Alice
Bob
Alice

二、解题报告

1、思路分析

思路来源：y总讲解视频
y总yyds

1. 正解

  • 先手必胜态：可以走到一个必败态。
  • 先手必败态：走不到任何一个必败态。

直接给出结论：具体证明过程见y总讲解视频

  1. k不是3的倍数
    1. n不是3的倍数，先手必胜。
    2. n是3的倍数，先手必败。
  2. k是3的倍数，计算n%(k+1)的余数r
    1. r和k相等或r不是3的倍数，先手必胜。
    2. r

2. 打表找规律

2、时间复杂度

时间复杂度为O(n)

3、代码详解

正解

#include 
using namespace std;
int T,n,k;
int main(){cin>>T;while(T--){cin>>n>>k;if(k%3){if(n%3) cout<<"Alice"<int r=n%(k+1);if(r==k||r%3) cout<<"Alice"<

打表找规律

#include 
using namespace std;
const int N=110;
int n,k;
int f[N];
int main(){cin>>n>>k;f[0]=0;for(int i=1;i<=n;i++){int d[]={1,2,k};for(int j=0;j<3;j++){int x=d[j];if(i>=x&&!f[i-x]) f[i]=1;}}for(int i=0;i<=n;i++) cout<

三、知识风暴

博弈论

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：FPGA实现Flash读写操作

下一篇：十大排序算法极简汇总篇

相关内容

热门资讯

总算了解开挂!众乐乐开挂AI攻... 总算了解开挂!众乐乐开挂AI攻略,众乐乐多功能都是存在有开挂攻略1、上手简单，内置详细流程视频教学，...
程序员教你辅助!英豪娱乐城辅助... 程序员教你辅助!英豪娱乐城辅助AI工具,英豪娱乐城多功能原来真的是有辅助工具暗藏猫腻，小编详细说明英...
盘点几款辅助!冰球突破辅助AI... 盘点几款辅助!冰球突破辅助AI插件,冰球突破多功能其实真的有辅助插件1、冰球突破脚本辅助下载、冰球突...
分享一款辅助器!建湖好运麻将辅... 分享一款辅助器!建湖好运麻将辅助器AI教程,建湖好运麻将多功能竟然真的是有辅助器教程1、在建湖好运麻...
每日必备透视挂!新老夫子透视挂... 每日必备透视挂!新老夫子透视挂AI技巧,新老夫子多功能原来真的有透视挂技巧1、新老夫子脚本辅助下载、...
分享认知作弊器!星际互联作弊器... 分享认知作弊器!星际互联作弊器AI方法,星际互联多功能都是存在有作弊器方法1、每一步都需要思考，不同...
玩家必备攻略作弊器!闲逸斗地主... 玩家必备攻略作弊器!闲逸斗地主作弊器AI方法,闲逸斗地主多功能果然是有作弊器方法1、闲逸斗地主透视辅...
分辨真假透视挂!宁波游戏大厅透... 分辨真假透视挂!宁波游戏大厅透视挂AI软件,宁波游戏大厅多功能一直是有透视挂软件1、让任何用户在无需...
每日必看教程透视挂!君悦来透视... 每日必看教程透视挂!君悦来透视挂AI工具,君悦来多功能本来是有透视挂工具1、上手简单，内置详细流程视...
发现一款外挂!半岛外挂AI工具... 发现一款外挂!半岛外挂AI工具,半岛多功能一贯真的有外挂工具1、起透看视 半岛辅助软件价格2、随意选...