P9670 Frozen Scoreboard 题解：榜单冻结与提交序列还原的模拟思路

做区域赛补题的时候我最怕看到带 Scoreboard 字眼的模拟题。P9670 Frozen Scoreboard 就是典型代表题目背景看着花哨实际上考的是对比赛提交记录的状态还原。它来自 ICPC 2022 济南站洛谷难度标的是普及但很多选手一上手就发懵不是算法难而是不知道该按什么顺序处理那些约束。这道题的核心就一句话比赛中有一段“榜单冻结”时间冻结前你有一份榜单快照比赛结束后又有一份最终榜单题目让你判断这两份快照能不能对应上一个真实的提交序列并且把任意一种可能的提交序列构造出来。整个过程没有高级数据结构没有图论纯粹是“状态模拟 约束检查”。但正因为纯粹它把模拟题最容易踩的坑全部踩了一遍罚时口径、时间窗口、AC 后不能再提交、输出排序。下面我按自己的做题思路把这道题的完整解法拆开讲一遍。适合准备区域赛的选手也适合刷普及题单时被模拟题折磨的人。1. 从“榜单冻结”到“提交记录还原”题面到底在说什么1.1 为什么最后一段时间要冻结榜单ICPC 正式比赛有个规则比赛结束前的一段时间通常是最后一小时实时榜单会被“冻结”。冻结之后各个队伍仍然可以正常提交代码评测机也照常评测但观众和参赛队伍看不到这些新提交的结果。榜单上只显示这些题目“有新的提交”状态变成待定pending。直到比赛结束最终榜单才解冻把最后一小时的提交结果补进去。这个规则的设计初衷是防止强队看着实时榜单去挑软柿子捏希望各队在最后阶段凭自己判断选题。但落到算法题里它就变成了一个非常有趣的逆向问题给你一份冻结时的旧榜单和一份解冻后的最终榜单你能不能还原出冻结区间里到底发生了什么P9670 就是把这个问题包装成了一个“模拟 构造”题。题目给的是单个队伍或多个队伍在两个时间点的状态要求判断是否存在合法的冻结后提交序列并输出一种方案。1.2 两份榜单对照关系我先把榜单抽象成每个队伍、每个题目的四要素错误提交次数这个题提交了多少次但没有通过。是否 AC最终有没有通过。AC 时间如果 AC是在第几分钟通过的。罚时队伍总罚时等于所有 AC 题的罚时之和。对同一个队伍我们能拿到两份数据。第一份是冰冻时刻记为 freeze时的状态。它记录了每个题目在冻结前错误提交了几次。每个题目在冻结前是否已经 AC。如果已经 ACAC 时间是多少。第二份是比赛结束记为 end时的最终状态。它记录了每个题目最终错误提交几次。每个题目最终是否 AC。队伍最终过了多少题。队伍最终总罚时。注意最终状态里的“是否 AC”和“错误提交次数”是完整信息但题目不一定直接给出每个 AC 题的具体 AC 时间而是把它藏在总罚时里需要你反推。这也是这道题最需要小心的部分之一。1.3 我们用来做题的数据结构写代码之前先把状态定义清楚。对每个题目我用下面这个结构体存两份状态struct Problem { int preErr; // 冻结前错误提交次数 bool preAC; // 冻结前是否 AC int preTime; // 冻结前 AC 时间如果没 AC 则无意义 int finErr; // 最终错误提交次数 bool finAC; // 最终是否 AC int finTime; // 最终 AC 时间-1 表示需要程序构造 };这里我把“错误提交次数”和“AC 提交”分开统计。一个题如果最终 AC那么它的总罚时贡献是 AC 时间加上 20 乘以最终错误提交次数。这个口径很关键后面会专门说。从数据结构能看出我们需要做的其实是三件事逐题检查冻结前状态到最终状态是否逻辑自洽。根据总罚时反推出所有“冻结后 AC 题”的 AC 时间的总和。在合法时间窗口里找出一组互不相同的 AC 时间并且为每个题目分配对应的 WA 提交。明确了目标整个题就不再神秘了。2. 四个硬门槛不扫清写多少代码都是白搭这类模拟题有个特点算法本身不难但边界条件一旦漏判就会被各种 WA 打得怀疑人生。我先把最关键的四个硬性约束列出来。2.1 AC 之后不能再提交这是最容易忽略的一条。在真实比赛中一个题目通过后队伍基本不会再交这个题。榜单快照里如果冻结前某个题已经 AC那么最终状态里它必须仍然是 AC而且最终错误提交次数必须等于冻结前错误提交次数。如果一个题冻结前已经 AC最终状态却显示没 AC那直接是无解。同样地如果冻结前已经 AC最终错误提交次数却变多了也说明冻结后又交了这在赛制下不合法直接无解。if (p[i].preAC) { if (!p[i].finAC) return false; if (p[i].finErr ! p[i].preErr) return false; }2.2 错误提交次数只能增不能减冻结后队伍能干的事情有两种提交一道新题或者继续交一道没过的旧题。不管是哪种一个题的错误提交次数都只能变多不能变少。所以对于任意一道题都必须满足if (p[i].finErr p[i].preErr) return false;这个判断虽然简单但建议放在最前面统一处理。因为后面计算“冻结后还需要交多少次 WA”依赖这个差值。2.3 罚时公式必须用对ICPC 的罚时规则是一个题的罚时 AC 时间 20 × 该题 AC 前错误提交次数。要注意未 AC 的题不产生任何罚时哪怕你交了 100 发错误提交。如果某个题冻结前已经 AC那么它的 AC 时间就是冻结前的 AC 时间错误提交次数也是固定值它贡献的罚时是确定的。如果某个题冻结前没 AC但最终 AC 了说明它一定是在冻结后才通过的。这个题贡献的罚时是未知 AC 时间加上 20 × 最终错误提交次数。把所有 AC 题的罚时加起来应该等于题目给的最终总罚时。我们把已知部分全部挪到等式一边未知部分就是“冻结后所有 AC 题的 AC 时间之和”。这是后面构造的核心依据。2.4 一张状态转换表把两道题的合法转换整理成表写代码的时候可以对着查冻结前状态最终状态是否合法额外要求未 AC未 AC合法最终错误数 ≥ 冻结前错误数未 AC已 AC合法最终错误数 ≥ 冻结前错误数且必须存在一次冻结后 AC已 AC未 AC非法不可能倒退已 AC已 AC合法最终错误数 冻结前错误数AC 时间不变有了这张表第一阶段的检查就能保证不重不漏。3. 不枚举时间戳把问题转成 AC 时间和的构造3.1 为什么不要一上来就 DFS很多人看到“输出一种提交序列”第一反应是 DFS 枚举每分钟交了什么题。理论上确实可以从 freeze 1 到 end每个时间点要么不交要么交某道题再判断最终罚时是否匹配。但这样做有两个问题时间窗口最多可能有几百分钟每分钟都有几十种选择直接搜会非常暴力。你需要在搜索过程中维护“每道题内部 WA 必须排在 AC 之前”的顺序这个顺序约束会让剪枝很难写。其实这道题根本不需要枚举时间。罚时里除了 AC 时间只跟错误提交次数有关不关心错误提交具体发生在哪一分钟。也就是说WA 提交在时间轴上的位置对最终状态完全没影响。于是有一个非常关键的想法把所有 WA 一次性放在最前面再把所有 AC 放在后面。这样每道题的 WA 都天然排在它自己的 AC 之前完全满足题目要求。剩下的问题只剩一个给每一道“冻结后 AC”的题挑一个合适的 AC 时间使它们加起来等于罚时方程里算出来的那个总和。3.2 需要安排哪些操作先统计每个题的“冻结后还需提交次数”。对于最终未 AC 的题如果冻结后还需要交 WA那这些 WA 都要安排进时间线。对于冻结前未 AC、最终 AC 的题设它最终错误提交次数为 finErr冻结前错误提交次数为 preErr那么冻结后需要安排finErr - preErr 次 WA1 次 AC所有需要安排的 WA 次数加起来记为 totalWA。需要安排 AC 的题目数量记为 k。3.3 罚时守恒方程设frozenTimeSum 表示冻结前已经 AC 的题的 AC 时间总和。errPenaltySum 表示所有最终 AC 题的错误提交罚时总和也就是 20 × 每个最终 AC 题的 finErr 之和。那么最终总罚时 penalty 一定满足penalty frozenTimeSum 冻结后AC题的AC时间总和 errPenaltySum所以needSum penalty - frozenTimeSum - errPenaltySumneedSum 就是所有冻结后 AC 题的 AC 时间加在一起必须达到的值。有了这个值问题就变成了典型的“选 k 个互不相同的整数让它们的和等于 needSum”。3.4 AC 时间的可行区间因为所有 WA 都被我们故意排在了最前面如果 totalWA 次 WA 占据最早的 totalWA 个时间点那么第一个可用的 AC 时间是low freeze totalWA 1最后一个可用时间点是比赛结束时间 end。所以所有 AC 时间必须从区间 [low, end] 里选。注意一个时间点只能有一个提交所以还要满足 k ≤ end - low 1。在这个区间里选 k 个互不相同的整数能组成的和是连续的整数段。最小和是选最小的 k 个minSum k * low k * (k - 1) / 2最大和是选最大的 k 个maxSum k * end - k * (k - 1) / 2如果 needSum 不在 [minSum, maxSum] 范围内直接无解。这个区间判断可以过滤掉绝大多数非法情况。3.5 贪心构造 AC 时间在范围内时怎么把 needSum 具体分配成 k 个时间点我用一个从后往前的贪心构造。先把 k 个时间点初值设为区间中最小的 k 个low, low 1, ..., low k - 1它们的和是 minSum。现在需要额外增加 delta needSum - minSum。我们从最后一个时间点开始尽量让它变大但有一个限制它不能超过某个上界否则后面的时间点可能没有位置。对于第 i 个时间点0-indexed它的上界是high - (k - 1 - i)这个上界保证它后面还有足够的空间容纳剩余时间点。每个时间点能增加的量是上界减去当前值。然后把这个时间点往上抬最多消耗掉剩余 delta。这样一轮下来k 个时间点仍然严格递增总和恰好是 needSum而且全部落在 [low, end] 内。4. 完整 C17 实现检查、反推、生成提交序列前面思路捋顺了代码就很短。下面是一个完整可运行的 C17 实现。我按“每队给出冻结前状态和最终状态最终 AC 时间用 -1 表示未知”的输入格式来写实际提交时只需要按题目格式微调输入解析部分。#include bits/stdc.h using namespace std; struct Problem { int preErr; bool preAC; int preTime; int finErr; bool finAC; int finTime; }; struct Op { int t, id; string result; }; bool constructACtimes(int k, int low, int high, long long needSum, vectorint out) { if (k 0) return needSum 0; if (low high) return false; if (k high - low 1) return false; long long minSum 1LL * k * low 1LL * k * (k - 1) / 2; long long maxSum 1LL * k * high - 1LL * k * (k - 1) / 2; if (needSum minSum || needSum maxSum) return false; long long delta needSum - minSum; vectorint a(k); for (int i 0; i k; i) a[i] low i; for (int i k - 1; i 0; i--) { long long curMin low i; long long curMax high - (k - 1 - i); long long canAdd curMax - curMin; long long add min(delta, canAdd); a[i] (int)(curMin add); delta - add; } if (delta ! 0) return false; out a; return true; } bool solveTeam(int m, int freeze, int endTime, int K, long long penalty, vectorProblem p, vectorOp ops) { long long frozenTimeSum 0; long long errPenaltySum 0; vectorint needAC; vectorint needWA(m, 0); long long totalWA 0; for (int i 0; i m; i) { if (p[i].preErr p[i].finErr) return false; if (p[i].preAC) { if (!p[i].finAC) return false; if (p[i].finErr ! p[i].preErr) return false; if (p[i].finTime ! -1 p[i].finTime ! p[i].preTime) return false; frozenTimeSum p[i].preTime; } else { if (p[i].finAC) { needAC.push_back(i); needWA[i] p[i].finErr - p[i].preErr; totalWA needWA[i]; } else { needWA[i] p[i].finErr - p[i].preErr; totalWA needWA[i]; } } if (p[i].finAC) { errPenaltySum 20LL * p[i].finErr; } } int acCnt 0; for (int i 0; i m; i) acCnt p[i].finAC ? 1 : 0; if (acCnt ! K) return false; long long needSum penalty - frozenTimeSum - errPenaltySum; long long windowLen endTime - freeze; int k (int)needAC.size(); if (totalWA k windowLen) return false; int low freeze (int)totalWA 1; int high endTime; vectorint acTimes; if (!constructACtimes(k, low, high, needSum, acTimes)) return false; int curT freeze 1; for (int i 0; i m; i) { for (int j 0; j needWA[i]; j) { ops.push_back({curT, i, WA}); curT; } } for (int idx 0; idx k; idx) { ops.push_back({acTimes[idx], needAC[idx], AC}); } sort(ops.begin(), ops.end(), [](const Op a, const Op b) { return a.t b.t; }); return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, freeze, endTime; cin n m freeze endTime; for (int team 0; team n; team) { int K; long long penalty; cin K penalty; vectorProblem p(m); for (int i 0; i m; i) { int ac, t, err; cin ac t err; p[i].preAC (ac 1); p[i].preTime t; p[i].preErr err; } for (int i 0; i m; i) { int ac, t, err; cin ac t err; p[i].finAC (ac 1); p[i].finTime t; p[i].finErr err; } vectorOp ops; bool ok solveTeam(m, freeze, endTime, K, penalty, p, ops); if (!ok) { cout No\n; continue; } cout Yes\n; cout ops.size() \n; for (auto op : ops) { cout op.t op.id 1 op.result \n; } } return 0; }这套实现的正确性建立在“最终 AC 时间由程序反推”的约定上。如果原题已经明确给出了每个题目的最终 AC 时间那么需要在代码里额外加一步把所有冻结后 AC 题的 finTime 之和与 needSum 比较不相等就无解。这是很小的改动不影响整体框架。5. 写这题我翻过的车以及对应的避坑经验5.1 罚时口径不统一公式越推越乱我最开始写的时候把finErr理解成“总提交次数”也就是把 AC 那一次也算进去结果罚时公式一直跟样例对不上。后来才把口径统一成“错误提交次数”AC 单独用finAC表示。这里给出一个自查技巧一个题如果最终 AC 了那么AC 时间贡献 AC 时间本身。错误提交次数贡献20 × finErr分钟罚时。AC 那一次提交本身不产生罚时。如果题目给的是“总提交次数”那么罚时要写成AC时间 20 × (总提交次数 - 1)。两种口径最后的代码会差很多做题前必须确认清楚。5.2 总罚时和 AC 时间总和要开 long long单看一个题的罚时数量级也就是几百。可一旦 AC 题变多20 × finErr累加起来再叠加上 AC 时间总和很容易超出 int 范围。我在第一次提交时就是没注意这个WA 了好几发才用对拍定位到是溢出。建议统计区间和、罚时、needSum 的地方全部用 long long不要舍不得。5.3 无解判断要把所有分支都列全这类模拟题的无解分支非常多漏一个就会输出错误的 Yes。我总结下来至少需要检查这几类冻结前 AC 的题最终是否仍 AC。冻结前 AC 的题最终错误次数是否没变。所有题的最终错误次数是否都不小于冻结前错误次数。最终 AC 题数是否等于题目给的 K。冻结后 AC 题的 AC 时间总和是否落在可行区间内。总操作数是否小于等于可用时间点数。这六条检查全部通过才可以说有解。5.4 输出提交序列前一定要按时间排序在构造时我先连续排了所有 WA再排所有 AC这只是一个“思考中的方案”。真正输出时必须把操作按时间排序否则构造出的时间点和操作顺序不一致会被判成格式错误或逻辑错误。我用一个Op结构体存所有输出最后统一 sort这样最省心。6. 从这道模拟题延伸出去状态还原类题目的通用套路做完整道题最大的收获不是会了一个“P9670”而是理解了一类“状态还原”问题。这类题的共同点是你有两份状态一份是中间态一份是终态中间有一段时间的行为被隐藏了需要你通过约束反推隐藏行为。常见的约束类型有数值单调性错误提交次数不减。状态不可逆AC 状态不能变回未 AC。总量守恒罚时总和固定。时间窗口限制所有操作必须落在某个区间内。只要把约束逐条列出来再判断是“验证”类还是“构造”类。验证类直接检查所有条件是否成立构造类可以先通过守恒关系算出必须满足的数值再贪心构造一组方案不需要无脑搜索。P9670 这道题还有不少变体。比如多队同时出现时由于不同队伍之间提交时间可以重叠队伍之间不会互相挤占时间点因此只要按队伍分别处理即可。还有些题会把冻结时刻作为输入的一部分那就在读入时直接把 freeze 变量替换掉。但核心的“罚时守恒 时间窗口区间判断”思路完全通用。最后说句实在话模拟题拼的不是灵感而是谁的状态划分更清楚。Frozen Scoreboard 这名字唬人拆开以后也不过是几个 if 再加一个贪心构造。如果你在赛场上遇到它别慌老老实实把状态表列出来一组一组套就行。