POJ 1704 Georgia and Bob(階梯Nim博弈)

Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 11357   Accepted: 3749 Description Georgia and Bob decide to play a self-invented game. They draw a row of grids on paper, number the grids from left to right by 1, 2, 3, ..., and place N chessmen on different grids, as shown in the following figure for example:  Georgia and Bob move the chessmen in turn. Every time a player will choose a chessman, and move it to the left without going over any other chessmen or across the left edge. The player can freely choose number of steps the chessman moves, with the constraint that the chessman must be moved at least ONE step and one grid can at most contains ONE single chessman. The player who cannot make a move loses the game.  Georgia always plays first since "Lady first". Suppose that Georgia and Bob both do their best in the game, i.e., if one of them knows a way to win the game, he or she will be able to carry it out.  Given the initial positions of the n chessmen, can you predict who will finally win the game?  Input The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case contains two lines. The first line consists of one integer N (1 <= N <= 1000), indicating the number of chessmen. The second line contains N different integers P1, P2 ... Pn (1 <= Pi <= 10000), which are the initial positions of the n chessmen. Output For each test case, prints a single line, "Georgia will win", if Georgia will win the game; "Bob will win", if Bob will win the game; otherwise 'Not sure'. Sample Input 2 3 1 2 3 8 1 5 6 7 9 12 14 17 Sample Output Bob will win Georgia will win Source POJ Monthly--2004.07.18

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

這題做法真的666啊，不知道std是怎麼想出來的

首先我們想到一種必敗態：即僅有兩個點且相鄰

那麼我們可以把所有的點排序之後兩兩捆綁，這樣如果A移動第一個，那麼B可以把第二個移動相同的步數

這樣我們就解決了順序的問題

那麼接下來就考慮如何解決博弈問題

這裡有個神仙操作

把兩點直接的距離看做一堆石子，然後請Nim來就可以啦

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=1e4+10,INF=1e9+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int a[MAXN];
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int QwQ=read();
    while(QwQ--)
    {
        int N=read();
        for(int i=1;i<=N;i++) a[i]=read();
        sort(a+1,a+N+1);
        int ans;
        if(N&1)//奇數 
        {
            ans=a[1]-1;
            for(int i=3;i<=N;i+=2)
                ans=ans^(a[i]-a[i-1]-1);
        }
        else
        {
            ans=a[2]-a[1]-1;
            for(int i=4;i<=N;i+=2)
                ans=ans^(a[i]-a[i-1]-1);
        }
        if(ans) printf("Georgia will win\n");
        else printf("Bob will win\n");
    }
    return 0;
}