1. 赛题整体复盘与难度定位

AtCoder Beginner Contest 173 这场比赛的题目梯度设置得相当典型，A 到 D 四道题分别对应了入门模拟、基础数学、状态压缩枚举、以及带排序的贪心构造四个层次。如果你正在刷 AtCoder 的 ABC 场次来打基础，这场非常适合拿来当阶段性检验——它不涉及复杂数据结构，也不需要高深的算法知识，但对边界条件处理和枚举思路的完整性有比较明确的要求。

我个人的体感是：A、B 两题属于“读完题就能写”的送分题，C 题是整场的分水岭，D 题则是那种“想到了就很简单，想不到就卡死”的典型构造题。很多刚接触竞赛的朋友在 C 题上翻车，不是因为不会写代码，而是因为没有把二维网格的枚举方式想清楚；D 题翻车则多半是因为排序方向搞反或者没意识到前缀和可以优化。

这篇文章我会把四道题逐一拆开，不光给代码，更重要的是讲清楚每一步为什么这么设计、有哪些容易踩的坑、以及如果比赛时卡住了该怎么换思路。代码统一用 C++17 编写，这也是 AtCoder 上最主流的提交语言，STL 用起来顺手，跑得也快。

提示：AtCoder 的 Beginner Contest 每场 100 分钟，A~D 四题的总分通常是 100 + 200 + 300 + 400。如果你的目标是稳定上分，A~C 必须做到 20 分钟内全清，D 题留足 40 分钟以上来推思路和调试。

2. A 题：基础模拟与取模运算

2.1 题目核心需求解析

A 题的场景很直白：给定一个整数 N，判断它除以 1000 之后的余数情况，输出对应的结果。具体来说，如果 N 是 1000 的倍数，输出 0；否则输出“凑到下一个 1000 的倍数还差多少”。这本质上就是一个向上取整到最近的 1000 的倍数的问题。

这类题在 ABC 的 A 位置反复出现，考察的就是你对取模运算%的理解。很多人第一反应是写一堆 if-else，但其实一行取模就能搞定。关键在于想清楚：N % 1000得到的是 N 除以 1000 的余数，如果余数是 0，说明已经整除，答案是 0；否则答案就是1000 - (N % 1000)。

2.2 取模思路的推导与实现

为什么是1000 - (N % 1000)而不是别的？你可以这样理解：假设 N = 1234，那么1234 % 1000 = 234，说明它比 1000 多出了 234，要凑到 2000 还差1000 - 234 = 766。再验证 N = 2000，2000 % 1000 = 0，此时按公式算是1000 - 0 = 1000，但正确答案应该是 0，所以必须特判余数为 0 的情况。

#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int rem = N % 1000; if (rem == 0) cout << 0 << endl; else cout << 1000 - rem << endl; return 0; }

这段代码的时间复杂度是 O(1)，空间也是 O(1)，没有任何优化空间，也不需要优化。A 题的目标就是快速、准确地拿下，不要在这里浪费超过 3 分钟。

注意：取模运算在 C++ 中对正数行为是明确的，但如果题目出现负数，%的结果符号会跟随被除数，这时候需要额外处理。本题 N 是正整数，所以不用操心这个问题，但养成“看到取模先想符号”的习惯没坏处。

2.3 实操心得与常见失误

我在带新人刷题时发现，A 题最常见的失误不是逻辑错，而是输出格式。比如有人会多输出一个换行、或者把整数输出成了浮点数。AtCoder 的判题是严格字符串比对（忽略行末空格），所以cout << ans << endl;是最稳妥的写法。

另一个小坑是变量类型。N 的范围在 ABC 的 A 题里通常不会超过 int，但如果你不确定，直接用long long也不会有任何性能问题。我个人的习惯是：只要不是明确的小范围计数，一律用 long long，省得后面因为溢出返工。

3. B 题：条件判断与分类讨论

3.1 题目逻辑拆解

B 题给出一组裁判的评分，每个评分对应一个字符串标签，要求你统计各标签出现的次数，最后按固定顺序输出。这道题的核心是用 map 或数组做计数，然后按题目指定的顺序遍历输出。

题目里出现的标签是固定的几种（比如 AC、WA、TLE、RE 之类），所以最省事的做法是用map<string, int>或者直接用四个变量分别计数。用 map 的好处是代码短、通用性强；用四个变量的好处是输出顺序天然确定，不用额外维护顺序数组。

3.2 两种实现方式的取舍

我一般会看标签数量：如果标签只有 3~5 种，直接用变量或数组更直观；如果标签种类多且不确定，用 map 更合适。本题标签是固定的四种，所以我倾向于用 map 配合一个顺序数组来输出，这样代码既短又不容易出错。

#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; map<string, int> cnt; for (int i = 0; i < N; i++) { string s; cin >> s; cnt[s]++; } vector<string> order = {"AC", "WA", "TLE", "RE"}; for (auto& k : order) { cout << k << " x " << cnt[k] << endl; } return 0; }

这里有个细节：cnt[k]在 k 不存在时会自动插入一个 0，所以即使某个标签一次都没出现，输出也是正确的0。这是 map 的一个便利特性，但也要注意它会在你不经意间改变 map 的大小，如果后续要遍历 map 本身，可能会多出一些“假”条目。

3.3 输出格式的坑与规避

B 题的输出格式是标签 x 数量，中间有空格，x 是小写字母。我见过有人写成标签 * 数量或者标签 X 数量，直接 WA 到怀疑人生。竞赛里这种“格式分”看似低级，但每年都有大量选手栽在上面。

提示：提交前一定要把样例复制到本地跑一遍，肉眼比对输出。AtCoder 的样例通常会给 2~3 组，覆盖边界情况，跑通了再提交，能省下大量罚时。

另外，如果题目要求按出现顺序输出而不是固定顺序，那就不能用 map 直接遍历（map 是按 key 排序的），需要额外记录首次出现的顺序。本题是固定顺序，所以简单很多。

4. C 题：二维网格枚举与状态压缩

4.1 问题建模与暴力思路

C 题是整场的重头戏。题目给一个 H 行 W 列的网格，每个格子是黑色或白色，要求你统计有多少种“选择若干行和若干列并全部涂黑”的方式，使得最终网格中黑色格子的总数恰好等于 K。

直接想这个问题会有点绕：你选择的行和列会被全部涂黑，但原本就是黑色的格子不会重复计数。所以最终黑色数量 = 被选中的行覆盖的格子数 + 被选中的列覆盖的格子数 - 行列交叉处被重复计算的格子数。更准确地说，如果选中了 r 行和 c 列，那么这些行列覆盖的所有格子都会变黑，其中原本就是黑的不影响，原本是白的会被涂黑。最终黑色总数就是被选中的行或列覆盖的区域内，原本是黑色的格子数 + 原本是白色但被覆盖的格子数，其实就等于被覆盖的格子总数中，原本黑色的保留，原本白色的变黑，所以最终黑色数 = 被覆盖的格子总数。

等等，这里要仔细想：被选中的行和列覆盖的格子，不管原来是黑是白，最终都会变成黑色。所以最终黑色总数 = 被选中的行集合与列集合的并集所覆盖的格子数量。但题目要求的是最终黑色数等于 K，而原本就黑的格子即使不被选中也仍然是黑的。所以正确的等式是：

最终黑色数 = 原本黑色数 + 被选中行列覆盖的白色格子数

这个转化很关键。如果你直接去模拟涂色再数黑色，复杂度会很高；但转化成“原本黑色数 + 新增黑色数”之后，问题就清晰了。

4.2 枚举行列组合的实现细节

H 和 W 的范围在 ABC 的 C 题里通常不超过 6，这意味着我们可以用二进制枚举所有行组合（2^H 种）和所有列组合（2^W 种），总组合数是 2^(H+W)，最大也就是 2^12 = 4096，完全在可接受范围内。

对于每一种行列组合，我们遍历整个网格，统计最终黑色格子数。如果等于 K，答案加一。总复杂度是 O(2^(H+W) * H * W)，最大约 4096 * 36 ≈ 15 万次操作，瞬间完成。

#include <bits/stdc++.h> using namespace std; int main() { int H, W, K; cin >> H >> W >> K; vector<string> grid(H); for (int i = 0; i < H; i++) cin >> grid[i]; int ans = 0; for (int rowMask = 0; rowMask < (1 << H); rowMask++) { for (int colMask = 0; colMask < (1 << W); colMask++) { int black = 0; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { bool rowSel = (rowMask >> i) & 1; bool colSel = (colMask >> j) & 1; if (rowSel || colSel || grid[i][j] == '#') black++; } } if (black == K) ans++; } } cout << ans << endl; return 0; }

这段代码的逻辑是：对于每个格子，如果它所在的行被选中、或所在的列被选中、或它原本就是黑色，那么它最终就是黑色。三个条件用||连接，非常直观。

4.3 复杂度分析与优化空间

有人可能会问：能不能不遍历整个网格，而是用前缀和预处理来加速？理论上可以，但对于 H, W ≤ 6 的范围，完全没必要。竞赛里有一个重要原则：在时限内能跑过的暴力就是好算法。不要为了炫技而引入不必要的复杂度，那样只会增加出错概率。

不过，如果你想把这道题当成练习状态压缩的素材，可以尝试用位运算预处理每一行的黑色分布，然后用__builtin_popcount来加速统计。但这属于“做完之后回头优化”的范畴，比赛时优先保证正确性。

注意：二进制枚举时，1 << H在 H 较大时会溢出 int。本题 H ≤ 6 没问题，但养成用1LL << H的习惯，以后遇到 H ≤ 20 的题就不会翻车。

5. D 题：排序贪心与前缀和构造

5.1 题意转化与贪心策略推导

D 题描述的是一个构造过程：有一组数，你需要按某种顺序排列它们，使得按规则累加后的总和最大。具体规则是，第一个数不计入总和，从第二个数开始，每个数计入总和的是它前面所有数中的最小值（或者类似的前缀最小值关系）。

这类题的突破口在于观察贡献方式。每个数对总和的贡献取决于它前面出现过的最小数，所以为了让总和最大，我们希望大的数尽量放在“前面已经出现过较大最小值”的位置。换句话说，我们应该把最大的数放在最前面，让它成为后续所有数的“最小值贡献源”。

但第一个数不计入总和，所以第一个数应该放什么？直觉上应该放最大的数，因为它不计入总和，放最大的“浪费”最小。然后第二个数放次大的，它会计入总和，且它的贡献是第一个数（最大值），所以贡献很大。第三个数放第三大的，它的贡献是前两个数的最小值，也就是次大的那个数。以此类推。

这个贪心策略的正确性可以用交换论证来证明：如果存在一对相邻的数顺序反了，交换它们不会让结果变差。具体证明略过，但结论是降序排列后按顺序处理是最优的。

5.2 前缀和优化与实现

如果直接模拟，对于每个位置 i，需要找它前面所有数的最小值，复杂度是 O(N^2)。但 N 可能达到 2×10^5，O(N^2) 会超时。观察发现，降序排列后，前面的数总是比后面的大，所以“前面所有数的最小值”其实就是前一个数（因为降序，越往后越小，前一个数就是前面所有数中最小的）。

等等，这里要仔细：降序排列后，序列是 a1 ≥ a2 ≥ a3 ≥ ... ≥ aN。对于位置 i（i ≥ 2），它前面所有数是 a1 到 a(i-1)，其中最小值是 a(i-1)（因为降序，最后一个最小）。所以第 i 个数的贡献就是 a(i-1)。那么总和就是 a1 + a2 + ... + a(N-1)？不对，第一个数不计入，第二个数贡献 a1，第三个数贡献 a2，...，第 N 个数贡献 a(N-1)。所以总和 = a1 + a2 + ... + a(N-1)。

但这样第二个数本身的值 a2 没有被计入？让我重新读题。题目的规则通常是：第一个数直接放入集合，不计入总和；之后每个数 x 放入时，总和增加当前集合中的最小值，然后把 x 加入集合。如果是这个规则，那么降序排列后，集合中的最小值始终是最后加入的那个数（因为降序，越加越小）。所以第二个数加入时，集合中只有第一个数，最小值是 a1，总和增加 a1；第三个数加入时，集合中有 a1 和 a2，最小值是 a2，总和增加 a2；...；第 N 个数加入时，总和增加 a(N-1)。

所以总和 = a1 + a2 + ... + a(N-1)。这意味着我们只需要把最大的 N-1 个数加起来？但 a1 到 a(N-1) 正好是降序排列后的前 N-1 个数，也就是最大的 N-1 个数。所以答案就是把所有数降序排列，取前 N-1 个求和。

这个结论非常简洁，但前提是规则确实如我所述。如果规则是“每个数计入总和的是它前面所有数的最小值”，那结论是一样的。总之核心就是降序排列后取前 N-1 个求和。

#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<long long> a(N); for (int i = 0; i < N; i++) cin >> a[i]; sort(a.begin(), a.end(), greater<long long>()); long long sum = 0; for (int i = 0; i < N - 1; i++) sum += a[i]; cout << sum << endl; return 0; }

5.3 边界情况与易错点

这道题有几个容易翻车的点。第一，N = 1 的情况：此时只有一个数，第一个数不计入总和，所以答案是 0。上面的代码中循环i < N - 1在 N=1 时不会执行，sum 保持 0，正确。

第二，数值范围：a[i] 可能很大，N 也可能很大，总和可能超过 int 范围，所以必须用long long。我见过有人用 int 存总和，结果在大型测试点上溢出，WA 得莫名其妙。

第三，排序方向：必须用greater<long long>()做降序，如果写成默认的升序，答案会完全错误。这个错误很隐蔽，因为小样例可能碰巧过，但大样例必挂。

提示：D 题这种“排序后取前 N-1 个”的结论，如果比赛时不确定，可以先用小数据暴力验证。比如 N=3，手动枚举所有排列，看看最大值是不是降序排列的前两个数之和。验证一次就能建立信心。

6. 赛后总结与训练建议

6.1 四题知识点串联

把这场四道题放在一起看，它们覆盖了竞赛入门阶段最核心的几种能力：A 题考取模与边界，B 题考计数与格式化输出，C 题考状态压缩枚举，D 题考贪心与排序。这四块能力是后续学习更复杂算法的基础，缺一不可。

我建议刷完这场之后，不要急着开下一场，而是把 C 题和 D 题各再写一遍，不看题解，从零推导。C 题重点练“把涂色问题转化成覆盖问题”的建模能力；D 题重点练“观察贡献方式并证明贪心正确性”的思维习惯。这两项能力一旦建立，后面遇到类似的题会轻松很多。

6.2 常见失分点速查表

这张表里的每一条都是我或身边朋友真实踩过的坑。尤其是 C 题的“原本黑色”条件，很多人第一次写的时候会忘记，导致答案偏小。

6.3 下一步训练方向

如果你这场打下来感觉 A~C 很顺、D 题也能在 30 分钟内搞定，那说明你的基础已经比较扎实了，可以开始挑战 ABC 的 E 题和 F 题，或者去刷 ARC 的 A、B 题。E 题通常涉及更复杂的 DP 或图论，F 题可能是高级数据结构或数学推导，这些才是真正拉开差距的地方。

如果你在 C 题上卡了很久，建议专门找 10 道状态压缩枚举的题集中训练，把1 << n的枚举模板练到肌肉记忆。如果你在 D 题上没思路，建议先补一补贪心算法的经典题型，比如区间调度、背包贪心、排序不等式等，这些是构造类题目的基础。

最后分享一个我个人的训练习惯：每场比赛结束后，把没做出来的题记在一个本子上，只记题目核心思路和关键转化点，不记代码。过一周再回头看，如果能立刻说出解法，说明真的掌握了；如果还是模糊，就再推一遍。这个方法比反复刷题有效得多，因为它在训练你的模式识别能力，而竞赛的本质就是在有限时间内快速匹配已知模式并调整。