一、HDU 1730 Northcott Game 

游戏在一个n行m列（1 ≤ n ≤ 1000且2 ≤ m ≤ 100）的棋盘上进行，每行有一个黑子（黑方）和一个白子（白方）。执黑的一方先行，每次玩家可以移动己方的任何一枚棋子到同一行的任何一个空格上，当然这过程中不许越过该行的敌方棋子。双方轮流移动，直到某一方无法行动为止，移动最后一步的玩家获胜。Tom总是先下（黑方）。图1是某个初始局面，图二是Tom移动一个棋子后的局面（第一行的黑子左移两步）。 

     

题解：

等效于nim游戏。相当于n堆石子，每堆石子的数量等于每行黑白棋子间有多少个空格。如果全部都没有空格了，那么先走的必败，因为后走的可以贴着先走的棋子走，而对方一定在有限步之内穷途陌路，这时就相当于石子取完了。直观不同于nim的是，这里有可能通过反向移动，相当于增加石子，不过这也不会改变必胜必败态的。因为如果此时该走之人出于必胜态，那么就不必反向移动了，如果是必败态想通过增加石子改变必败态，那么另一方可以走相同的方向和步数来维持自己的必胜态，而耍赖一方的耍赖次数也是有限的。  到此模型就完全等价于nim游戏了。

代码：

int main()
{
    int n,m,i,j,k;
    while (~scanf("%d%d",&n,&m))
    {
        int ans=0;
        for (i=1;i<=n;i++)
        {
            scanf("%d%d",&j,&k);
            ans=ans^(abs(j-k)-1);
        }
        if (ans)puts("I WIN!");else puts("BAD LUCK!");
    }
    return 0;
}


二、HDU 1846 Brave Game 

题意：

只有一堆n个石子,两个人轮流从这堆石子中子,规定每次至少取一个,最多取m个.最后取光者得胜.

题解：

巴什博弈

若n%(m+1)=0，则先手必败，否则先手必胜。显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的石子,后者取胜.因此我们发现了如何取胜的法则：如果n=(m+1)*r+s,(s≤m),那么先取者要拿走s个石子,如果后取者拿走k(k≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜.

代码：

int main()
{
    int n,m,i,j,k;
    scanf("%d",&k);
    while (k--)
    {
        scanf("%d%d",&n,&m);
        if (n%(m+1))puts("first");else puts("second");
    }
    return 0;
}


三、HDU 1847 Good Luck in CET-4 Everybody! 

题意：

总共n张牌，双方轮流抓牌，每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…，最后抓完牌的人为胜者； 

题解：

暴力SG函数，打表。

代码：

int sg[1010]={0},i,j,k,l,n,m,t,h;
int v[10]={1,2,4,8,16,32,64,128,256,512};
int dfs(int x)
{
    if (sg[x]!=-1)return sg[x];
    bool c[12]={0};
    for (int i=0;i<10;i++)if (v[i]<=x)
    {
        int t=x-v[i];
        sg[t]=dfs(t);
        c[sg[t]]=1;
    }else break;
    for (int i=0;;i++)if (!c[i]) return i;
}

int main()
{
    memset(sg,-1,sizeof sg);
    for (i=0;i<1001;i++)sg[i]=dfs(i);
    while (~scanf("%d",&n))if (sg[n])puts("Kiki");else puts("Cici");
    return 0;
}


四、HDU 1580 Being a Good Boy in Spring Festival 

题意：

有m堆牌，两个人先后取某堆中的任意（不少于一）张牌，最后取完者胜；问先手取胜第一次取牌有多少种取法。

题解：

先求异或和为k。然后k再与每堆异或，若异或值（k^a）小于那堆的石子数(a)，说明取到(k^a),此时k^a^(k^a)==0,为必败态，那么自己就是必胜态，就是一种可行解。

代码：

int main()
{
    while(~scanf("%d",&n) && n)
    {
        k=0;
        for (i=1;i<=n;i++)scanf("%d",&a[i]),k^=a[i];
        if (!k)puts("0");else
        {
            j=0;
            for (i=1;i<=n;i++) if ((k^a[i])<a[i])j++;
            printf("%d\n",j);
        }

    }
    return 0;
}


五、 HDU 2147 kiki's game 

题意：

一个n*m的表格，起始位置为右上角，目标位置为左下角，甲先开始走，走的规则是可以向左，向下或者向左下（对顶的）走一格。谁先走到目标位置谁就胜利。在甲乙都采用最佳策略的时候，先走者能否获胜。也是一个巴什博弈的题目。首先画出PN图。

                                                                

只要m或者n有一个是偶数先手就能必胜。

代码：

int main()
{
    while(~scanf("%d%d",&n,&m) && n)
    {
        n--;m--;
        if (n%2==0 && m%2==0 )puts("What a pity!");else puts("Wonderful!");

    }
    return 0;
}


六、HDU 2149 Public Sale

题意：

两人拍卖，每次加价不超过N，超过M就卖给谁，问第一次加价多少才能肯定买到？

题解：

巴什博弈。

代码：

int main()
{
    while(~scanf("%d%d",&n,&m) && n)
    {
        if (m>=n)
        {
            for (i=n;i<m;i++)printf("%d ",i);printf("%d\n",i);
        }else
        if (n%(m+1)==0)puts("none");else printf("%d\n",n%(m+1));
    }
    return 0;
}


七、HDU 2177 威佐夫博弈

题意：

代码：

int n,m,i,j,k,a[200010];
int c[1000010];

int main()
{
    double x=(1+sqrt(5))*0.5;
    memset(c,-1,sizeof c);
    for (i=0;i<=1000000;i++)
    {
        k=i+i*x;
        if (k>1000010)break;
        c[k]=i*x;
    }
    while(~scanf("%d%d",&n,&m) && n)
    {
        if (n>m)swap(n,m);
        int t=(m-n)*x;
        if (t==n)puts("0");else
        {
            puts("1");
            t=m-n;
            int xx=t*x,yy=xx+t;
            if (n-xx == m-yy)printf("%d %d\n",xx,yy);
            if (c[n]!=-1)printf("%d %d\n",c[n],n);
            if (m!=n && c[m]!=-1)printf("%d %d\n",c[m],m);
        }
    }
    return 0;
}