P1199 三国游戏网特链接P1199 三国游戏题目描述小涵很喜欢电脑游戏这些天他正在玩一个叫做《三国》的游戏。在游戏中小涵和计算机各执一方组建各自的军队进行对战。游戏中共有N NN位武将N NN为偶数且不小于4 44任意两个武将之间有一个“默契值”表示若此两位武将作为一对组合作战时该组合的威力有多大。游戏开始前所有武将都是自由的称为自由武将一旦某个自由武将被选中作为某方军队的一员那么他就不再是自由武将了换句话说所谓的自由武将不属于任何一方。游戏开始小涵和计算机要从自由武将中挑选武将组成自己的军队规则如下小涵先从自由武将中选出一个加入自己的军队然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→ \to→计算机→ \to→小涵→ … \to\dots→…”的顺序选择武将直到所有的武将被双方均分完。然后程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武拥有更高默契值的一对武将组合获胜表示两军交战拥有获胜武将组合的一方获胜。已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合它采取的具体策略如下任何时刻轮到计算机挑选时它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对找出所有配对中默契值最高的那对武将组合并将该组合中的自由武将选入自己的军队。 下面举例说明计算机的选将策略例如游戏中一共有6 66个武将他们相互之间的默契值如下表所示武将编号12345615 5528 282816 161629 292927 272725 5523 23233 3320 20201 11328 282823 23238 8832 323226 2626416 16163 338 8833 333311 1111529 292920 202032 323233 333312 1212627 27271 1126 262611 111112 1212双方选将过程如下所示小涵轮到计算机时可选的自由武将计算机计算机选将说明第一轮5 551 , 2 , 3 , 4 , 6 1,2,3,4,61,2,3,4,64 \color{magenta}44小涵手中的5 55号武将与4 44号的默契值最高所以计算机选择4 44号。第二轮5 , 3 5,35,31 , 2 , 6 1,2,61,2,64 , 1 4,\color{magenta}14,1小涵手中的5 55号和3 33号武将与自由武将中配对可产生的最大默契值为29 2929是由5 55号与1 11号配对产生的所以计算机选择1 11号。第三轮5 , 3 , 6 5,3,65,3,62 224 , 1 , 2 4,1,\color{magenta}24,1,2小涵想知道如果计算机在一局游戏中始终坚持上面这个策略那么自己有没有可能必胜如果有在所有可能的胜利结局中自己那对用于比武的武将组合的默契值最大是多少假设整个游戏过程中对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题保证对于不同的武将组合其默契值均不相同。输入格式共N NN行。第一行为一个偶数N NN表示武将的个数。第2 22行到第N NN行里第i 1 i1i1行有N − i N-iN−i个非负整数每两个数之间用一个空格隔开表示i ii号武将和 $i1,i2,\dots,N $ 号武将之间的默契值0 ≤ 默契值 ≤ 10 9 0 \le \text{默契值} \le 10^90≤默契值≤109。输出格式共一或二行。若对于给定的游戏输入存在可以让小涵获胜的选将顺序则输出 $ 1$并另起一行输出所有获胜的情况中小涵最终选出的武将组合的最大默契值。如果不存在可以让小涵获胜的选将顺序则输出0 00。输入输出样例 #1输入 #16 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12输出 #11 32输入输出样例 #2输入 #28 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输出 #21 77说明/提示数据范围对于 $ 40%$ 的数据有N ≤ 10 N≤10N≤10。对于 $ 70%$ 的数据有 $ N≤18$。对于100 % 100\%100%的数据有4 ≤ N ≤ 500 4\le N≤5004≤N≤500。保证对于不同的武将组合其默契值均不相同。NOIP2010 普及组 第四题解题思路本题核心是博弈论结论推导无需模拟复杂选将过程直接通过规律求解最优解。根据游戏规则与计算机的破坏策略可得出关键结论小涵必定必胜对于任意一个武将其默契值最高的搭档一定会被计算机抢走但第二高的搭档小涵一定能成功选中。因此我们只需要遍历每一个武将找到该武将所有默契值中的第二大值再取所有武将第二大值中的最大值即为小涵能获得的最优默契值。算法仅需排序与遍历时间复杂度O ( N 2 log ⁡ N ) O(N^2\log N)O(N2logN)完美适配N ≤ 500 N≤500N≤500的数据规模。总结核心逻辑利用博弈策略计算机只能抢走每个武将的最优搭档小涵保底能拿到次优搭档取所有次优值的最大值。关键操作构建对称默契值矩阵、每行排序取第二大值、全局取最大值。效率保障结论式解法无复杂模拟简洁高效且100%正确。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M1e610;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cinn;vectorvectorinta(n1,vectorint(n1));for(inti1;in;i)for(intji1;jn;j){cina[i][j];a[j][i]a[i][j];}intans0;for(inti1;in;i){sort(a[i].begin()1,a[i].begin()n1);ansmax(ans,a[i][n-1]);}cout1\nans\n;return0;}