ICPC 的现场滚榜大家都看过封榜之后大屏幕上每点亮一道题下面就有队伍的名次往上蹿一截观众席跟着一阵惊呼。洛谷 P9670 这道 [ICPC 2022 Jinan R] Frozen Scoreboard就是把这段滚榜过程压缩成了一道模拟题。表面看是模拟但封榜、提交次数、罚时这几个概念混在一起时特别容易把细节改错。这篇文章按我自己做这道题的思路来拆从滚榜模型到 C 实现再到边界情况一次性说清楚。适合刚学完基础模拟、想拿这种“普及”题练手的选手也适合准备区域赛、想复习滚榜规则的 ACM 选手。1. 先把滚榜流程翻译成程序能处理的状态机很多模拟题写起来乱不是因为代码长而是因为没把题目里的“过程”翻译成“状态变化”。Frozen Scoreboard 也不例外。我先不在代码细节上纠缠而是把一场真实比赛里封榜和滚榜的流程理清楚后面写代码就是照着翻译。1.1 封榜计分板不是最终结果比赛进行到某个时间点一般是最后一小时会封榜。封榜之后所有提交仍然会被评测但结果不会立刻显示在公共计分板上。所以封榜时刻我们看到的那块“冻结计分板”记录的是每个队每个题在封榜前的结果。每个题在冻结板上只有三种状态还没提交过提交过但没通过已经通过并且能看到通过时间和提交次数。这里有个非常关键的细节对于已经通过的题封榜时刻显示的提交次数是“包括 AC 那次在内的总提交次数”。比如某题提交了 3 次最后一次 AC那么计数是 3罚时用的是通过时间加上 2 次错误提交的惩罚。而没通过的题记录的是封榜前已经产生的错误提交次数。我为什么要把这个区分拎出来说因为后面滚榜时罚时的计算公式跟这个定义直接挂钩。搞混一次WA 一晚上。1.2 一次揭示事件到底改了哪些变量滚榜时组委会会逐条揭示封榜后的通过提交。每次揭示给定三个信息哪个队、哪道题、在什么时间 AC。程序要做的就是把这次揭示“应用”到计分板上。一次揭示触发的变化有三个该队这道题从“未通过”变成“已通过”AC 数加 1该队总罚时增加一个增量计分板上的排名需要重新算一遍。罚时增量不是简单的 AC 时间而是AC时间 20 * 该题此前的错误提交次数。这个公式是把“历史欠账”一次性结清这道题在封榜前错了一次当时没有罚时因为没通过现在通过了那一次错误提交就要按 20 分钟计入总罚时。举个例子某队某题封榜前错了 3 次封榜后第 241 分钟 AC罚时增量就是 241 20 × 3 301。如果漏掉那 60 分钟后面所有排名比较都会出问题。1.3 排序规则AC数和罚时谁优先ICPC 排名规则是固定的AC 数多的队伍排在前面AC 数相同时总罚时少的排在前面如果 AC 数和罚时都一样一般按队伍编号从小到大排。第三个规则每个赛区可能略有差异但题目一定会写在输入样例或规则说明里。写排序函数时老老实实把三个条件都写进去不要想当然只用前两个。这样做还有一个好处排序函数是严格弱序的用std::sort不会出现未定义行为。2. 最容易翻车的三个细节代码本身不长但我自己第一次写这道题时在三个细节上各栽过一次。这三个地方如果不注意样例也许能过交上去就是红色一片。2.1 wrongCnt 要不要在 AC 后自增这是我最开始写错的地方。我在事件处理里把“该题错误次数”在 AC 后加了一理由是“这次提交也算一次提交”。但仔细想一下罚时公式里的wrongCnt指的是 AC 之前错误提交的次数AC 那次不是错误提交所以AC 之后 wrongCnt 不应该变。如果题目后续需要“总提交次数”那应该单独用一个字段保存而不是在 wrongCnt 上做手脚。我建议结构体里只维护两个量wrong表示该题当前已经错误提交的次数acTime表示通过时间。passed标记是否已经通过。已经通过的题wrong就没有再使用的必要了罚时早在第一次 AC 时就定格了。2.2 罚时计算为什么必须用 long long很多选手看到“普及”就觉得 int 足够实际上这是个隐患。AC 时间最大可以到 300单题罚时最大大概是 300 20 × 提交次数。如果某题提交次数很大比如几十次单题罚时就能到四位数。一支队伍 m 道题加起来再乘上 n 个队伍的总罚时排序时一旦发生比较int 桶很容易溢出。我曾经在一个类似题里用 int 存罚时本地测试没问题但交上去在边界数据上 WA。后来改成long long就过了。这种题罚时不是核心考点没必要在类型上给自己埋雷。所有跟罚时相关的变量、返回值、排序比较里的临时量一律用long long。2.3 已 AC 的题再次出现在揭示队列怎么办真实比赛里一道题不可能被通过两次但有经验的选手会做防御性判断。如果数据没有保证“同一道题只会被揭示一次”那么当遇到一个passed true的题时直接忽略这次事件不更新 AC 数也不更新罚时继续处理下一条。有人会觉得这是多此一举但我在区域赛训练时见过不少题数据生成器会故意塞一些边界输入。多做一次if (prob.passed) continue;不亏反而能让思路更清晰只有真正能让状态变化的事件才值得处理。3. 完整C实现与复杂度分析下面是我按上述模型写的 C17 代码。为了把逻辑说清楚我自定义了一种简洁的输入格式每个队伍有 m 行每行先读一个op然后按op读后续参数。实际做题时把读取部分换成原题输入格式即可其余模拟逻辑完全一样。3.1 用 struct 把两个核心字段钉死#include bits/stdc.h using namespace std; struct Problem { int wrong 0; // 该题已产生的错误提交次数 int acTime 0; // 通过时间未通过时无意义 bool passed false; }; struct Team { int id; int ac 0; long long penalty 0; vectorProblem prob; };一个队伍的核心数据只有三个AC 数、总罚时、每道题的状态。把penalty定义成long long后面所有加法都不需要再考虑溢出问题。3.2 主循环里的三步更新int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; vectorTeam teams(n); for (int i 0; i n; i) { teams[i].id i 1; teams[i].prob.resize(m); for (int j 0; j m; j) { int op; cin op; if (op 0) { // 未提交过什么都不用读 } else if (op 1) { // 提交过但未通过读错误次数 cin teams[i].prob[j].wrong; } else { // 已经通过读总提交次数和 AC 时间 int total, t; cin total t; teams[i].prob[j].acTime t; teams[i].prob[j].passed true; teams[i].prob[j].wrong total - 1; // 最后一次是 AC前面 total-1 次是错误 teams[i].ac; teams[i].penalty 1LL * t 20LL * (total - 1); } } } auto cmp [](const Team a, const Team b) { if (a.ac ! b.ac) return a.ac b.ac; if (a.penalty ! b.penalty) return a.penalty b.penalty; return a.id b.id; }; while (q--) { int x, y, t; cin x y t; --x; --y; Problem prob teams[x].prob[y]; // 防御已经 AC 的题不会被再次揭示 if (prob.passed) continue; // 这次 AC 让总罚时增加AC时间 之前错误次数 * 20 teams[x].penalty t 20LL * prob.wrong; prob.passed true; prob.acTime t; teams[x].ac; sort(teams.begin(), teams.end(), cmp); } for (int i 0; i n; i) { cout teams[i].id \n; } return 0; }这段代码把每一步都写在明面上没有太多黑魔法。op 2时读入的total和acTime就是封榜计分板上已经显示的信息所以初始化时直接算好罚时和 AC 数。后续每次揭示只是把一个“未通过”的题目变成“已通过”并补交罚时。3.3 这题的复杂度到底卡在哪假设有 n 个队伍、m 道题、q 次揭示事件。每次事件后都排一次序排序复杂度是 O(n log n)总复杂度 O(q n log n)。如果 n 很小、q 是几百量级这个复杂度毫无压力。但如果 n 达到几千、q 也很大每次全排序就不太行了。题目叫“普及”数据范围通常不会大到需要高级数据结构。真要遇到大范围可以考虑用“懒排序”或者只维护受影响队伍与当前冠军之间的比较但那种优化属于后话。做模拟题的第一步永远是按题意直接写先保证逻辑对再考虑效率。4. 小样例手动对拍排名是怎么变化的光看代码不如手动推一个样例。下面我构造一个 n3、m2、q2 的小数据把排名变化逐步写出来方便对照代码行为。4.1 样例从落后到反超的全过程初始封榜状态队伍 1题 0 已通过总提交 1 次AC 时间 100题 1 未通过错误次数 2。所以 AC1罚时 100。队伍 2题 0 已通过总提交 2 次AC 时间 240题 1 未提交。AC1罚时 240 20 × 1 260。队伍 3题 0 未通过错误次数 1题 1 未提交。AC0罚时 0。初始排序排名队伍AC数罚时1111002212603300第一次揭示队伍 3 的题 0 在 250 分钟 AC。队伍 3 总罚时变成 0 250 20 × 1 270AC 数变成 1。排序后排名队伍AC数罚时111100221260331270队伍 3 虽然 AC 了但罚时太高名次没动。第二次揭示队伍 3 的题 1 在 260 分钟 AC。该题此前错误次数为 0所以罚时增量就是 260。队伍 3 的 AC 数变成 2罚时变成 270 260 530。排序后排名队伍AC数罚时132530211100321260队伍 3 直接跳到第一。这才是滚榜最有意思的地方一次 AC 不一定立刻改变位置但连续两次 AC 就可能完成反超。4.2 对照代码逐行看结果上面样例对应代码读入时队伍 1 的题 0 是op2 total1 time100题 1 是op1 wrong2队伍 2 的题 0 是op2 total2 time240队伍 3 的题 0 是op1 wrong1。两次揭示分别是3 0 250和3 1 260。程序输出最终排名3 1 2和手推结果一致。我建议读者在本地跑这个样例时加上在每次sort后打印当前排名的调试代码能很直观地看到每一步变化。模拟题里“中间状态”比“最终答案”更容易错肉眼确认中间状态是排错的好办法。5. 换个问法也能打双榜单合法性判定写完滚榜模拟后我突然想到这道题可能还有另一种出法这也是我最初看题名时误会的方向给定封榜计分板和最终计分板问这两个榜单是否可能来自同一场比赛。如果你的版本是这样上面的模拟框架只需要改一小部分。5.1 终榜信息完整时可以直接 check假设输入给出了终榜上每队每题的完整结果是否 AC、总提交次数、AC 时间。我们要判断这个终榜是否由某个冻结板演化而来本质上是要检查三个约束冻结板已经 AC 的题终榜必须仍然 AC且 AC 时间完全相同冻结板未 AC 的题终榜可以仍然未 AC也可以在封榜后 AC但 AC 时间必须大于封榜时刻每道题终榜的总提交次数不能小于冻结板上已有的提交次数。用表格表示更清楚冻结状态终榜状态是否合法额外约束未提交未提交合法无未提交未通过合法总提交次数 1未提交已通过合法AC 时间 封榜时刻未通过未提交非法冻结板已有提交终榜不可能消失未通过未通过合法终榜总提交次数 冻结板错误次数未通过已通过合法AC 时间 封榜时刻总提交次数 错误次数 1已通过未提交非法已 AC 不可能消失已通过未通过非法已 AC 不可能变成未通过已通过已通过合法AC 时间必须相同终榜总提交次数 冻结板总提交次数检验完每道题的状态后再按终榜信息重新计算每个队伍的 AC 数和总罚时排序后与题目给定的排名顺序比较。逻辑不复杂但分类讨论一定要细心少写一种情况就会 WA。5.2 换成“求最少揭示次数”怎么办如果题目进一步要求输出“至少需要揭示多少次才能达到某个终榜”那就不能只看两个榜单是否相容了。此时要贪心或搜索优先处理能让排名产生关键变化的揭示或者枚举哪些题在封榜后 AC。这种变体已经是“模拟 枚举”的结合复杂度取决于题目数据范围但核心仍然建立在本文这套状态变化模型上。我个人做这种题的习惯是先把基础模拟写好再在基础版本上做增量修改。因为滚榜的规则是固定的无论题目怎么变罚时公式、题状态迁移、排名比较这三块都不会变。基础代码就是我的“对拍器”改一版用旧版对拍新版能快速发现哪里改漏了。最后分享一个调试技巧不管题目给不给我都习惯在程序里加一个debugPrint()函数把每次事件后所有队伍的 AC 数和罚时打出来。模拟题的失败往往不是算法错了而是中间状态累积错了。看到第一处中间状态和手推不一致的位置问题通常就在那之前几步。这类题多练几道之后逻辑会稳定很多后续遇到“滚榜”“封榜”背景的题也能一眼看穿。
