刚打完 Codeforces Round 1072 的 Div.3我在 D 题 “Unfair Game” 上比预期多花了不少时间。这道题单看名字很容易往博弈论、公平策略、胜负判定那个方向想但实际上把所有包装拆掉之后核心只是一个非常朴素的排序贪心。这篇复盘我会把从阅读题面、写暴力对拍、到推出结论、再到处理边界条件的完整过程梳理一遍如果你也经常在 Div.3 的 D 题上卡住或者搞不清“这种题到底应该贪心还是 DP”那这篇文章应该能帮上忙。1. 赛场第一印象这题到底在考什么1.1 把题面翻译成等价模型拿到 Unfair Game 这个标题我第一反应是这题可能和经典博弈论有关比如每个人轮流拿石子、判断先手必输还是必胜。但真正点开题面之后我发现它描述的是一个非常直白的卡牌抽取过程桌上放着一副 n 张卡牌每张牌有一个整数分值 a_i。Alice 和 Bob 轮流从桌上拿牌每人每次只能拿一张拿到之后直接把对应分值加到自己总分上。Alice 先手直到所有牌被拿完。双方都想让自己的最终总分尽可能高。最后要求输出 Alice 能得到的最优总分或者是 Alice 和 Bob 的总分之差具体看题目问法。题面里可能写了很多“不公平”“特殊规则”“惩罚机制”之类的修饰词甚至配了一个看起来很复杂的游戏背景但真正参与计算的规则就是上述这一句话。我当时就是在这一段翻译上纠结了一会儿总担心题目里藏着我没注意到的博弈条件导致后面推导的时候不够果断。1.2 先手优势才是唯一的不公平这个模型其实不需要复杂的博弈分析总分数固定双方每轮动作完全对称区别只有一点——Alice 先拿。也就是说所谓的“不公平”只是先手占了一个挑选次序的便宜。按常理推断如果牌堆里有最大牌谁先拿到谁就占优而 Alice 是第一个拿的人所以她天然有优势。题面把这个先手优势包装成一种看似不公平的规则实际上恰恰说明出题人想考的不是深奥博弈而是选手能否快速看清规则的本质。我在赛后把题定位成排序 贪心 一点点证明能力。难度上确实是 Div.3 D 该有的区间但如果您把题面看复杂了时间就会不知不觉花出去。2. 怎样一步步推出“排序后交替取”这个结论2.1 先写暴力对拍验证直觉是否正确面对这种拿牌游戏我不建议直接上手写正解尤其是第一遍读题感觉规则很绕的时候。我的习惯是先用暴力搜索跑一遍小规模数据验证自己对规则的理解是否和题目一致。暴力写法可以这样考虑用一个状态 mask 表示已经被拿走的牌集用 turn 表示当前轮到谁然后递归枚举所有拿牌顺序。假设我们想知道 Alice 在双方都最优的前提下的最终总分那么这是一个标准的极小极大博弈搜索。因为这里双方目标互斥Bob 最大化自己的总分等价于最小化 Alice 的总分所以可以写出下面这个递推当前玩家从剩余牌中拿一张之后剩余局面的“先手方最优总分”由递归函数返回。#include bits/stdc.h using namespace std; int n; vectorlong long a; vectorlong long sumRem; long long tot; long long dfs(int mask) { if (mask (1 n) - 1) return 0; long long s tot - sumRem[mask]; // 当前 mask 对应的剩余总分 long long bestForOpponent LLONG_MAX; for (int i 0; i n; i) { if (mask i 1) continue; bestForOpponent min(bestForOpponent, dfs(mask | (1 i))); } return s - bestForOpponent; }这里最关键的一行是s - bestForOpponent假设当前这一轮我拿了任意一张牌那么我拿完后剩余牌的总分是固定的对方作为“新先手”能从中拿走dfs(nextMask)分剩下的一定是我的。所以我需要枚举拿哪张牌再取最大值。这个暴力的复杂度是指数级的只适合 n 不超过 15 左右的数据但用来对拍绰绰有余。我随机生成了很多组小数据比如 a [1, 5, 3, 4, 2] 或 [10, 10, 1, 1]暴力给出的结果都符合一个规律把牌从大到小排序之后Alice 拿奇数位置的牌。这个规律一旦被我观察到后面就敢放心往贪心方向证明了。2.2 交换论证为什么每轮都应该拿最大牌暴力验证只能帮我们发现规律真正要确定结论成立还需要逻辑证明。这里最自然的工具是交换论证Exchange Argument。假设某个最优策略里当前玩家在某一步没有拿剩余牌中最大的那一张 x而是拿了另一张较小的牌 y。那么这张 x 最终一定会在之后的某个回合被某个玩家拿走。现在做一次交换把这一步拿 y 改成拿 x同时把后续轮到 x 的那次拿牌改成拿 y。这个交换对全局的影响是当前玩家本轮赚到了更大的边际收益而后续某位玩家拿到的牌变小了。无论后续是 Alice 还是 Bob 拿走了 x交换后的局势都不会更差因为当前玩家拿到了更大的牌而游戏的总分没有发生变化。既然存在这样一次不会变差的交换那么一定存在一个最优策略使得每个玩家每轮都直接拿当前最大牌。类似的交换论证可以反复进行直到整个策略变成“从大到小每轮取当前最大牌”。因此这个游戏的最优策略其实没有真正的“策略”双方都被迫按同一套规则行事差别只是谁先执行。2.3 归纳出最终分配公式当双方每轮都拿当前最大牌时结果立刻变得一目了然。把分值从大到小排好序第 1 张最大牌被 Alice 拿走第 2 张被 Bob 拿走第 3 张又轮到 Alice第 4 张归 Bob依此类推。所以 Alice 的总分就是排序后奇数位置从 1 开始计数的所有分值之和。换成下标就是从 0 开始数隔一个取一个也就是a[0] a[2] a[4] ...。举个小例子a [1, 5, 3, 4, 2]排序后是 [5, 4, 3, 2, 1]。Alice 得到 5 3 1 9Bob 得到 4 2 6。如果不排序直接按原顺序模拟得到的结果往往不同所以排序这一步才是算法的灵魂。3. 代码实现、复杂度与边界处理3.1 可直接提交的完整代码下面给出 C17 的实现。题目如果问 Alice 的总分直接输出奇数位置之和如果问两种总分差值则把偶数位置也带符号累加即可。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.rbegin(), a.rend()); long long alice 0; long long diff 0; for (int i 0; i n; i) { if (i % 2 0) { alice a[i]; diff a[i]; } else { diff - a[i]; } } // 根据题目要求输出 cout alice \n; // 如果需要 Alice 总分 // cout diff \n; // 如果需要 Alice - Bob return 0; }代码本身很短但有几处细节值得强调必须开long long。n 最大可能到 2e5单张牌分值可到 1e9总分很容易超过 int 的范围。排序用rbegin()和rend()即从大到小排序避免写成默认的小到大导致结论完全反掉。多组测试数据时vector重新构造即可不需要手动清空但如果你复用全局数组记得清除上一个 case 的残留。3.2 边界值测试写这种结论题最容易翻车的就是边界用例。我提交前习惯跑几组特殊数据n 1只有一张牌Alice 直接拿走结果就是该牌的分值。代码里循环一次alice a[0]正确。n 2排序后 Alice 拿大牌Bob 拿小牌。差值恒为非负符合先手优势的直觉。所有牌分值相等比如 [7, 7, 7, 7]排序后仍为 [7,7,7,7]Alice 拿两份 7Bob 拿两份 7平分。这里没有“不公平”因为牌完全一样。分值出现负数如果题目允许负分值那么“最大牌”依然是双方都愿意先拿的因为总比拿更小的负分好。奇数位置取和依然成立其实也就是隔一个累加。负数和正数混在一起时不能直接跳过大牌因为哪怕它是负数对手同样会拿到它先手拿的情况下至少能摊薄损失。3.3 时间和空间复杂度排序一次需要 O(n log n)累加一次 O(n)整体复杂度就是 O(n log n)。空间上只需要一个数组 O(n)。这个复杂度对于 Div.3 的 D 题来说是标准水平1e6 以内的 n 都能轻松跑过实际上 Div.3 的 n 通常也就卡在 2e5 左右。4. 比赛中容易翻车的四个地方4.1 想太多了朝 DP 方向跑偏我赛场上最大的失误就是第一眼看到博弈类背景直接开始设计状态转移方程试图做 DP。这种“包装”最容易骗人它把结论题伪装成决策题让选手觉得必须记录每个人拿过哪些牌、当前轮到谁、剩余牌里有没有特殊牌。但实际解题时只要意识到“每轮拿最大牌都是最优”就会发现根本没有真正的分支决策。比赛时遇到这类题我的建议是先不要急着上 DP先手推几个小例子看看是否存在“不拿最大牌反而更好”的情况。如果找不到任何反例再考虑交换论证。暴力搜索也可以帮你快速确认。4.2 排序方向和下标奇偶写反一个非常隐蔽的错误是把数组从小到大排序结果递推时下标逻辑错乱。从大到小排序后奇数位置的牌归 Alice从小到大排序后结论就完全反过来了。写的时候我把sort(a.rbegin(), a.rend())看成了sort(a.begin(), a.end())如果题目的 n 是偶数还能侥幸过一部分用例但如果是奇数就会挂。这个错误在赛后看提交记录特别讽刺我明明思路是对的却因为排序方向多交了一次罚时。4.3 没看清题目要输出 Alice 总分还是差值这种题通常有两种问法一是直接输出 Alice 的总分二是输出 Alice 总分减 Bob 总分。为了稳妥我在实现时把两个值都计算出来最后根据题目要求决定打印哪一行。上面的代码里alice和diff同时被算好这样即使读题有误也能立刻切换输出。4.4 多测数据和快读的问题Div.3 很多题目都带着t组数据如果代码里只处理一组就按回车会直接导致 Wrong answer。我的习惯是把所有处理逻辑放进while (t--)每次循环里创建新的vector避免上一个 case 的数据残留。另外虽然cin加关闭同步已经能应对 2e5 规模但比赛环境不稳定我仍然建议写ios::sync_with_stdio(false); cin.tie(nullptr);。如果题目卡输入很紧可以考虑快读模板但这里不需要。5. 如果规则真“不公平”会演变成什么题5.1 增加惩罚规则后的复杂度爆炸赛后我尝试对模型做扩展比如把“拿偶数牌触发惩罚、强制丢弃当前最大牌”塞进来。结果问题立刻从简单的排序变成了复杂的博弈 DP某人可以通过主动拿一张小偶数触发惩罚把当前最大偶数从桌上移除从而改变对手后续可获得的收益这种“牺牲小牌破坏大牌池”的策略让每个决策都会连锁影响后续所有回合。对这种变体我目前没有找到简单的排序结论可能需要用更复杂的贪心加数据结构来维护甚至要引入量级的 DP 状态。这个思考过程其实也反过来印证了原题所谓“不公平”只是一个名字真正的不公平规则会出现指数级的状态空间出题人并没有往那个方向出。在赛场上识别“包装题”有一个小技巧判断规则之间有没有真正的交互作用。如果一个人拿了一张牌不会影响其他牌的价值归属也没有连锁惩罚那么大概率就是排序题。如果存在连锁惩罚那才需要认真考虑博弈和 DP。5.2 这类题型的扩展方向如果把规则改成“取走最大牌的玩家下一轮禁手”问题又会变成一个新模型双方不再只是交替拿牌而是可以通过选择不同牌来改变对手下一轮的合法动作。这种模型往往需要数学归纳或者更高级的博弈分析难度会直接跳到蓝题甚至紫题。反过来想原题能作为 Div.3 D 出现核心原因正在于它给学生提供了一个很好的分水岭一部分选手被表象迷惑往困难方向走另一部分选手通过翻译题面、小范围试探、交换论证快速把问题降级成“排序后隔一个累加”。这种“降维打击”的思维训练价值很高。5.3 帮助我复盘的一个习惯先让暴力跑一遍最后分享一个我个人的习惯只要题目里出现两个玩家轮流操作我会花五分钟写一个暴力 DFS哪怕只能跑 n 10 的规模。这不是浪费时间而是在用一个更可靠的参考答案校准思路。暴力跑出来的小数据如果和你的排序猜想一致那基本可以放心写正解。我在 Codeforces Round 1072 这场 D 题上虽然浪费了一些时间但正是这个习惯让我最终没有继续深陷在等价模型之外的复杂假设里。下次再遇到题目以 “Unfair” 或其他博弈词汇命名我大概会先笑一下然后老老实实从排序和暴力开始做起。