[NOIP 2010 普及组] 三国游戏

GitHub 跳转原题关系图返回列表

把每个武将所在行的次大默契值看成他起手后能保住的最强搭档，再取所有次大值的最大者；同时用高边构成匹配证明小涵一定能赢。

OJ: luogu

题目 ID: P1199

难度:普及+/提高

标签:思维博弈图论构造最大次大值

日期: 2026-06-20 10:19

题意

有 n 个武将，任意两人之间都有一个互不相同的默契值。

小涵和计算机轮流选将，小涵先手。
计算机每次都会按题目指定的贪心策略，优先抢走最能破坏小涵下一步最强组合的那个自由武将。

所有武将被平分后，双方各自在自己军队里选出默契值最高的一对武将出战，默契值更大的一方获胜。

要求判断：

小涵是否一定能赢
如果能赢，在所有可能胜利结局中，小涵那对出战武将的最大默契值是多少

思路

先看一个可以完整模拟规则的小数据暴力：

cpp

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n;
int w[MAXN][MAXN];
int all_mask;
map<long long, int> memo_win;
map<long long, int> memo_best;

// 计算某一方当前军队中的最强组合。
int best_pair_value(int mask) {
    int ans = -1000000000;
    for (int i = 0; i < n; i++) {
        if (((mask >> i) & 1) == 0) {
            continue;
        }
        for (int j = i + 1; j < n; j++) {
            if ((mask >> j) & 1) {
                ans = max(ans, w[i][j]);
            }
        }
    }
    return ans;
}

long long encode_state(int xmask, int cmask, int turn) {
    return ((long long) xmask << 21) | ((long long) cmask << 1) | turn;
}

pair<int, int> dfs(int xmask, int cmask, int turn) {
    long long key = encode_state(xmask, cmask, turn);
    if (memo_win.count(key)) {
        return make_pair(memo_win[key], memo_best[key]);
    }

    int free_mask = all_mask ^ xmask ^ cmask;
    if (free_mask == 0) {
        int x_best = best_pair_value(xmask);
        int c_best = best_pair_value(cmask);
        if (x_best > c_best) {
            memo_win[key] = 1;
            memo_best[key] = x_best;
        }
        else {
            memo_win[key] = 0;
            memo_best[key] = -1000000000;
        }
        return make_pair(memo_win[key], memo_best[key]);
    }

    if (turn == 0) {
        int can_win = 0;
        int best_value = -1000000000;
        for (int i = 0; i < n; i++) {
            if ((free_mask >> i) & 1) {
                pair<int, int> ret = dfs(xmask | (1 << i), cmask, 1);
                if (ret.first) {
                    can_win = 1;
                    best_value = max(best_value, ret.second);
                }
            }
        }
        memo_win[key] = can_win;
        memo_best[key] = best_value;
        return make_pair(can_win, best_value);
    }
    else {
        // 计算机的策略是：
        // 从“小涵已选武将”与“当前自由武将”的所有配对中，
        // 找到默契值最大的那一对，并抢走其中的自由武将。
        int choose = -1;
        int best_match = -1;
        for (int i = 0; i < n; i++) {
            if (((xmask >> i) & 1) == 0) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if ((free_mask >> j) & 1) {
                    if (w[i][j] > best_match) {
                        best_match = w[i][j];
                        choose = j;
                    }
                }
            }
        }
        pair<int, int> ret = dfs(xmask, cmask | (1 << choose), 0);
        memo_win[key] = ret.first;
        memo_best[key] = ret.second;
        return ret;
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cin >> w[i][j];
            w[j][i] = w[i][j];
        }
    }

    all_mask = (1 << n) - 1;

    pair<int, int> ret = dfs(0, 0, 0);
    cout << ret.first << '\n';
    if (ret.first) {
        cout << ret.second << '\n';
    }

    return 0;
}

暴力会枚举小涵每一步选谁，计算机则按题意固定回应，最后比较双方最强二人组。它只能用于很小的数据，但很适合帮我们验证结论。

第一步：固定第一手看会发生什么

假设小涵第一手选了武将 i。

由于此时小涵军队里只有 i 一个人，所以计算机下一手一定会：

在所有自由武将里找一个和 i 默契值最大的
然后把它抢走

这就意味着：

i 最好的搭档一定被破坏
小涵围绕 i 还能保住的最好搭档，只能是第二好的那个

所以对每个武将 i，只要看它这一行里的：

最大值
次大值

其中次大值，就是“小涵如果第一手拿 i，最终至少能保住的最好组合值”。

于是先得到一个候选答案：

ans = max(第 i 行次大值)

第二步：为什么这个值一定能赢

关键性质是：

所有 严格大于 ans 的边，一定构成一个匹配

原因很简单：
如果某个点连出去有两条边都大于 ans，那么这个点所在行的次大值也会大于 ans，这和 ans 的定义矛盾。

既然这些高边构成匹配，那么在选将过程中：

计算机一次最多只能拿走某条高边的一个端点
小涵总能在自己的下一步把对应的另一个端点拿走

所以计算机最终不可能同时拥有某条高边的两个端点，也就不可能形成默契值大于 ans 的组合。

而小涵只要从“次大值等于 ans”的那一行对应武将起手，就能保证自己最后拿到一条默契值至少为 ans 的边。

因此：

小涵一定能赢
最大可保证值就是 ans

代码

cpp

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

const int MAXN = 505;

int n;
int w[MAXN][MAXN];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> w[i][j];
            w[j][i] = w[i][j];
        }
    }

    int answer = 0;

    // 对于每个武将 i：
    // 如果小涵第一步先拿 i，
    // 计算机一定会抢走和 i 默契值最大的那个武将。
    // 那么小涵以后能和 i 组成的最好搭档，只能是“这一行的次大值”对应的人。
    // 在所有起手武将里取最大的次大值，就是最终答案。
    for (int i = 1; i <= n; i++) {
        int first_max = 0;
        int second_max = 0;
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                continue;
            }
            if (w[i][j] > first_max) {
                second_max = first_max;
                first_max = w[i][j];
            }
            else if (w[i][j] > second_max) {
                second_max = w[i][j];
            }
        }
        answer = max(answer, second_max);
    }

    cout << 1 << '\n';
    cout << answer << '\n';

    return 0;
}

复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

总结

这题表面是博弈，真正的关键却是一个很短的图论结论：

固定第一手后，计算机会破坏这一行最大值
所以这一行能保住的是次大值
所有超过全局答案的边会形成匹配，计算机拿不成完整的一条

所以最后答案就是：

所有行的次大值中的最大值

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1199 [NOIP 2010 普及组] 三国游戏

题目描述

小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。

在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有 $N$ 位武将（ $N$ 为偶数且不小于 $4$ ），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。

游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵 $\to$ 计算机 $\to$ 小涵 $\to\dots$ ”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。

已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己的军队。下面举例说明计算机的选将策略，例如，游戏中一共有 $6$ 个武将，他们相互之间的默契值如下表所示：

武将编号	1	2	3	4	5	6
1		$5$	$28$	$16$	$29$	$27$
2	$5$		$23$	$3$	$20$	$1$
3	$28$	$23$		$8$	$32$	$26$
4	$16$	$3$	$8$		$33$	$11$
5	$29$	$20$	$32$	$33$		$12$
6	$27$	$1$	$26$	$11$	$12$

双方选将过程如下所示：

	小涵	轮到计算机时可选的自由武将	计算机	计算机选将说明
第一轮	$5$	$1,2,3,4,6$	$\color{magenta}4$	小涵手中的 $5$ 号武将与 $4$ 号的默契值最高，所以计算机选择 $4$ 号。
第二轮	$5,3$	$1,2,6$	$4,\color{magenta}1$	小涵手中的 $5$ 号和 $3$ 号武将与自由武将中配对可产生的最大默契值为 $29$ ，是由 $5$ 号与 $1$ 号配对产生的，所以计算机选择 $1$ 号。
第三轮	$5,3,6$	$2$	$4,1,\color{magenta}2$

小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？

假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。

输入格式

共 $N$ 行。

第一行为一个偶数 $N$ ，表示武将的个数。

第 $2$ 行到第 $N$ 行里，第 $i+1$ 行有 $N-i$ 个非负整数，每两个数之间用一个空格隔开，表示 $i$ 号武将和 $i+1,i+2,\dots,N $ 号武将之间的默契值（ $0 \le \text{默契值} \le 10^9$ ）。

输出格式

共一或二行。

若对于给定的游戏输入，存在可以让小涵获胜的选将顺序，则输出 $ 1$，并另起一行输出所有获胜的情况中，小涵最终选出的武将组合的最大默契值。如果不存在可以让小涵获胜的选将顺序，则输出 $0$ 。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
66 
5 28 16 29 27 
23 3 20 1 
8 32 26 
33 11 
12

输出 #1

text

1
21
32

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
88 
42 24 10 29 27 12 58 
31 8 16 26 80 6 
25 3 36 11 5 
33 20 17 13 
15 77 9 
4 50 
19

输出 #2

text

1
21
77

说明/提示

数据范围

对于 $ 40%$ 的数据有 $N≤10$ 。

对于 $ 70%$ 的数据有 $ N≤18$。

对于 $100\%$ 的数据有 $4\le N≤500$ 。保证对于不同的武将组合，其默契值均不相同。

NOIP2010 普及组第四题

[NOIP 2010 普及组] 三国游戏

目录

题意

思路

第一步：固定第一手看会发生什么

第二步：为什么这个值一定能赢

代码

复杂度

总结

一图流解析