首页 > ACM题库 > HDU-杭电 > HDU 4023-Game-博弈论-[解题报告]HOJ
2015
04-15

HDU 4023-Game-博弈论-[解题报告]HOJ

Game

问题描述 :

Alice and Bob are playing game with each other. They play the game on a 2D board. Alice has many vertical 1*2 tiles while Bob has many horizontal 2*1 tiles. They take turn to place their own tiles on the board. Considering about that the tiles cannot overlap each other, the player cannot do the placement any more loses. Since this is such a complex game that they could not find optimal method to play that, Alice decide to simplify this game by replace the large 2D board by some small ones. Alice set up a lot of Tetris tiles instead of the original 2D board. In the other words, the player can only place their own vertical or horizontal tiles on the Tetris-like board. Each player can choose one possible place on any Tetris tiles to place its own tiles. In fact, there are following 15 types of Tetris playground.
Bombing

The playground cannot be transformed in any ways, including reflection and rotation.
Given the number of each type of tiles, you are asked to determine who will win the game if Alice plays first and both players are playing optimal.

输入:

There are multiple test cases; the first line of input contains a single integer denoting the number of test cases.
For each test case, there are only one line contains 15 integers denoting the number of Tetris tiles of the above 15 types. All the numbers are no greater than 100.

输出:

There are multiple test cases; the first line of input contains a single integer denoting the number of test cases.
For each test case, there are only one line contains 15 integers denoting the number of Tetris tiles of the above 15 types. All the numbers are no greater than 100.

样例输入:

3
5 4 0 0 0 0 0 0 0 0 0 0 0 0 0
5 5 0 0 0 0 0 0 0 0 0 0 0 0 0
100 100 0 0 0 0 0 0 0 0 0 2 1 0 0

样例输出:

Case #1: Alice
Case #2: Bob
Case #3: Alice

著名的博弈玩家Alice and Bob, A有1*2的方块,B有2*1的方块,给出15种大方块,每样最多100个(约去平衡态后这个数据并不是很重要的东西), 没人轮流选在任意方块上放上一个自己专有的方块,不能为者负。

根据每个方块的能被放的情况对方块分类,共5类

1– 2A  2–2B                                              ///1

3 4– 1A OR 2B       5 6 –1B OR 2A        ///2

7 8 1A1B OR 1A    9 10–1A1B OR 1B  ///3

11 12 13 14 1A OR 1B                            ///4

15 2A OR 2B                                             ///5

总游戏 其实就是5类游戏的组合游戏,但是SG函数很难找状态,还是找规律约去不影响结果的平衡局势即可。

根据贪心策略 有 5>2>4>3>1

#include <cstdio>
#define min(a,b) (a>b?b:a)
int num[16];
int game[10];
int p[5];
int main ()
{
    int cas;
    scanf("%d",&cas);
    for (int I=1 ; I<=cas ; ++I)
    {
        int tmpmin;
        int turn=0;//表示当前子游戏的先手
        p[0]=0;p[1]=0;//记录约去平衡状态后的每个人的可放个数
        for (int i=0 ; i<15 ; ++i)
        {
            scanf("%d",num+i);
        }
        game[0]=num[0];     game[1]=num[1];             ///1
        game[2]=num[2]+num[3];  game[3]=num[4]+num[5];  ///2
        game[4]=num[6]+num[7];    game[5]=num[8]+num[9];///3
        game[6]=num[10]+num[11]+num[12]+num[13];        ///4
        game[7]=num[14];                                ///5
        
        /**约去平衡态**/
        /// 1
        game[0]>game[1]?p[0]+=2*(game[0]-game[1]):p[1]+=2*(game[1]-game[0]);
        /// 2
        tmpmin=min(game[2],game[3]);
        game[2]-=tmpmin;
        game[3]-=tmpmin;
        /// 3
        tmpmin=min(game[4],game[5]);
        game[4]-=tmpmin;    game[5]-=tmpmin;
        /// 4
        game[6]=game[6]&1;
        /// 5
        game[7]=game[7]&1;

        /// 5>2>4>3>1
        ///**按优先级进行游戏 1情况不影响结果可先处理**///
        ///5
        if(game[7])p[turn]+=2,turn^=1;
        ///2
        if(game[2])
        {
            if(game[2]&1){if(turn == 1)p[1]+=2;  else p[0]+=1; turn^=1 ; }
            p[1]+=game[2]/2*2;
            p[0]+=game[2]/2;
        }
        if(game[3])
        {
            if(game[3]&1){if(turn == 0)p[0]+=2;  else p[1]+=1; turn^=1 ; }
            p[0]+=game[3]/2*2;
            p[1]+=game[3]/2;
        }
        ///4
        if(game[6])
        {
            p[turn]+=1;turn^=1;
        }
        ///3
        if(game[4])
        {
            p[0]+=game[4];
            if(game[4]&1)
            {
                if(turn == 1)p[1]+=1;
                turn^=1;
            }
            p[1]+=game[4]/2;
        }
        if(game[5])
        {
            p[1]+=game[5];
            if(game[5]&1)
            {
                if(turn == 0)p[0]+=1;
                turn^=1;
            }
            p[0]+=game[5]/2;
        }
        ///
        //printf("%d----%d\n",p[0],p[1]);
        printf("Case #%d: %s\n",I,p[0]>p[1]?"Alice":"Bob");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/jxy859/article/details/6766427


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。