HDU 3544 Alice's Game（贪心博弈）

Alice's Game

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 798    Accepted Submission(s): 357

Problem Description Alice and Bob have got a lot of chocolates. All the chocolates are rectangles of different shapes as X i * Y i.They decide to play an interesting game on the chocolates. They take turns choose a chocolate and split it into two pieces. The one who can not take operations lose. Due to the game is too simple, the additional rules apply. Alice is only allowed to split the chocolate vertically, and Bob is only allowed to split the chocolate horizontally.

Specifically, for Alice, a chocolate X i * Y i, can only split into A * Y i, and B * Y i where A + B = X i and A, B > 0. And for Bob, a chocolate X i * Y i, can only split into X i * A, and X i * B where A + B = Y i and A, B > 0.

Alice and Bob are clever enough to take the optimal operation, if Alice plays first, your are to decide who will win.  

Input The input contains multiple test cases. The first line of input contains a single integer denoting the number of test cases.

For each test case, the first line contains an integer N, the number of pieces of chocolates. (1 <= N <= 100)

For the next N lines, each line contains two integers X i and Y i, denoting the chocolate sized X i * Y i. (1 <= X i, Y i <= 1000000000)  

Output For each test cases, output "Alice" when Alice will win, and "Bob" otherwise. See sample test cases for further details.  

Sample Input

4
1
1 1
1
2 1
2
2 2
2 1
1
3 2
        

Sample Output

Case 1: Bob
Case 2: Alice
Case 3: Alice
Case 4: Bob
        

     题意：给一块n*m的巧克力，Alice只能垂直切，切成A*m和B*m,并且A+B=n,Bob只能横切，只能切成A*n和B*n，并且A+B=m。

     自己的思路：这题我想到了，如果要切，肯定切对手是1 的情况，否则对手大于1，肯定就多让人切了一倍。。。自己也不能尽量切出1来，因为自己切出1来就让对手抓住机会切这个了。。所以为了减少自己切出1 的可能性，尽量平分着切，推迟自己切到1的情况，在这期间看看能不能耗到对手切到不了了。。这题自己想到了平分着切，可就是做不出来，就是捅不破那层窗户纸，就差一点点。。。其实就是每一块巧克力，假设他们都是平分着切，看谁先切到1，就变成n，1这种情况了，这样自己就多出了n-1次切法，每一个巧克力都这样，看谁总的多出来的次数最多就赢了。。。就是把这种策略分到每一块巧克力就行。。。就是突破不了这个瓶颈。。

     网上的思路：谁都不希望给对手1 × n（或者n × 1）的情况，因为这样对手就会比我多出n - 1步可以走，所以为了推迟1 × n（或者n × 1）这种情况的到来，在分的时候就要平分，然后后面的人要选小块的来分 。因为是平分，那么只要看平分后的其中一块就可以，因为其他块也是一样的情况，最后只要分到n × 1（或者1 × n）这种情况出现就可以定胜负了。还要注意，谁面对n × n这种情况一定是输的。

本题我抄袭自《Winning Ways for your Mathematical Plays》 ，一本关于游戏论的科 

普类图书。 

这题是一个组合游戏，但是并不是一个对等的组合游戏，所以试图使用 SG 函数相关知 

识解答是会面临巨大的挑战的。 书中本题的做法描述得十分简单， 当然对于有这类组合游戏 

知识的同学来说这题也确实十分简单，如果没有相关背景知识，也没有关系，我们来慢慢分 

析这道题目。 

要成功地解答本题需要认真地分析这个游戏的规则，我们首先来考虑一些简单情况。 

（1） 只有 n*1 和 1*m 的巧克力的时候 

（2） 2*2 的巧克力 

（3） 2*3 和 3*2 的巧克力 

（4） n*2 和 2*m 的巧克力 

（5） n*3 和 3*m 的巧克力 

（6） 很多巧克力在一起的情况 

我们来一个一个分析这些情况，对于 n*1 和 1*m 的巧克力，显然 n*1 的巧克力对 alice 

有利， 而 1*m 的巧克力对 bob 有利。 假设 n*1 对于 alice 有 n-1 的 HP 贡献， 而 1*m 对于 bob 

有 m-1 的 HP 贡献。至于谁胜利？自然是谁 HP 多谁就胜利，当然考虑到先 alice 先扣 HP， 

所以如果 HP 一样多， alice 也输了。 为了方便， 我们定义 alice 的 HP 为正， bob 的 HP 为负。 

于是这个局面就可以通过简单的加法获得总的 HP 了。 

那 2*2 的巧克力呢， 认真分析就可以发现 2*2 在这个游戏中纯属幻觉！ 谁也不愿意先拿 

他开刀，切一道送了对方两次切的机会，而自己却只切了一刀。于是我们可以说，2*2 的巧 

克力值 0 的 HP。 

同样 2*3 和 3*2 的巧克力也因为同样的道理就这么被无情地抛弃了。 

对于 n*2 的巧克力，根据直觉 alice 应该感到很高兴（当然不是 1*2） ，bob 自然不会傻 

到来切这个巧克力， 于是 alice 自己要想办法自己尽量多切几刀， 注意到切出 1*2 的巧克力 

是很不利的事情，于是每次都切 2*2 的，可以切(n/2)-1 刀。于是这就是 n*2 的巧克力的 HP 

贡献了。2*m 以及 n*3，3*m 的就不再赘述，都是一样。 

以此类推，4*4，8*8，16*16，都是比较关键的巧克力。

弄一个表吧，再找不到规律„„

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

看表格就知道 HP(i,j)=HP(i2,j2)  

然后 HP(1,j) 和 HP(i,1) 都是直接求的。代码不贴了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e9 + 7;
int main()
{
    int x, y, n, t, Case = 0;
    scanf("%d", &t);
    while(t--)
    {
        long long ansx = 0, ansy = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%d", &x, &y);
            while(x > 1 && y  > 1)
            {
                x /= 2;
                y /= 2;
                ansx++;
                ansy++;
            }
            if(x == 1) ansy += y - 1;
            if(y == 1) ansx += x - 1;
        }
        if(ansx <= ansy) printf("Case %d: Bob\n", ++Case);
        else printf("Case %d: Alice\n", ++Case);

    }


    return 0;
}