首页 > ACM题库 > HDU-杭电 > HDU 4387-Stone Game-博弈论-[解题报告]HOJ
2015
05-24

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

Stone Game

问题描述 :

  Alice and Bob are playing a game. It is played in 1*N grids. Each grid can be occupied by one stone. Alice has K white stones on the left (numbered 1 to K from left to right), and Bob has K black stones on the right (numbered 1 to K from right to left). They take turns to move their own stones, and Alice moves first. In each move, the player must choose one stone to move to the nearest empty grid forward (Alice moves to the right, Bob moves to the left). If one player cannot find any stone to move, he wins.
  Now Alice asks you to find a winning strategy of the game. Can you help him?

Quadrilateral

输入:

  There are multiple test cases. In each case, there is one line containing two integers N, K.

Technical Specification
  3 <= N <= 1,000,000, 1 < K*2 < N

输出:

  There are multiple test cases. In each case, there is one line containing two integers N, K.

Technical Specification
  3 <= N <= 1,000,000, 1 < K*2 < N

样例输入:

3 1
4 1

样例输出:

Case 1: Bob
Case 2: Alice 1

题意:在一行有N个方格的棋盘里,左右分别放了K个白色和黑色的棋子。游戏规则如下:Alice使左面的白色棋子向右走,Bob使右面的黑色棋子向左走。每次移动,要让自己的一个棋子前进到对应方向的前方的空格子。不能继续决策的人赢。

思路:

k=1时

  很容易看出,n为奇数则后手获胜,n为偶数则先手获胜

  k>1时

  如果n=2*k+1,则棋 盘中只有一个空白的格子,每次移动必须移动到当前的空白格子上。先手方可以先随意选择一颗棋子占据中间的位置,然后双方互有移动,移动过程中双方肯定都会 选择一颗在己方半场的棋子移动到对方半场里。直到后手方还剩下一颗己方半场的棋子时,先手方把占据中间的棋子移动到对方半场,此时后手方必须移动剩下的这 颗棋子到空出的中间的格子里,先手方再把最后一颗棋子移动到新空出的位置即可获胜。

  如果n>2*k+1,那么棋盘中就有了多余一个的 空白格子。如果n为奇数,先手方只要每次移动己方最靠后的一颗棋子即可获胜。并且第一次移动必须选择1号棋子,否则会让自己的棋子中间留下空白相当于把先 手让给了对方,这时对方只要采用先手策略即可获胜;如果n为偶数,那么先手方只需采用n=2*k+1时的策略在双方交会的时候保住先手即可,当然此时的第一步还是1号棋子,否则将失去先手优势。

代码如下:

#include <cstdio>
#include <algorithm>

using namespace std;

int n,k;

int main(void)
{
    //freopen("input.txt","r",stdin);
    int cas = 1;
    while(scanf("%d %d",&n,&k)!=EOF){
        printf("Case %d: ",cas++);
        int r = n - 2 * k;
        int ans = 1;
        bool sig = true;
        if(r&1){
            if(k == 1) sig = false;
            else if(r == 1) ans = k;
        }
        
        if(sig)
            printf("Alice %d\n",ans);
        else
            puts("Bob");
    }
    return 0;
}



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

参考:http://blog.csdn.net/u012139398/article/details/38866057