文章目录
- 一、题目
- 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总讲解视频
- k不是3的倍数
- n不是3的倍数,先手必胜。
- n是3的倍数,先手必败。
- k是3的倍数,计算n%(k+1)的余数r
- r和k相等或r不是3的倍数,先手必胜。
- r<k而且r是3的倍数,先手必败。
2. 打表找规律
2、时间复杂度
时间复杂度为O(n)
3、代码详解
正解
#include <iostream>
using namespace std;
int T,n,k;
int main(){cin>>T;while(T--){cin>>n>>k;if(k%3){if(n%3) cout<<"Alice"<<endl;else cout<<"Bob"<<endl;}else{int r=n%(k+1);if(r==k||r%3) cout<<"Alice"<<endl;else cout<<"Bob"<<endl;}}return 0;
}
打表找规律
#include <iostream>
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<<f[i]<<' ';return 0;
}
三、知识风暴
博弈论