Chaos Slover 补档计划 - 博弈论

2015.11.09 09:42 Mon| 12 visits oi_2016| ChaosSlover补档计划| Text

提示:为缩短代码长度,本题解中代码的头文件均为<bits/stdc++.h>,因此有时可能无法通过编译。

注意:一大波土豪题预警。

POJ1704 Georgia and Bob

一个数轴,其中某些点有棋子(非升序给出)。两个人玩游戏,把某一个棋子往左移动,但不能和之前的棋子重叠或跨越之前的棋子。无法操作时判负,询问谁会赢?

将相邻的棋子两两“绑定”到一起(如果棋子数为奇数,不妨假设原点处也有一个棋子)。可以发现,如果将一对棋子中的前一个向前移动,那么另一个人也一定可以将后一个棋子向前移动同样的距离。因此一堆棋子在数轴上的位置可以忽略,而需要考虑的只有它们之间的相对距离。这样可以将每一对棋子间的距离看成石子数,问题就转化成了 NIM 游戏。

继续考虑,如果现在第一个人有了 NIM 游戏的必胜态,第二个人能否不配合第一个人的左移动作,不将后一个棋子移动相应的距离呢?可以想到,如果第二个人不配合,第一个人可以在下一次操作的时候顺便补齐这一操作,一定不会影响到 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
#include <bits/stdc++.h>
using namespace std;

#define N 10005

int T, n, a[N];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        int ans = 0;
        for (int i = n; i > 0; i -= 2)
            ans ^= (a[i] - a[i - 1] - 1);
        if (!ans) puts("Bob will win");
        else puts("Georgia will win");
    }
    return 0;
}

BZOJ1115 [POI2009]石子游戏Kam

和上一题基本相同,只是将坐标大于改为了不小于。比较懒的做法是,只需要把每一堆的石子数加上堆的编号,就可以用相同的代码 AC 此题了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

#define N 1005

int T, n, a[N];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]), a[i] += i;
        sort(a + 1, a + n + 1);
        int ans = 0;
        for (int i = n; i > 0; i -= 2)
            ans ^= (a[i] - a[i - 1] - 1);
        if (!ans) puts("NIE");
        else puts("TAK");
    }
    return 0;
}

BZOJ1188 [HNOI2007]分裂游戏

将每一个石子的状态看作一个子局面,那么整个局面的 SG 函数值为每一个石子的局面的 SG 函数的异或和。直接枚举所有第一步可能的操作方式,判断操作之后 SG 函数值是否为零就可以知道是否计入答案了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 25

int T, n, a[N], sg[N], vis[N * N];

void getsg(int x)
{
    static int tag = 0;
    ++tag;
    if (x == n) { sg[x] = 0; return; }
    for (int i = x + 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            vis[sg[i] ^ sg[j]] = tag;
    for (int i = 0; i > -1; ++i)
        if (vis[i] != tag)
            { sg[x] = i; return; }
}

int main()
{
    cin >> T;
    while (T--)
    {
        int ans = 0, tot = 0;
        memset(sg, -1, sizeof sg);
        cin >> n;
        for (int i = n; i; --i)
            getsg(i);
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            if (a[i] & 1) ans ^= sg[i];
        }
        for (int i = 1; i < n; ++i)
            for (int j = i + 1; j <= n; ++j)
                for (int k = j; k <= n; ++k)
                    if (a[i] && (ans ^ sg[i] ^ sg[j] ^ sg[k]) == 0)
                    {
                        ++tot;
                        if (tot == 1)
                            cout << i - 1 << ' ' << j - 1 << ' ' << k - 1 << '\n';
                    }
        if (tot == 0) puts("-1 -1 -1");
        cout << tot << endl;
    }
    return 0;
}

BZOJ1874 [BeiJing2009 WinterCamp]取石子游戏

写代码不要改来改去!!!写代码不要改来改去!!!

这道题其实做起来并不困难。需要注意一下在求 SG 函数的时候不能递归(我的做法),否则会让 vis 数组乱掉。这两道题其实数据都很水的……总是不考虑一些细节也能够通过。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 25
int n, m, a[N], b[N], sg[1005], vis[1005];

void getsg(int x)
{
    static int tag = 0;
    ++tag;
    if (sg[x] != -1) return;
    for (int i = 1; i <= m; ++i)
        if (x >= b[i])
            vis[sg[x - b[i]]] = tag;
    for (int i = 0; i > -1; ++i)
        if (vis[i] != tag)
            { sg[x] = i; return; }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++i)
        cin >> b[i];
    sort(b + 1, b + m + 1);
    memset(sg, -1, sizeof sg);
    int ans = 0;
    for (int i = 0; i <= 1000; ++i) getsg(i);
    for (int i = 1; i <= n; ++i)
        ans ^= sg[a[i]];
    if (ans)
    {
        puts("YES");
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (a[i] >= b[j] && !(ans ^ sg[a[i]] ^ sg[a[i] - b[j]]))
                    { cout << i << ' ' << b[j] << endl; return 0; }
    }
    else puts("NO");
    return 0;
}

BZOJ1457 棋盘游戏

当存在 x=0 或 y=0 或 x=y 的点的时候需要特判。在其余情况下,只在先手是 SB 的情况下会有棋子被移动到这三种位置。因此,只将 (1,2) 和 (2,1) 看作必败状态求裸 SG 函数即可。

可是为什么把 (0,0) 看作必败态过不了样例呢?这真是为什么呢?

 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
#include <bits/stdc++.h>
using namespace std;

int T, n, m, sg[105][105], vis[10005];

void getsg(int x, int y)
{
    static int tag = 0;
    ++tag;
    if (sg[x][y] != -1) return;
    for (int i = 1; i < x; ++i)
        if (x - i != y)
            vis[sg[x - i][y]] = tag;
    for (int i = 1; i < y; ++i)
        if (x != y - i)
            vis[sg[x][y - i]] = tag;
    for (int i = 1; i < min(x, y); ++i)
        if (x - i != y - i)
            vis[sg[x - i][y - i]] = tag;
    for (int i = 0; i > -1; ++i)
        if (vis[i] != tag)
            { sg[x][y] = i; return; }
}

int main()
{
    memset(sg, -1, sizeof sg);
    sg[1][2] = sg[2][1] = 0;
    for (int i = 1; i <= 99; ++i)
        for (int j = 1; j <= 99; ++j)
            if (i != j)
                getsg(i, j);
    cin >> T;
    while (T--)
    {
        int ans = 0, flag = 0;
        cin >> n;
        for (int x, y, i = 1; i <= n; ++i)
        {
            cin >> x >> y, ans ^= sg[x][y];
            if (!x || !y || x == y) flag = 1;
        }
        if (ans == 0 && !flag) puts("T_T");
        else puts("^o^");
    }
    return 0;
}

BZOJ1982 [Spoj 2021]Moving Pebbles

膜拜大爷题解 http://blog.csdn.net/popoqqq/article/details/46123417

另外如果有奇数个堆的话,先手开始时会用最大的堆进行填补后拿光剩余的石子。如果后手将某一堆里的石子放在拿光了的堆里,那么先手可以利用对应的堆里面的石子去调整那一个堆内的石子个数,从而使得这三个堆中石子个数一个为零,另两个里面相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, a[N], flag;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i += 2)
        if (a[i] != a[i + 1])
            flag = 1;
    if (n % 2 == 0 && !flag)
        puts("second player");
    else puts("first player");
    return 0;
}

BZOJ2275 [Coci2010]HRPA

当石子个数是斐波那契数的时候,先手必败。证明参见 http://blog.csdn.net/dgq8211/article/details/7602807

其余情况下:

Zeckendorf定理(齐肯多夫定理):任何正整数可以表示为若干个不连续的Fibonacci数之和。

先手可以取掉能够分解出的最小的斐波那契数个石子,得到必胜状态。

在分解的时候可以利用贪心,使当前分解出的斐波那契数尽可能大。而且想要保证正确性的话,大概要保证分解出的斐波那契数不相同。然而无论是否相同都能够通过这道问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

#define N 100005

long long n, f[N], tot;

int main()
{
    cin >> n;
    f[0] = f[1] = 1; tot = 1;
    while (f[tot] < n)
        f[tot + 1] = f[tot] + f[tot - 1], ++tot;
    while (n)
    {
        while (f[tot] > n) --tot;
        if (f[tot] == n)  { cout << n << endl; return 0; }
        n -= f[tot--];
    }
    return 0;
}

BZOJ1299 [LLH邀请赛]巧克力棒

被取出的EX咖哩棒将会构成一个 NIM 游戏。先手想要必胜,一定要取出一堆长度异或和为零的巧克力棒,并且使得剩下的巧克力棒中不存在一些巧克力棒的长度异或值为零。

其实在写代码的时候,只要判断在这样一堆巧克力棒中可以选出来一些使得长度异或值为零就好了。写一个 2^n 搜索刚刚好。

 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
#include <bits/stdc++.h>
using namespace std;

int n, a[20], flag;

void dfs(int d, int c, int s)
{
    if (d == n + 1)
    {
        if (c && !s) flag = 1;
        return;
    }
    dfs(d + 1, c, s);
    if (!flag) dfs(d + 1, c + 1, s ^ a[d]);
}

int main()
{
    for (int T = 1; T <= 10; ++T)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        flag = 0;
        dfs(1, 0, 0);
        if (flag) puts("NO");
        else puts("YES");
    }
    return 0;
}