hdu-1847 Good Luck in CET-4 Everybody!

2016年07月19日 |

acm

| acm

• 题目：
• 代码：
• 解析&吐槽：

题目：

Good Luck in CET-4 Everybody!
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8088 Accepted Submission(s): 5209


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

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
#include <limits>
#include <algorithm>
#include <numeric>
#include <string>
#include <utility>
#include <cstdlib>
//#include <cstdio>

using namespace std;

int good[1010];

inline int pow2(const int& n)
{
    return (1 << n);
}

inline void init()
{
    for (int i = 0;pow2(i) < 1010;++i)
        good[pow2(i)] = 1;
    good[3] = 2;
    good[5] = 1;
    good[6] = 2;
}

int getres(int n)
{
    if (good[n])
        return good[n];

    good[n] = 2;
    for (int i = 0;n - pow2(i) > 0;++i)
    {
        if (getres(n - pow2(i)) == 2)
        {
            good[n] = 1;
            break;
        }
    }

    return good[n];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    init();
    int n;
    while (cin >> n)
    {
        if (getres(n) == 1)
            cout << "Kiki" << endl;
        else
            cout << "Cici" << endl;
    }
}

解析&吐槽：

一道博弈论的题，大家都说这是巴什博奕。

分析题目可知，设对于 Kiki 胜利的局势是必胜局。

• 对于 n 等于 2 的幂次方的情况一定是必胜局。
• 如果 n 减去某个 2 的幂次方可以得到必胜局的话，那么 n 也一定是必胜局。
• 如果不管怎么减都无法得到必胜局，则 n 是必败局。

可见，上述的情况是一个完美的递归，可以用记忆化搜索的方式来提高效率。

我看过网上的题解说列出前几个必败局的情况，“通过观察可知”只要 n 是 3 的倍数，就一定是必败局。 也就是说下面的代码一样可以 AC：

int T;
while (cin >> T) {
  if (T % 3 == 0)
    printf("Cici\n");
  else
    printf("Kiki\n");
}

不过这到底是为什么呢，感觉这种找规律的事情也太不讲理了吧。