1. 项目概述从一道经典NOIP题看博弈与贪心最近在带学生刷信奥信息学奥赛的历年真题又翻到了这道P1199“三国游戏”。这道题出自2010年NOIP普及组虽然标签是“普及组”但它的内核却非常精妙融合了图论建模、博弈论分析和贪心策略是检验一个选手是否真正理解“先手优势”和“局部最优”的绝佳试金石。很多初学者第一次看到题目描述里那个巨大的“武将默契值”矩阵时可能会有点发懵感觉无从下手。但一旦你理解了它背后的模型就会感叹出题人的巧妙——它用了一个看似复杂的游戏规则包装了一个极其优雅的数学结论。这道题的核心是让你作为玩家先手与电脑进行一场选将游戏目标是使自己选出的武将组合间的“默契值”尽可能大并判断玩家是否有必胜策略。输入是一个N*N的矩阵实际上只给了上三角部分表示N个武将两两之间的默契值。游戏规则是玩家先选一个武将然后电脑会“拆散”玩家这个武将的最强搭档即选择与玩家所选武将默契值最高的那个武将接着玩家再选电脑再拆如此循环。最终玩家和电脑各拥有N/2个武将玩家得分为自己阵营内武将配对的最大默契值。题目要求输出玩家是否能赢1表示能以及玩家能获得的最大分数。乍一看这像是一个复杂的动态规划或者搜索问题但仔细分析规则后你会发现玩家其实拥有一个“不败金身”。今天我就结合自己当年打比赛和后来教学的经验用C带你彻底拆解这道题不仅给出AC代码更重点讲清楚“为什么这么做是对的”以及编码实现时那些容易踩坑的细节。无论你是正在备赛的OIer还是对算法感兴趣的C学习者相信这篇都能让你有所收获。2. 核心思路拆解为什么玩家总能赢在动手写代码之前我们必须把题目背后的逻辑吃透。一上来就对着矩阵埋头苦想很容易迷失方向。我的习惯是先把复杂的游戏规则翻译成我们熟悉的数学模型。2.1 建立图论模型武将就是点默契就是边题目给出的那个对称的默契值表格本质上就是一个无向完全图的邻接矩阵。什么叫“完全图”就是任意两个顶点之间都有一条边相连。在这里每个武将就是一个顶点武将i和武将j之间的默契值w[i][j]就是连接顶点i和j的这条边的边权。这样一来游戏过程就变成了玩家和电脑轮流从图中挑选顶点武将。当所有顶点被瓜分完毕后玩家阵营的得分定义为玩家所拥有的顶点之间所有边权中的最大值。注意不是所有边权之和而是单条边的最大值。这一定义是理解后续策略的关键。2.2 分析电脑的“破坏”策略与玩家的应对规则规定每当玩家选择一个武将i后电脑会立刻选择与武将i默契值最高的那个武将记为best_partner[i]。电脑这个策略是固定且贪婪的它的目的很明确阻止玩家获得与武将i相连的、边权最大的那条边。那么作为先手的玩家在第一轮选中武将i后他与best_partner[i]的这条最强边就被电脑“抢走”了玩家注定无法获得它。这是否意味着玩家就亏了呢恰恰相反这揭示了游戏的第一个核心结论对于任何一个武将其关联的最大边权玩家和电脑都永远无法同时获得。因为只要一方先选了该武将另一方就会立刻抢走其最佳搭档。既然最大的边权注定拿不到玩家的策略就应该转向“次优解”。玩家在第一回合选了武将i后电脑抢走了best_partner[i]。接下来玩家再选时他完全可以去选与武将i默契值第二高的那个武将记为second_best_partner[i]。这样玩家就能稳定获得边权为w[i][second_best_partner[i]]的这条边。2.3 贪心策略与必胜性的证明现在我们把视角从单个武将扩展到全局。玩家作为先手拥有选择“发起进攻点”的主动权。他可以遍历所有武将i计算如果自己第一手选i那么最终能稳定获得的边权就是w[i][second_best_partner[i]]即该武将的次大默契值。那么玩家只要在开局时选择那个能使w[i][second_best_partner[i]]最大的武将i他就能确保自己最终获得的分数至少是这个“所有次大值中的最大值”。我们把这个值记为final_score。电脑的策略是固定的、反应式的。在玩家选择了最优的i并获得了对应的次大边后无论电脑后续如何选择它都无法获得任何一条大于final_score的边吗这里需要严谨思考电脑有没有可能通过后续操作组合出一条边权大于final_score的边答案是否定的。因为任何一条边(u, v)其边权w[u][v]要么是u的最大边权要么是v的最大边权要么同时是两者的最大边权当u和v互为最佳搭档时。根据规则只要这条边是某个顶点的最大边权那么先选中该顶点的玩家其对手电脑就会立刻抢走这条边使得这条边不可能被同一个人获得。因此游戏中任何一方都不可能获得任意一个顶点的最大边权。那么双方能争夺的就只剩下各个顶点的“次大边权”。而玩家作为先手可以主动挑选一个顶点并“预定”它的次大边权。由于电脑没有优先选择权它只能被动地破坏玩家的最大边却无法阻止玩家去获取那个预先看好的次大边。因此玩家总可以确保自己获得final_score。而电脑所能获得的最好情况也只是所有剩余顶点次大边权中的最大值这个值绝对不会超过玩家主动挑选的那个final_score因为玩家挑的就是全局最大的次大值。所以玩家必胜。输出结果的第一行永远是1。第二行要输出的就是那个final_score即所有顶点次大默契值中的最大值。注意这里有一个非常关键的思维转换点。题目问的是玩家“能否获胜”比较的是玩家和电脑最终得分的大小。我们证明了玩家得分 final_score而电脑得分 final_score且由于玩家先手选走了最优的次大边电脑的得分严格小于玩家得分的可能性很大但至少也是平局理论上可能存在平局但题目数据设定保证了玩家得分严格大于电脑得分所以输出1。很多初学者会纠结于模拟整个对战过程其实完全不需要这就是博弈题的特点——往往存在一个简洁的必胜策略。3. 算法设计与实现要点思路清晰了接下来就是用C将其实现。这里有几个技术细节需要仔细考量直接影响到代码的效率和正确性。3.1 数据存储与输入处理题目输入首先给出武将数量N然后按行输入上三角矩阵不包括对角线。例如N4输入会是w[1][2], w[1][3], w[1][4], w[2][3], w[2][4], w[3][4]。我们需要构建一个完整的N*N对称矩阵g[N1][N1]索引从1开始更符合题目习惯。#include iostream #include algorithm using namespace std; const int MAX_N 505; // 根据题目数据范围设定 int g[MAX_N][MAX_N]; int n; int main() { cin n; for (int i 1; i n; i) { for (int j i 1; j n; j) { cin g[i][j]; g[j][i] g[i][j]; // 构建对称矩阵 } } // ... 后续处理 }实操心得这里务必注意数组大小。题目虽未明确给出N的最大值但根据NOIP普及组的惯例和内存限制N通常在500左右。设置MAX_N505是一个安全且常见的做法稍微留一点余量。直接使用g[n1][n1]的动态大小在竞赛中并不推荐可能因为栈空间限制导致运行时错误。3.2 核心算法高效求取每行的次大值这是整个程序的核心也是一个经典的算法小考点如何在一个序列中用一次遍历就找到最大值和次大值最直观的方法是对每一行进行排序然后取第二大的数。时间复杂度是O(N log N)对于N500虽然也能过但不够优美也失去了锻炼思维的意义。我们追求的是O(N)的线性解法。方法一双变量维护法这是最常用且高效的方法。我们为每一行i维护两个变量max1最大值和max2次大值。初始化时可以将它们都设为0因为题目保证默契值为正整数。然后遍历该行的每一个元素g[i][j](j ! i因为对角线为0)如果g[i][j] max1说明发现了新的最大值。那么原来的最大值就变成了新的次大值即max2 max1然后更新max1 g[i][j]。否则如果g[i][j] max2说明这个值虽然没超过最大值但超过了当前的次大值那么就更新次大值max2 g[i][j]。遍历结束后max2就是该武将的次大默契值。int final_ans 0; for (int i 1; i n; i) { int max1 0, max2 0; // 每行重置 for (int j 1; j n; j) { if (i j) continue; // 跳过自己也可以通过在循环条件中避免 int val g[i][j]; if (val max1) { max2 max1; max1 val; } else if (val max2) { max2 val; } } // 更新全局答案 final_ans max(final_ans, max2); } cout 1 endl final_ans;方法二使用小顶堆优先队列另一种思路是维护一个大小为2的小顶堆。遍历元素时将其插入堆中如果堆大小超过2就弹出堆顶最小的元素。遍历完后堆里剩下的两个元素就是最大的两个堆顶元素就是次大值。这种方法同样是一次遍历但堆操作有O(log 2)的常数开销代码稍复杂在此作为拓展思路提及。避坑指南在实现双变量维护法时最易出错的是比较条件。务必使用来更新最大值以处理有多个并列最大值的情况。此时次大值应该等于原来的最大值即并列最大之一而不是保持不变。例如一行数据为[5, 5, 3]正确的次大值应该是5。如果只用第一次遇到5max15, max20第二次遇到5由于不满足val max1会进入else if (val max2)分支导致max2被更新为5这是正确的。但若数据是[5, 3, 5]用就会出错。使用是最稳妥的。3.3 复杂度分析与优化空间时间复杂度构建对称矩阵需要O(N²)计算每一行的次大值也需要O(N²)总体是O(N²)。对于N500完全在承受范围内。空间复杂度就是存储矩阵的O(N²)。这是必要的因为我们需要任意查询g[i][j]。优化遐想有没有可能不用存整个矩阵理论上我们在读取输入的同时就可以实时更新每一行的最大值和次大值。因为输入是按(i, j)对给出的我们可以同时更新第i行和第j行的状态。但这需要对输入顺序有很好的把握代码逻辑会变得复杂容易出错。在竞赛中清晰正确比极致的空间优化更重要除非数据范围大到矩阵存不下本题显然不是。4. 完整代码实现与逐行解析下面给出一个整合了上述所有要点的、带有详细注释的AC代码。我推荐使用“双变量维护法”它效率高且易于理解。#include iostream #include algorithm // 为了使用max函数 using namespace std; const int N 505; // 定义最大武将数留出余量 int main() { // 数据存储二维数组g下标从1开始使用 int g[N][N] {0}; int n; cin n; // 步骤1读入数据并构建完整的对称邻接矩阵 // 输入只包含上三角部分i j我们需要填充下三角部分 for (int i 1; i n; i) { for (int j i 1; j n; j) { cin g[i][j]; // 读入武将i和j的默契值 g[j][i] g[i][j]; // 利用对称性填充矩阵的另一半 } } // 步骤2计算最终答案 int final_score 0; // 玩家能保证获得的最大分数 // 遍历每一个武将即矩阵的每一行 for (int i 1; i n; i) { int max1 0; // 记录当前武将的最大默契值 int max2 0; // 记录当前武将的次大默契值 // 遍历当前武将与其他所有武将的默契值 for (int j 1; j n; j) { if (i j) continue; // 跳过自己对角线默认为0 int synergy g[i][j]; // 当前默契值 // 核心逻辑更新最大值和次大值 if (synergy max1) { // 发现新的最大值原最大值降级为次大值 max2 max1; max1 synergy; } else if (synergy max2) { // 值介于当前最大值和次大值之间更新次大值 max2 synergy; } } // 对于武将i玩家选择他开局后能稳定获得的分数就是max2 // 我们取所有武将中这个值的最大值 final_score max(final_score, max2); } // 步骤3输出结果 // 根据分析玩家有必胜策略第一行总是1 cout 1 endl; cout final_score endl; return 0; }代码关键点解析矩阵构建第13-18行这是处理输入的关键。for (int j i 1; j n; j)确保了只读取上三角部分。g[j][i] g[i][j];这一行完成了对称矩阵的构建使得后续查询任意g[a][b]都正确。跳过对角线第28行if (i j) continue;严格来说题目中自己对自己的默契值没有定义矩阵中这部分我们也没有初始化。加上这个判断是良好的编程习惯避免访问到未初始化的数据尽管全局数组初始化为0。更新逻辑第32-39行这是算法的灵魂。注意条件是和的区别确保了在遇到多个相同最大值时次大值能被正确更新为这个最大值。全局答案更新第43行在每一行即每个武将的次大值max2计算出来后立即用final_score max(final_score, max2);来更新全局最优解。这样只需要一次遍历即可完成。5. 测试与调试如何验证你的代码写完代码不代表万事大吉尤其是竞赛题必须用各种边界情况测试。测试用例设计最小规模测试N2。输入一个数w[1][2]。此时玩家先选1电脑必选2玩家没有第二次选择机会。玩家阵营得分为0因为阵营内只有一个武将电脑得分也为0。根据我们的算法对于武将1次大值为0因为没有其他武将了最终final_score0。输出1和0。虽然结果是平局但题目判定玩家赢符合输出。常规测试使用题目样例。输入 4 5 28 16 29 27 23 输出 1 27可以手动模拟一下验证结果是否正确。最大值相同测试构造一行中有多个相同最大值的情况验证次大值计算是否正确。输入 3 10 10 5 对应矩阵 [0,10,10; 10,0,5; 10,5,0] 对于武将1max110, max210 最终final_score应为10。最大规模测试在本地生成一个N500的随机数据测试程序运行时间和内存是否正常。调试技巧输出中间变量如果不确定可以在内层循环结束后输出每个武将的max1和max2看看是否符合预期。使用静态分析在竞赛中像本题这样逻辑清晰的题目更多时候是“想错”而非“写错”。如果结果不对优先回顾2.3节的博弈分析确认自己对“必胜”和“得分”的理解是否与题目完全一致。确保自己计算的是“次大值”而不是“第二大值”在有并列第一的情况下两者不同。6. 举一反三从本题延伸的算法思维这道P1199虽然AC代码很短但其蕴含的思想却可以延伸到很多地方。1. 博弈问题的简化思维很多博弈题看起来复杂但往往存在一个“对称性破坏点”或“先手优势点”。这道题的关键在于识破电脑的策略是固定且贪婪的从而将其转化为一个对玩家更简单的模型——电脑的每次操作反而帮助玩家排除了一个“最坏情况”。遇到类似的题不妨先思考对手的最优策略是什么这个策略是否固定我能否利用这个固定策略来规划我的行动2. 维护序列最大值/次大值的模板一次遍历求最大值、次大值甚至前k大值是一个经典问题。双变量维护法是其最简单形式。你可以试着扩展它求最小值、次小值。求最大值、最小值同时维护。求第三大的值需要维护三个变量。 这个技巧在动态规划、滑动窗口等场景中非常有用。3. 图论模型的抽象能力这道题没有显式地建图、存边但我们心里必须有一个“完全图”的模型。这种将实际问题抽象为图论模型的能力至关重要。比如以后遇到“城市间道路”、“人物亲密度”、“网络节点延迟”等描述两两关系的问题要能立刻联想到邻接矩阵或邻接表。4. 贪心策略的证明意识我们用了贪心策略玩家只需关注所有顶点次大值中的最大值。但贪心算法必须要有正确性证明或至少是 plausibility 的论证。在这道题中我们通过分析电脑的固定策略和边的归属性质证明了玩家不可能得到任何最大边而能保证得到他选中的那次大边。在做题时养成“为什么这样贪心是对的”的思考习惯能极大提升算法设计能力。最后这道题在洛谷上的难度评级是“普及-”但它考察的思维绝不简单。它完美地诠释了信息学竞赛的魅力用简洁的代码解决蕴含深刻数学原理的问题。希望这篇详细的拆解能帮你不仅通过这道题更能理解其背后的逻辑从而在遇到“P1199 Plus”版本的题目时也能游刃有余。编程刷题理解永远比死记硬背代码更重要。