「HDU 1847」Good Luck in CET-4 Everybody

Description

一个公平组合游戏:

  1. 总共 $n$ 张牌;
  2. 双方轮流抓牌,两人都足够聪明;
  3. 每人每次抓牌的个数只能是 $2$ 的幂次(即:$1,2,4,8,16\ldots$);
  4. 最后抓完牌的人为胜者。

$\rm Kiki$ 先手,$\rm Cici$ 后手,求最后谁能获胜。$(1 \leq n \leq 10^3)$

Source

[hdu]1847

Solution

$\rm SG$ 函数经典例题。

我们把这个游戏放到一个 DAG 上。

EzQxcq.png

最终取完牌的状态是 $0$,$0$ 没有后继状态,所以 $sg_0 = {\rm mex}(\varnothing ) = 0$,且这个点是必败点。

剩 $1$ 张牌的时候只能取走 $1$ 张,即 $1$ 的后继状态只有 $0$,所以

$sg_1 = {\rm mex}(\{sg_0\}) = {\rm mex}(\{0\})=1$ 。

剩 $2$ 张牌的时候能取走 $1$ 张或 $2$ 张,即 $2$ 的后继状态有 $1$ 和 $0$,所以

$sg_2 = {\rm mex}(\{sg_0,sg_1\}) = {\rm mex}(\{0,1\})=2$ 。

剩 $3$ 张牌的时候也能取走 $1$ 张或 $2$ 张,即 $3$ 的后继状态有 $2$ 和 $1$,所以

$sg_3 = {\rm mex}(\{sg_1,sg_2\}) = {\rm mex}(\{1,2\})=0$ 。

剩 $4$ 张牌的时候能取走 $1$ 张,$2$ 张或 $4$ 张,即 $4$ 的后继状态有 $3,2$ 和 $0$,所以

$sg_4 = {\rm mex}(\{sg_0,sg_2,sg_3\}) = {\rm mex}(\{0,2\})=1$ 。

同理我们能得到 $sg_5 = 2,sg_6 = 0,sg_7 = 1$ 。

$sg_0$$sg_1$$sg_2$$sg_3$$sg_4$$sg_5$$sg_6$$sg_7$
$0$$1$$2$$0$$1$$2$$0$$1$

综上所述我们可以列出一个表格,很容易发现规律:$sg_n = n \bmod 3$ 。

所以当 $n$ 能被 $3$ 整除时,它的 $\rm SG$ 函数值为 $0$,即先手必败。

反之则先手必胜。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline bool read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) {
if (c == EOF) return 0;
f ^= c == '-';
}
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
return 1;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int main() {
for (int n; read(n); ) {
if (n % 3) puts("Kiki");
else puts("Cici");
}
return 0;
}

本文标题:「HDU 1847」Good Luck in CET-4 Everybody

文章作者:Heartlessly

发布时间:2019年05月21日 - 07:35:14

最后更新:2019年05月21日 - 08:28:21

原始链接:https://heartlessly.github.io/problems/hdu-1847/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%