B.HDU 1846 Brave Game
算是最简单的入门博弈题吧......
呃......我用的......算是不是方法的方法吧——找规律~
可以发现：X-M为奇数时，先手会输；而为偶数的时候，先手会赢~
代码：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5
6 int main()
7 {
8 int t,x,y;
9 scanf("%d",&t);
10 while(t--)
11 {
12 scanf("%d%d",&x,&y);
13 int k=y+1;
14 if(x%k==0)
15 printf("second\n");
16 else
17 printf("first\n");
18 }
19 return 0;
20 }
//memory：268KB time：0ms
C.HDU 1527 取石子游戏
哎~肿么讲这道题呢~比赛的时候已经找出规律了......但是不知道怎么判断输入的数是规律里的数~= =
我做这道题时，可以很容易就发现，先手赢的几率很明显比后手大很多，因此就找出后手赢的情况【用（a,b）表示，且a<b】：
显然（1，2）（3,5）（4,7）（6,10）（8，13）.......(ai,bi)【i从1开始】
ai是前面还未出现的数字的最小值，而bi则是ai+i......
T v T推到这一步，就不知该如何是好了= =结果看了网上的代码.......想死的心都有了......我肿么没想到除法...我肿么没想到黄金分割比= =，高中的数学都退给老师了么T T
接着我上面的想法，就差这临门一脚——a(k) = k * (1 + sqrt(5))/2 b(k)=a(K)+K;
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; int main()
{
int a,b,k;
while(~scanf("%d%d",&a,&b))
{
if(a<b)
{
int t=a;
a=b;
b=t;
}
k=a-b;
a=(int)(k*(+sqrt(5.0))/2.0);
if(a==b)
printf("0\n");
else
printf("1\n");
}
return ;
}
//memory：240KB time：15ms