UVA12293 Box Game —

题目链接：https://vjudge.net/problem/UVA-12293

题意：

两人玩游戏，有两个盒子，开始时第一个盒子装了n个球，第二个盒子装了一个球。每次操作都将刷量少的盒子的球倒掉，然后再从数量多的盒子中拿出若干个球放到空盒子里，最终状态为（1,1），达到这个状态的玩家获胜。

题解：

1.由于每次都是倒掉数量少的那个盒子，再对数量多的盒子进行分割，所以可以把规则简化为：初始时有n个球，每次只能拿走不多于n/2的球，最终状态为1个球，达到这个状态的玩家获胜。

2.简化游戏规则之后，可知这是一个典型的SG博弈，但是由于n的范围很大，不能直接求SG值，那就打表找规律，如下：

可知，当n为 2^i - 1时，先手输；否则先手赢。

代码一：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = +;

 int SG[MAXN], vis[MAXN];

 void table()

 {

     SG[] = ;

     for(int i = ; i<=; i++)

     {

         memset(vis, , sizeof(vis));

         for(int j = (i+)/; j<i; j++) vis[SG[j]] = ;

         for(int j = ;;j++) if(!vis[j]) {

             SG[i] = j;

             break;

         }

     }

     for(int i = ; i<=; i++) printf("%-2d ",i); putchar('\n');

     for(int i = ; i<=; i++) printf("%-2d ",SG[i]); putchar('\n');

 /*

     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

     0  1  0  2  1  3  0  4  2  5  1  6  3  7  0  8  4  9  2  10 5  11 1  12 6  13 3  14 7  15 0  16

 */

 }

 bool judge(int x)

 {

     x++;

     int bit = ;

     while(x)

     {

         bit += x&;

         x >>= ;

     }

     return bit==;

 }

 int main()

 {

 //    table();

     int n;

     while(scanf("%d", &n) &&n)

     {

         if(judge(n)) printf("Bob\n");

         else printf("Alice\n");

     }

 }

代码二：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = +;

 int SG[MAXN], vis[MAXN];

 void table()

 {

     SG[] = ;

     for(int i = ; i<=; i++)

     {

         memset(vis, , sizeof(vis));

         for(int j = (i+)/; j<i; j++) vis[SG[j]] = ;

         for(int j = ;;j++) if(!vis[j]) {

             SG[i] = j;

             break;

         }

     }

     for(int i = ; i<=; i++) printf("%-2d ",i); putchar('\n');

     for(int i = ; i<=; i++) printf("%-2d ",SG[i]); putchar('\n');

 /*

     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

     0  1  0  2  1  3  0  4  2  5  1  6  3  7  0  8  4  9  2  10 5  11 1  12 6  13 3  14 7  15 0  16

 */

 }

 int main()

 {

 //    table();

     int n;

     while(scanf("%d", &n) &&n)

     {

         if(n&(n+)) printf("Alice\n");

         else printf("Bob\n");

     }

 }

巴特西

UVA12293 Box Game —— SG博弈

最新文章

热门文章