8-14-Exercise（博弈：HDU 1846 & HDU 1527 ）

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

巴特西

8-14-Exercise（博弈：HDU 1846 & HDU 1527 ）

最新文章

热门文章