HDU 1847-Good Luck in CET-4 Everybody!(博弈-SG函数/找规律)

逃离我推掉我的手 2022-08-22 01:30 64阅读 0赞

# Good Luck in CET-4 Everybody! #

**Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 7710 Accepted Submission(s): 4954**

Problem Description

大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张得连短学期的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”，每个实例的输出占一行。

Sample Input

1
    3

Sample Output

Kiki
    Cici

Author

lcy

Source

[ACM Short Term Exam\_2007/12/13][ACM Short Term Exam_2007_12_13]

Recommend

lcy | We have carefully selected several similar problems for you: [1848][] [1849][] [1846][] [2147][] [2149][]

## 解题思路： ##

①n是三的倍数时，是必败点。

[From][]简单证明一下：3的倍数是必败状态。

*  如果n % 3 = 1，那么拿走1个石子；如果n % 3 = 2，那么拿走两个石子，都将转移到3的倍数的状态。所以每个必胜状态都有一个后继是必败状态。
 *  如果n % 3 = 0，因为2i里面没有一个是3的倍数，所以不管怎么拿，剩下的石子数n' % 3 != 0.所以每个必败状态的所有后继都是必胜状态。

②用sg函数做。

AC①

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            if(n%3)printf("Kiki\n");//必败点
            else printf("Cici\n");
    
        }
        return 0;
    }

AC②

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    #define MAXN 1010
    int f[MAXN];
    bool sg[MAXN];
    
    void solve()
    {
        int i,j,cnt=9;
        f[0]=1;
        for(i=1; i<=9; i++) //1000内的2次幂数
            f[i]=f[i-1]*2;
        sg[0]=false;
        for(i=1; i<=1000; i++) //求sg值,i表示牌的数目
        {
            sg[i]=false;
            for(j=0; j<=cnt; ++j)
                sg[i]|=f[j]<=i&&!sg[i-f[j]];
        }
    }
    int main()
    {
        int n;
        solve();
        while(~scanf("%d",&n))
        {
            if(sg[n]) printf("Kiki\n");//必败点
            else printf("Cici\n");
        }
        return 0;
    }

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define MAXN 1010
    int sg[MAXN],f[MAXN],temp[MAXN];
    
    void solve()
    {
        int i,j,cnt=9;
        f[0]=1;
        for(i=1; i<=9; i++) //1000内的2次幂数
            f[i]=f[i-1]*2;
        memset(sg,-1,sizeof(sg));
        sg[0]=0;
        for(i=1; i<=1000; i++) //求sg值,i表示牌的数目
        {
            memset(temp,-1,sizeof(temp));
            for(j=0; j<=cnt&&f[j]<=i; ++j)
                temp[sg[i-f[j]]]=0;//i-f[j]表示从i张牌中取走f[j]张后的状态
            for(j=0;; ++j)//求mem
                if(temp[j]==-1)
                {
                    sg[i]=j;
                    break;
                }
        }
    }
    int main()
    {
        int n;
        solve();
        while(~scanf("%d",&n))
        {
            if(sg[n]) printf("Kiki\n");//必败点
            else printf("Cici\n");
        }
        return 0;
    }

[ACM Short Term Exam_2007_12_13]: http://acm.hdu.edu.cn/search.php?field=problem&key=ACM+Short+Term+Exam_2007%2F12%2F13&source=1&searchmode=source
[1848]: http://acm.hdu.edu.cn/showproblem.php?pid=1848
[1849]: http://acm.hdu.edu.cn/showproblem.php?pid=1849
[1846]: http://acm.hdu.edu.cn/showproblem.php?pid=1846
[2147]: http://acm.hdu.edu.cn/showproblem.php?pid=2147
[2149]: http://acm.hdu.edu.cn/showproblem.php?pid=2149
[From]: http://www.cnblogs.com/AOQNRMGYXLMV/p/4418412.html