题意
有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出2堆石子的数量，问最后谁能赢得比赛。
思路
枚举小数字的a,b，发现必败态有如下规律：
- 每组必败态两数之差为1，2，3...
- 必败态任意数字不重复
于是可以递推(1,2),(3,5)(4,7),(6,10)...
暴力可做，另有公式较小数a==(b-a)*1.618时为必败态。
1.618具体为(sqrt(5)+1)/2，V2必须用这个公式和高精，未做，日后再做。
代码
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll T,a,b;
int c[5000020];
bool f[50000200];
ll abs(ll x){
return x>0?x:-x;
}
void fun(){
memset(f,false,sizeof(f));
int cnt=1;
for(int i=1;i<=5000000;i++){
if(!f[i]&&!f[i+cnt]){
c[i]=i+cnt;
f[i]=f[i+cnt]=true;
cnt++;
}
}
}
int main(){
fun();
cin>>T;
while(T--){
cin>>a>>b;
if(b<a) swap(a,b);
if(c[a]==b) cout<<"B\n";
else cout<<"A\n";
}
return 0;
}
|