巴什博弈入门

http://acm.hdu.edu.cn/showproblem.php?pid=1847

http://acm.hdu.edu.cn/showproblem.php?pid=2149

这两个是巴什博弈的入门题，这个还是挺简单的

所谓的巴什博弈大概是这样的

只有一堆n个物品，每次每个人从中取M（>=1）个，先取完的人胜利，问谁能胜利

当n = m+1的时候，无论前面一个人取多少个，后取的人都可以胜利

所以，当n=(m+1)*r+s的时候，前面的人必定可以胜利

因为第一次取S，然后就相当于交换了先后手，无论后面的人怎么取，你都可以构成一个m+1

所以前面的人必胜。 2149是这个类型

1847这种，每次取的都是2的次方，但是由于每一个数，都可以由2的次方的和构成（十进制和二进制的转换）

所以当你取走后，留下3的倍数的时候，你必赢

因为如果还有3张牌，那么对面的只能取一张或者两张，剩下的你都可以一次性取完

如果还有3的倍数的话，剩下的一定是还有3*k+1或者3*k+2张，你又可以构造出3*k

反正如果一开始就是3的倍数的话，那么你必输

 1 //2149
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 int main()
 6 {
 7     int a,b;
 8     while(~scanf("%d%d",&a,&b))
 9     {
10         if(a<=b)
11         {
12              for(int i = a;i<b;i++)
13                 printf("%d ",i);
14                 printf("%d
",b);
15         }else {
16             if(a%(b+1))
17                 printf("%d
",a%(b+1));
18             else printf("none
");
19         }
20     }
21     return 0;
22 }
23 //1847
24 #include <stdio.h>
25 #include <string.h>
26 
27 int main()
28 {
29     int a;
30     while(~scanf("%d",&a))
31         if(a%3)
32             printf("Kiki
");
33         else
34             printf("Cici
");
35     return 0;
36 }

相关推荐