企业官网建设流程全解析

做区域赛补题的时候，我最怕看到带 "Scoreboard" 字眼的模拟题。P9670 Frozen Scoreboard 就是典型代表：题目背景看着花哨，实际上考的是对比赛提交记录的状态还原。它来自 ICPC 2022 济南站，洛谷难度标的是普及+，但很多选手一上手就发懵，不是算法难，而是不知道该按什么顺序处理那些约束。

这道题的核心就一句话：比赛中有一段“榜单冻结”时间，冻结前你有一份榜单快照，比赛结束后又有一份最终榜单，题目让你判断这两份快照能不能对应上一个真实的提交序列，并且把任意一种可能的提交序列构造出来。整个过程没有高级数据结构，没有图论，纯粹是“状态模拟 + 约束检查”。但正因为纯粹，它把模拟题最容易踩的坑全部踩了一遍：罚时口径、时间窗口、AC 后不能再提交、输出排序。

下面我按自己的做题思路，把这道题的完整解法拆开讲一遍。适合准备区域赛的选手，也适合刷普及+题单时被模拟题折磨的人。

1. 从“榜单冻结”到“提交记录还原”，题面到底在说什么

1.1 为什么最后一段时间要冻结榜单

ICPC 正式比赛有个规则：比赛结束前的一段时间（通常是最后一小时），实时榜单会被“冻结”。冻结之后，各个队伍仍然可以正常提交代码，评测机也照常评测，但观众和参赛队伍看不到这些新提交的结果。榜单上只显示这些题目“有新的提交”，状态变成待定（pending）。直到比赛结束，最终榜单才解冻，把最后一小时的提交结果补进去。

这个规则的设计初衷是防止强队看着实时榜单去挑软柿子捏，希望各队在最后阶段凭自己判断选题。但落到算法题里，它就变成了一个非常有趣的逆向问题：给你一份冻结时的旧榜单和一份解冻后的最终榜单，你能不能还原出冻结区间里到底发生了什么？

P9670 就是把这个问题包装成了一个“模拟 + 构造”题。题目给的是单个队伍（或多个队伍）在两个时间点的状态，要求判断是否存在合法的冻结后提交序列，并输出一种方案。

1.2 两份榜单对照关系

我先把榜单抽象成每个队伍、每个题目的四要素：

• 错误提交次数：这个题提交了多少次，但没有通过。
• 是否 AC：最终有没有通过。
• AC 时间：如果 AC，是在第几分钟通过的。
• 罚时：队伍总罚时等于所有 AC 题的罚时之和。

对同一个队伍，我们能拿到两份数据。

第一份是冰冻时刻（记为 freeze）时的状态。它记录了：

• 每个题目在冻结前错误提交了几次。
• 每个题目在冻结前是否已经 AC。
• 如果已经 AC，AC 时间是多少。

第二份是比赛结束（记为 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 乘以最终错误提交次数。这个口径很关键，后面会专门说。

从数据结构能看出，我们需要做的其实是三件事：

1. 逐题检查冻结前状态到最终状态是否逻辑自洽。
2. 根据总罚时反推出所有“冻结后 AC 题”的 AC 时间的总和。
3. 在合法时间窗口里找出一组互不相同的 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 一张状态转换表

把两道题的合法转换整理成表，写代码的时候可以对着查：

有了这张表，第一阶段的检查就能保证不重不漏。

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 次 WA
• 1 次 AC

所有需要安排的 WA 次数加起来，记为 totalWA。需要安排 AC 的题目数量记为 k。

3.3 罚时守恒方程

设：

• frozenTimeSum 表示冻结前已经 AC 的题的 AC 时间总和。
• errPenaltySum 表示所有最终 AC 题的错误提交罚时总和，也就是 20 × 每个最终 AC 题的 finErr 之和。

那么最终总罚时 penalty 一定满足：

penalty = frozenTimeSum + 冻结后AC题的AC时间总和 + errPenaltySum

所以：

needSum = penalty - frozenTimeSum - errPenaltySum

needSum 就是所有冻结后 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. 完整 C++17 实现：检查、反推、生成提交序列

前面思路捋顺了，代码就很短。下面是一个完整可运行的 C++17 实现。我按“每队给出冻结前状态和最终状态，最终 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, vector<int>& 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; vector<int> 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, vector<Problem>& p, vector<Op>& ops) { long long frozenTimeSum = 0; long long errPenaltySum = 0; vector<int> needAC; vector<int> 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; vector<int> 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; vector<Problem> 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; } vector<Op> 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 再加一个贪心构造。如果你在赛场上遇到它，别慌，老老实实把状态表列出来，一组一组套就行。