Link

http://acm.hdu.edu.cn/showproblem.php?pid=1847

Problem

大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的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!

Analysis

裸地SG函数入门题。下面是转载的SG函数基本概念和方法:

sg 即Graph Game,把博弈游戏抽象成有向无环图

(1) 有向无环图
(2) 玩家1先移动,起点是x0
(3) 两个玩家轮流移动
(4) 对于顶点x, 玩家能够移动到的顶点集记为F(x).
(5) 不能移动的玩家会输掉游戏

首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、 mex{2,3,5}=0、mex{}=0。

定义: 一个图的Sprague-Grundy函数(X,F)是定义在X上的非负函数g(x),并且满足:
g(x) = mex{g(y) : y∈F(x)}

看到这里先好好理解一下sg值是怎么求的;

如果在取子游戏中每次只能取{1,2,3},那么各个数的SG值是多少?

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14. . .
g(x) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2. . .
看看这个和上面那个图的规律:

P-点: 即令 g(x) = 0 的 x 点!
N-点: 即令 g(x) > 0 的 x 点!

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024;
int sg[maxn], vis[maxn];

void getSG() {
    for(int i = 1; i < maxn; ++i) {
        memset(vis, false, sizeof(vis));
        //枚举状态转移:i -> i-2^j
        for(int j = 0; i-(1<<j) >= 0; ++j)
            vis[sg[i-(1<<j)]] = true;
        for(int j = 0; ; ++j) {
            if(!vis[j]) {
                sg[i] = j;
                break;
            }
        }
    }
}

int main() {
    getSG();
    int N;
    while(~scanf("%d", &N)) {
        if(sg[N]) puts("Kiki");
        else puts("Cici");
    }
    return 0;
}

欢迎留言