在讲解三国游戏这道真题前，我们先来解决上一节课的题目，这 是博弈论的入门题目。

1.博弈论入门

你和你的朋友，两个人一起玩游戏：桌子上有一堆石头，每次你 们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。 你作为先手。 你们是聪明人，每一步都是最优解。 编写一个程序，来判断你是 否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4 输出: false 解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛； 因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会 被你的朋友拿走。 这个题目的典型特征： 只有两个玩家，游戏规则固定，游戏里面 有可变的数据（这题是石头的数量），询问你是否必胜？ 看到这种描述你就要明白，你遇到一个博弈论的题目啦，千万注 意绝对不是让你用程序去模拟题目的游戏过程再得出结果的。你 要在脑中分析出过程，重点分析两点： 1.什么时候可以判定胜利者， 2.先手的影响。 题目描述了石头数量为 4 的情况，数量为 4 的时候先手的那个人 必输，因为他一次拿不完，但是又不得不拿，不管他拿多少后手 的人只要把剩下的都拿完就赢了。这个时候发散思维就派上用场 了，这个示例给我们的启示是：只要场上剩下的石头数量是 4 的 倍数，那么后手必胜，假设这一轮先手的一方拿了a个，那么后手 的一方就拿 4 - a 个，按照这样的玩法，每轮消耗4块石头。玩完 最后一轮后手就赢了。 所以这个游戏后手必胜规则是：当石头数量是 4 的倍数。 因为后手输了就代表先手赢了，所以先手必胜的条件是反着的： 当石头数量不是 4 的倍数。 到这里这个题目已经解出来了，如果你好奇石头数量不能被 4 整 除时先手怎么赢的，那么可以看这里: 对于这个游戏来说，假设原本的游戏规则是共有 n 个石头，A 先 手，B后手，如果 A 总是先手拿 m 个石头，那么这个游戏等同于 共有 n - m 个石头，B 先手， A 后手的一场游戏。所以，当石头 数量不能被 4 整除的时候，先手拿走被4整除的余数数量的石头就 能保证必胜。 拿石头这个游戏是经典的“巴什博弈”，

例题描述

小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游 戏。 在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。 游戏中共有N 位武将（N为偶数且不小于4），任意两个武将之间 有一个“默契值”，表示若此两位武将作为一对组合作战时，该组 合的威力有多大。游戏开始前，所有武将都是自由的（称为自由 武将，一旦某个自由武将被选中作为某方军队的一员，那么他就 不再是自由武将了），换句话说，所谓的自由武将不属于任何一 方。游戏开始，小涵和计算机要从自由武将中挑选武将组成自己 的军队，规则如下：小涵先从自由武将中选出一个加入自己的军 队，然后计算机也从自由武将中选出一个加入计算机方的军队。 接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将，直 到所有的武将被双方均分完。然后，程序自动从双方军队中各挑 出一对默契值最高的武将组合代表自己的军队进行二对二比武， 拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜 武将组合的一方获胜。

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

下面举例说明计算机的选将策略，例如，游戏中一共有6 个武 将，他们相互之间的默契值如下表所示。

双方选将过程如下：

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

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

输入输出格式

输入格式： 共 N 行。 第一行为一个偶数 N,表示武将的个数。 第 2 行到第 N 行里，第i+1行有Ni个非负整数，每两个数之间用 一个空格隔开，表示 i 号武将和 i+1,i+2,…,N 号武将之间的默契值 （0≤默契值≤1,000,000,000)。

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

输入输出样例 输入样例#1： 6 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12 输出样例#1： 1 32 输入样例#2： 8 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： 1 77

说明

【数据范围】 对于 40% 40%的数据有 N≤10。 对于 70% 70%的数据有 N≤18。 对于 100%的数据有 N≤500。

首先我们要明确这是一个博弈论的题目，不要去模拟过程，想办 法分析获胜的方式。计算机和玩家对抗的方式比较傻，第一感觉 是玩家肯定能赢，这个题有10 组用例，如果玩家输了只需要输出 0即可，如果这个游戏真的有输有赢，那直接cout<<0; 的同学肯 定能得一部分分数，所以我直接输出 0 然后提交了代码，结果一 分未得，说明在博弈论的视角下，这个游戏的玩家是必胜的。所 以最终输出的格式肯定是 1 X X 如何得到呢，读懂题意不难发现 X 是一组武将的默契值，这个 数不是计算出来的，而是输入数据中的某个数字，而且按照题意 这个数字越大越好，对比了一下两个用例，第一组用例输出的是 32， 第二组输出的是 77. 刚好都是所有数据中第二大的数字，由 于计算机的阻挠，玩家不可能选到默契值最大的武将组合，那么 玩家最终获胜的数字是否是次大的那个数字呢？为了验证我的猜 测，我写了个很简单的程序，找到所有输入数据中第二大的数 字，结果只得了 20 分，也就是说真实的情况没这么简单，刚好只 有这两组示例用例满足我的猜测而已。 看来这题没法继续骗分了😈，我必须得认认真真分析了。对比巴 什博弈的题目，我要从题目给的唯一的一组选将过程中寻找答 案。巴什博弈中不管石头总数有多少，每一轮玩家都要想办法拿 4 - a 块石头。那么这个游戏中小涵是如何选择的呢？

我把小涵和电脑玩的那一局复盘了一下，由于计算机是被动的跟 着小涵选的，所以我们只要分析出小涵3次选将的依据，这个题就 做出来了。横着看上图，小涵第一次拿了 5，第 5 行确实大数字 很多，计算机为了阻挠小涵，所以拿了 4，这样小涵就拿不到默 契值为 33 的组合了。这个时候小涵选择了 3，计算机选了 1，对 比这两步可以发现，小涵前两轮拿到了 32 这个默契值，而这个默 契值是全场第二高的，这是我刚才分析过的，结果已经被证明是 片面的想法了。 正确的思路是：小涵和电脑都拿不到每个武将的最大默契值，因 为小涵每拿起最大组合的其中一个，另一个就被电脑拿走了，但 是电脑也无法占有该组合的最大值，因为另一个在小涵手里，这 个组合的最大值其实就作废了。但是小涵在第二次选将时可以拿 到第一次选中的武将的次大默契值组合。在双方都拿不到最大默 契值的情况下，显然谁拿到次大默契组合的最大值，谁就赢了。 以示例中的选将为例，武将1-6的次大默契值罗列出来：

小涵拿到 5 和 3 之后，小涵就已经赢了，电脑拿了4之后无法组 合出比 32更大的值。所以按照这个逻辑，小涵第一轮和第二轮拿 到 5 和 3，剩下的几步就可以随便选了。

3.二维数组

题目中给出的武将之间的对照关系是一个 N x N 的矩阵，在编程 中经常用二维数组保存“两两之间的关系”，比如讲到图论部分的 时候，我们会使用“邻接矩阵”保存点与点之间的连通关系，邻接 矩阵实际就是一个简单的二维数组而已。那么什么是二维数组 呢？ 数组： 线性表的一种，它用一组连续的内存空间，来存储具有相 同类型的数据。 我们已经接触过 int 数组和 char 数组了，完全符合上面的定义。 既然只要是相同类型的数据既可以放在数组中，那么如果数组中 的元素本身也是数组的话，就衍生出我们这次要用到的结构二维 数组了。 来练练手吧，默契值的矩阵是按照对角线对称的，输入数据的数 量只够填充其中的一半，所以在一边输入一边构造矩阵的时候要 把对称位置的数据一并填充。

#include<bits/stdc++.h>
using namespace std;
//放到 main 外面去定义可以得到的好处：数组 mo 的中所有元素都
会被默认赋值为 0
int mo[501][501],n;
int main()
{
cin>>n;
// 构造二维数组要用嵌套的 fo r循环，i 写入到数组第一维，j
写到数组第二维
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
cin>>mo[i][j];
//(i,j) 的对称位置是(j,i)
mo[j][i]=mo[i][j];
}
}
cout<<endl;
//写完了不急着写后面的代码，我们先把刚才构造的二维数组打
印一下看看
//注意打印时的嵌套for循环的范围跟写入时的差别
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
//每个元素使用空格间隔
cout<<mo[i][j]<<" ";
}
//一行打印完了换行
cout<<endl;
}
return 0;
}

结果如下图，上面的倒三角是我们输入的数据，下面的数字矩阵 是我们生成的二维数组中保存的值。

4.二维数组解题

上面我们使用了二维数组的构造以及遍历，现在你需要计算出二 维数组每一行中的次大值，这个任务更复杂一些。你可以把每一 行当做一个数组去做，找数组中第二大的值应该难不倒你，用两 个额外的变量保存最大值和次大值就行。另外也可以直接用 sort 函数把数组排序，这样你可以很容易地得到“第N大”的元素了。 我这里展示第二种解法，你可以直接对照下面的解法来思考，我 在关键的地方都加了注释。

#include<bits/stdc++.h>
using namespace std;
//放到 main 外面去定义可以得到的好处：数组 mo 的中所有元素都
会被默认赋值为 0
int mo[501][501],n;
int main()
{
cin>>n;
// 构造二维数组要用嵌套的 fo r循环，i 写入到数组第一维，j
写到数组第二维
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
cin>>mo[i][j];
//(i,j) 的对称位置是(j,i)
mo[j][i]=mo[i][j];
}
}
//ans 保存二维数组每一行次大值中的最大值
int ans = 0;
//对数组的第二维进行排序
for(int i=1;i<=n;i++)
{
//对 mo 的每一行都排序，sort 默认是从小到大的
sort(mo[i],mo[i]+n+1);
//排序后每一行第二大的值是 mo[i][n-1]
if(mo[i][n-1] > ans)
ans = mo[i][n-1];
}
cout<<1<<endl<<ans;
return 0;
}