数数字游戏
序号:#117 难度:困难 时间限制:1000ms 内存限制:10M
描述
小爱和小冰是一对好闺蜜,她们都是世界上最聪明的人工智能之一。某一天,他们俩一起玩数数字游戏,规则如下:
- 首先小爱和小冰各说一个目标数字num1num1,num2num2;
- 小爱和小冰轮流报数(小冰报数方法与小爱相同),每次只报一个数,报数者可以选择将这个数报给谁;
- 小爱先开始报数字,把这个数给自己或小冰都行,小爱和小冰各自得到的所有数之和不能超过自己的目标数字;
- 最终,谁再也报不出符合条件的数字谁就算输,另一个人就赢(即谁报完数后,两人所得数字之和都达到了各自的目标数字,谁就赢);
- 由于两人智商都是非常的高,所以觉得游戏太简单了,于是两人决定每次报的数只能是斐波那契数列中的元素(例如每次取1,2,3,5,8.......) 。
现在两人各说一个目标数字后请你判断谁会赢。如果小爱赢则输出"Xiaoai Win"
,反之小冰赢输出"Xiaobing Win"
。两人都很聪明,都会使用最优策略(每次报数是最优的)。
规定:斐波那契数列F(1)=1,F(2)=2,F(N)=F(N-1)+F(N-2)F(1)=1,F(2)=2,F(N)=F(N−1)+F(N−2)
输入
两个正整数,用空格隔开,分别表示小爱和小冰的目标数字num1num1,num2num2。
数据范围:num1,num2 < =10000num1,num2<=10000
输出
输出 "Xiaoai Win" 或 "Xiaobing Win",分别表示小爱赢或小冰赢。
输入样例
1 4
3 4
4 4
1 5
复制样例
输出样例
Xiaoai Win
Xiaoai Win
Xiaobing Win
Xiaobing Win
题意:不解释:
题解:sg函数搞一发就好了,怪自己太菜,当时没想到~~~~sg不太懂啊啊啊!!
上代码:
//小米那个OJ不能写子函数和全局,只能在规定的地方写,我也很醉,我这里按好看写的,改一下就过~~
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 1e4+10;
int f[MAX],sg[MAX],hash[MAX];
void getsg(int n){//sg函数模板,不懂就记住吧孩子~~~
memset(sg,0,sizeof(0));
for (int i = 1; i <= n;i++){
memset(hash,0,sizeof(hash));
for (int j = 1; f[j] <= i;j++){
hash[sg[i-f[j]]]=1;
}
for (int j = 0; j <= n;j++){
if(hash[j]==0){
sg[i]=j;
break;
}
}
}
}
int main(){
f[0]=f[1]=1;
for (int i = 2; i <= 20;i++){
f[i]=f[i-1]+f[i-2];
}
getsg(10000);
int num1,num2;
while(cin >> num1 >> num2){
if((sg[num1]^sg[num2])==0) cout << "Xiaobing Win" << endl;//注意:异或需要加括号
else cout << "Xiaoai Win" << endl;
}
return 0;
}