HDU 5011 Game (博弈水题)




Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 155 Accepted Submission(s): 120

Problem Description

Here is a game for two players. The rule of the game is described below: ● In the beginning of the game, there are a lot of piles of beads. ● Players take turns to play. Each turn, player choose a pile i and remove some (at least one) beads from it. Then he could do nothing or split pile i into two piles with a beads and b beads.(a,b > 0 and a + b equals to the number of beads of pile i after removing) ● If after a player’s turn, there is no beads left, the player is the winner. Suppose that the two players are all very clever and they will use optimal game strategies. Your job is to tell whether the player who plays first can win the game.


There are multiple test cases. Please process till EOF. For each test case, the first line contains a postive integer n(n < 105) means there are n piles of beads. The next line contains n postive integer, the i-th postive integer ai(ai < 231) means there are ai beads in the i-th pile.


For each test case, if the first player can win the game, ouput “Win” and if he can’t, ouput “Lose”

Sample Input

1 1 2 1 1 3 1 2 3

Sample Output

Win Lose Lose


2014 ACM/ICPC Asia Regional Xi’an Online

这题的常规做法就是,暴力打SG表。 找规律, 发现sg\[i\] = i; 然后就是所有数异或起来,为0就是输,否则赢。   当然如果你YY功力足够好,直接猜出异或,然后AC, 那也是可以的。  

/* ***
Author :kuangbin
Created Time :2014/9/15 0:15:56
File Name :E:\2014ACM\2014网络赛\2014西安\HDU5011.cpp
************************************************ */

#include <stdio.h>

#include <string.h>








#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

int main()
int n;
while(scanf(“%d”,&n) == 1){
int a,sum = 0;
sum ^= a;
else printf(“Lose\n”);
return 0;

------ 本文结束------
  • 本文作者: kuangbin
  • 本文链接: 391.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!