解題區/解題區 - UVa

UVa 1482 - Playing With Stones

contents

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

Problem

有 N 堆石頭，每次選一堆，只能不能拿大於一半的石頭總數。

求兩個人都採用最佳策略，請問誰輸誰贏。

Sample Input

1
2
3
4
5
6
7
8
9
4 
2 
4 4 
3 
1 2 3
3 
2 4 6
3 
1 2 1

Sample Output

1
2
3
4
NO 
YES 
NO 
YES

Solution

建造 SG 函數進行觀察，接著直接套用 SG 函數的 nim 規則。

關於 SG

让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i<k，都存在x的一个后继y满足g(y)=i。也 就是说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏， Nim游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶 点的SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！

http://baike.baidu.com/view/2855458.htm

Sprague-Grundy 圖示演說參考

對於博弈，一直以來盡可能靠記憶化搜索 dp 完成，寫題基本上也還算過得去，在大數據的題目上，除了幾個噁心的數學分析外，利用記憶化搜索進行小數據觀察，真的沒搞頭的題目，大多解法是所謂的 SG 函數 (Sprague-Grundy)。

再不學點新的，就要沒有看得懂的題目可以刷了 … 如果因為看不懂題目，而增加對英文的仇恨值，都不知道溢位幾個世紀去了。

SG 函數簡單而言是對於針對某一類型的博弈遊戲，可以轉換成 Nim 遊戲，每一個 SG 函數的 value 對應 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
#include <stdio.h>
#include <string.h>
void buildSG() { // observe rule
    int mex[1024] = {}, SG[50];
    SG[0] = 0;
    for (int i = 1; i < 50; i++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 1; j <= i/2; j++)
            mex[SG[i - j]] = 1;
        int sg = 0;
        for (sg = 0; mex[sg]; sg++);
        SG[i] = sg;
        printf("%d : %d\n", i, SG[i]);
    }
}
long long SG(long long x) {
    return x%2 == 1 ? SG(x/2) : x/2; 
}
int main() {
//	buildSG();
    int testcase, n;
    long long x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            ret ^= SG(x);
        }
        puts(ret ? "YES" : "NO");
    }
    return 0;
}