51nod 1831 小C的游戏(暴力打表,博弈)

1.0 秒 131,072.0 KB 80 分 5级题

小C和小L是好朋友,她们在玩一个游戏。
一开始有一个大小为n的石子堆,小C先手。
每次可以对这个石子堆拿走一个或者把这个石子堆分成等量的几份并只取其中一份(不能不变或只剩下一个)。
如果取走最后一个人的算败,请问这个游戏小C是否能胜。


一开始理解错题意了,看了讨论区才知道那个只取一份不是取走一份的意思,是留下那一份的意思。。坑啊

一个一个取的话奇偶性就固定了,所以要看什么时候能分了然后就剩下他的因子,这样就会变成一个子问题的求解

n=1先手败,n=2后手败,n=3先手败,n=4后手败(可以变成n=2但先手会输,决定权在先手),n=5先手败,n=6后手败,n=7后手败(后手只能取掉一个变为n=6)

所以直接从小到大暴力求必胜态和必败态,如果可以一步到先手必败态,那么当前就是先手必胜态,n是1e9,找一下1e4内的规律,可以发现质数必败(2、17除外),合数必胜(16,34,289除外)

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<vector>
using namespace std;

#define LL long long
const int N=1005;
int a[N];
void init(){
a[1]=0;a[2]=1;
vector<int> lose;
for(int i=3;i<N;i++){
int flag=1;
if(a[i-1]==0){
a[i]=1;
continue;
}
for(int j=0;j<lose.size();j++){
if(i%lose[j]==0){
a[i]=1;
flag=0;
break;
}
}
if(flag){
a[i]=0;
lose.push_back(i);
}
}
for(int i=1;i<N;i++){
if(a[i]==0)printf("%d ",i);
}
}
bool isprime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
int main(){
int t,n;
// init();
cin>>t;
while(t--){
cin>>n;
if(n==2||n==17)puts("TAK");
else if(n==16||n==34||n==289)puts("NIE");
else if(isprime(n))puts("NIE");
else puts("TAK");
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信