【Nim博弈】
这道题一开始看上去不像Nim博弈,但它为什么会是Nim博弈呢?
首先我们可以看原题上的那个图:

原题说我们需要将每个格子内的棋子进行移动,当所有棋子都位于最左边编号为0的格子时,游戏结束.

首先我们将棋盘竖起来(自己画的,所以会少一点,但大体意思一样).

然后我们将其中的棋子分开来:

这样我们就可以将其转化为Nim博弈了.我们可以视为当前棋子所在的位置代表当前堆的石子个数.因为只能向左移动,即只能减少石子的数量.当棋子移动到0时,即代表石子已取空.

Code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int K;
    while(~scanf("%d",&K)){
        if(K==0) break;
        int ans=0;
        while(K--){
            int a;
            scanf("%d",&a);
            ans^=a;
        }
        if(ans==0)puts("Grass Win!");
        else puts("Rabbit Win!");
    }
    return 0;
}

【博弈论 – SG函数】

题目:

Good Luck in CET-4 Everybody!

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11483 Accepted Submission(s): 7446

大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是如此。当然，作为在考场浸润了十几载的当代大学生，Kiki和Cici更懂得考前的放松，所谓“张弛有道”就是这个意思。这不，Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”？“双扣”？“红五”？还是“斗地主”？
当然都不是！那多俗啊~
作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的：
1、 总共n张牌;
2、 双方轮流抓牌；
3、 每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生~），并且每次都是Kiki先抓牌，请问谁能赢呢？
当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态。

Good luck in CET-4 everybody!

Input

输入数据包含多个测试用例，每个测试用例占一行，包含一个整数n（1<=n<=1000）。

Output

如果Kiki能赢的话，请输出“Kiki”，否则请输出“Cici”，每个实例的输出占一行。

SampleInput

1
3

SampleOutput

Kiki
Cici

题解

首先我们要知道SG函数代表的是当前状态的数值.如果是0,则为先手必败(SG函数值为可到达状态中未出现的最小的整数).然后我们从SG函数延伸一下–

1.我们假设当n=0时,先手必败.
2.当n=1时,因为S(0)=0，所以当前状态是非奇异局势.先手必胜,即,你可以通过拿走一定的牌使下一个拿牌的人的局势变成奇异局势(必败态).
即转移给下一个抽牌者状态为S(0).
3.当n=2是,因为S(0)=0，S(1)=1.所以当前状态是非奇异局势,先手必胜.
即你可以把下一个抽牌者状态转换成S(0).
4.当n=3时,可到达状态为S(3-1)=S(2)=1.S(3-2)=S(1)=1.因为无论往那个状态走,都会使对方先手必胜,所以该局势为奇异局势.先手必败.

故我们可以根据以上推理过程将全部的1000个状态是否必胜预处理处来.其预处理过程为检查可以到达的状态是否存在奇异局势,如果存在,则该局势为非奇异局势,即先手必胜态.

因为可拿牌数都是2^n.所以预处理复杂度为O(nlg(n)).

PS…:其实预处理完以后你会发现.每当n%3==0时,为奇异局势.

Code:

//SG函数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

bool game[1001];

void init(){
    memset(game,false,sizeof(game));
    for(int i=1;i<=1000;++i){
        int t=1;
        while(i-t>=0){
            //如果i-t是奇异局势,则先手必胜
            if(!game[i-t]){
                game[i]=true;
                break;
            }
            t<<=1;
        }
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n)){
        if(game[n]){
            printf("Kiki\n");
        }else{
            printf("Cici\n");
        }
    }
    return 0;
}

【巴什博奕】

题目:

虽然不想，但是现实总归是现实，Lele始终没有逃过退学的命运，因为他没有拿到奖学金。现在等待他的，就是像FarmJohn一样的农田生涯。

要种田得有田才行，Lele听说街上正在举行一场别开生面的拍卖会，拍卖的物品正好就是一块20亩的田地。于是，Lele带上他的全部积蓄，冲往拍卖会。

后来发现，整个拍卖会只有Lele和他的死对头Yueyue。

通过打听，Lele知道这场拍卖的规则是这样的：刚开始底价为0，两个人轮流开始加价，不过每次加价的幅度要在1～N之间，当价格大于或等于田地的成本价 M 时，主办方就把这块田地卖给这次叫价的人。

Lele和Yueyue虽然考试不行，但是对拍卖却十分精通，而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。

由于Lele字典序比Yueyue靠前，所以每次都是由Lele先开始加价，请问，第一次加价的时候，
Lele要出多少才能保证自己买得到这块地呢？

Input:

本题目包含多组测试，请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数M和N(含义见题目描述，0<N，M<1100)

Output:

对于每组数据，在一行里按递增的顺序输出Lele第一次可以加的价。两个数据之间用空格隔开。
如果Lele在第一次无论如何出价都无法买到这块土地，就输出”none”。

Sample Input:

4 2
3 2
3 5

Sample Output:

1
none
3 4 5

题解

我们知道,在巴士博弈中,n=0为先手必输态,之后n=m+1为下一个先手必输态.
而当Lele在竞拍的时候,如果他所在的初始状态是如上所述的这样一个奇异局势(即先手必输局势),那他一定输(none).
当Lele在竞拍处于非奇异局势时,在选择最优的情况下,他一定可以赢得竞拍.即他只需要通过增价将对手置于奇异状态即可.
所以当我们想要找出Lele第一次出家的可能性时,只需要先找出Lele的第一个置对方为奇异局势的 价格 .然后在寻找下一个的时候只需要依次++,直到下一次加价会给对方一个 非奇异局势前 结束循环.
当然,存在一种可能性就是,初次加价可能会溢出n的价格范围.

//巴什博奕
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        if(n%(m+1)==0) printf("none\n");
        else{
            int next=0;
            while(1){
                next++;
                if((n-next)%(m+1)==0){
                    printf("%d",next);
                    break;
                }
            }
            while(next<m){
                next++;
                if((n-next)%(m+1)==0 || next>=n){
                    printf(" %d",next);
                }else{
                    break;
                }
            }
            printf("\n");
        }
    }
    return 0;
}