解題區/解題區 - UVa

UVa 12846 - A Daisy Puzzle Game

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有一套撥花瓣遊戲，一朵花有 n 片花瓣，每一片花瓣分別位置在 1…n，呈現環狀，首尾相連。兩個人輪流撥花瓣，每一次撥一片、或者撥相鄰的兩片，最後一個取走花瓣的人輸。

給已經撥去花瓣，請問現在她先手會不會勝利？

Sample Input

1
2
3
4
5
2
13 1
7
5 3
1 3 4

Sample Output

1
2
Case 1: yes
Case 2: no

Solution

看出是一道 SG 博奕遊戲，假設有 n 個連續花瓣，取中間一片、或連續兩片，將會變成兩段連續花瓣，藉此建造 SG 函數，求出連續 n 個連續花瓣的 SG 值，隨後統計有多少段連續花瓣，並且各自擁有多少花瓣，接著套用 nim 遊戲得到結果。

特別小心是環狀的，題目沒有描述得很清楚。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int SG[1024];
void buildSG() {
    int mex[1024] = {};
    SG[0] = 0;
    for (int i = 1; i < 50; i++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 0; j < i; j++) {
            mex[SG[j] ^ SG[i-j-1]] = 1;
            if (i-j-2 >= 0)
                mex[SG[j] ^ SG[i-j-2]] = 1;
        }
        int sg = 0;
        for (sg; mex[sg]; sg++);
        SG[i] = sg;
    }
}
int main() {
    buildSG();
    int testcase, cases = 0, n, m, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        int used[64] = {}, last = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            x--;
            used[last = x] = 1;
        }
        
        vector<int> nim;
        for (int i = 0, tmp = 0, pos; i < n; i++) {
            pos = (last + i)%n;
            if (used[pos] == 0)
                tmp++;
            if (used[pos] || i == n-1) {
                if (tmp)
                    nim.push_back(tmp);
                tmp = 0;
            }
        }
        
        int ret = 0;
        for (int i = 0; i < nim.size(); i++)
            ret ^= SG[nim[i]];
        printf("Case %d: %s\n", ++cases, ret ? "yes" : "no");
    }
    return 0;
}
/*
9999
13 1
7
5 3
1 3 4
6 2
1 5
1 1
1
1 0
*/