USACO 2017年12月青铜组真题全解析：几何、模拟与枚举的实战训练

每年12月USACO新赛季第一场月赛开打青铜组Bronze Division是绝大多数竞赛新手的第一站。我见过不少人把青铜组想得很简单——会排序、会循环、会数组好像就能拿满分——这话对了一半另一半得用真题来回答。2017年12月这场月赛正好是典型案例三道题分别考几何、模拟、枚举表面上一道比一道基础但真正能在比赛里一次AC三道的人远没有大家想象的多。这篇文章就把这三道真题完整拆开讲从读题、算法设计、边界条件到完整AC代码再把我自己踩过的坑和复盘别人代码时反复见到的问题一起列出来。适合刚打完这场月赛的同学做复盘也适合准备参加青铜组的选手当第一套真题来练手。1. 2017年12月青铜组的三道题到底在考什么先给这一场的题目来个全景。我刷这套题的时候最大的感受是每道题都只需要最基础的语法但每道题都藏着一个需要你主动发现的条件。这不是拼算法而是拼你愿不愿意在动手写代码之前多想两分钟。1.1 三道题一览题号官方题目名中文俗称核心考点一句话难点1Blocked Billboard被遮挡的广告牌矩形相交面积计算卡车可能同时遮住两块广告牌要分别扣减2Milk Measurement牛奶产量记录按时间排序 状态维护输入天数无序且墙面照片显示的是最高者的集合3Team Tic Tac Toe团队井字棋八条线枚举 组合去重不同的获胜组合要做无序去重从这张表能看出一个共性三道题其实都在考同一件事——你有没有把题目的限制条件完整读进去。第一题很多人想用逐格标记做因为坐标都不大逐格其实算得动但真正的问题出在部分遮挡的判定不精确搞错一个区间就全错。第二题最大的坑是输入天数乱序官方数据里故意把顺序打乱按读入顺序直接做的人基本都掉进去了。第三题则难在不同组合四个字字母对 AB 和 BA 必须算同一种没做过类似题的人很容易在这里多算。1.2 青铜组真正的分水岭我在各种OJ上见过很多刷了上百道水题的同学他们写循环、写数组、写字符串处理都很熟练但一上USACO真题经常卡在铜牌第一题两个小时。原因不是语法不熟而是长期刷水题养成了样例过了就交的习惯根本不检查边界。青铜组的题目设计很明显在筛选严谨而不是聪明。比如第二题只要你能想到先把记录按天数排序再模拟后面的代码几乎就是流水账。可比赛时很多人的第一反应是数据都给我了我就按输入顺序跑一遍吧然后完美错过答案。这一场的分水岭就是你能不能跳出输入给你的顺序去还原题目里的真实世界。2. Blocked Billboard矩形相交面积与先算整体再扣重叠这道题是2017年12月青铜组的开门题代码量很小但非常能检验你对几何问题抽象建模的基本功。它给我的感觉很像做小学应用题里的阴影面积两个矩形加在一起被第三个矩形挡住了一部分问剩下的可见面积是多少。2.1 题意理解广告牌、卡车和还能看见多少题目给你的信息是两块平行于坐标轴的广告牌分别用左下角坐标和右上角坐标描述一辆卡车同样是个矩形挡在广告牌前面。你要输出两块广告牌仍然可见的总面积。这里有几个隐含前提必须拎清楚两块广告牌之间互不重叠题目明确保证所以可见总面积才能直接等于两块的面积之和减去被遮挡的部分。卡车的遮挡是部分遮挡不是整块覆盖所以你要算的是广告牌矩形和卡车矩形的相交面积。一个矩形可以同时遮到两块广告牌所以必须对每块广告牌分别做一次相交面积计算。我用一组自己平时验证用的数据来演示第一块广告牌左下角 (1,1)、右上角 (4,4)面积是 3×39第二块广告牌左下角 (7,1)、右上角 (10,4)面积也是 9卡车左下角 (3,2)、右上角 (9,3)。卡车和第一块广告牌的公共部分x方向从 3 到 4宽 1y方向从 2 到 3高 1相交面积 1。卡车和第二块广告牌的公共部分x方向从 7 到 9宽 2y方向从 2 到 3高 1相交面积 2。所以答案是 99-1-215。2.2 相交面积公式为什么可以写成一行两个矩形相交的区域其实就是在x轴上两个区间取交集在y轴上两个区间取交集然后用交集的宽度乘以高度。x方向的交集宽度可以写成max(0, min(a.x2, b.x2) - max(a.x1, b.x1))如果你看不懂这个式子换个生活化的比喻两个人共用一张长条桌每个人的地盘是一个区间。他们实际能撞到胳膊的公共区域是从两人地盘右侧中较靠左的那个点起到两人地盘左侧中较靠右的那个点止。也就是取右边界里较小的取左边界里较大的这两者之差就是重叠长度。差为负数说明根本没碰上直接归零。把这个逻辑套到y方向就得到了完整的重叠面积函数struct Rect { int x1, y1, x2, y2; }; int overlapArea(const Rect a, const Rect b) { int w max(0, min(a.x2, b.x2) - max(a.x1, b.x1)); int h max(0, min(a.y2, b.y2) - max(a.y1, b.y1)); return w * h; }我当时第一次写这个函数时手滑把 max 和 min 用反了测出来的答案比样例大了好几倍。后来养成了一个习惯每写一个几何公式先找两组极端数据验证——完全重合和完全不相交两个结果都正确才敢往下走。2.3 完整AC代码与文件输入输出USACO所有题目都是文件输入输出不读标准输入。你需要在代码里写 freopen 把 billboard.in 和 billboard.out 接进来或者用 ifstream / ofstream。新手最容易在这两行上栽跟头忘了建输入文件或者文件名打错。#include bits/stdc.h using namespace std; struct Rect { int x1, y1, x2, y2; }; int area(const Rect r) { return (r.x2 - r.x1) * (r.y2 - r.y1); } int overlapArea(const Rect a, const Rect b) { int w max(0, min(a.x2, b.x2) - max(a.x1, b.x1)); int h max(0, min(a.y2, b.y2) - max(a.y1, b.y1)); return w * h; } int main() { freopen(billboard.in, r, stdin); freopen(billboard.out, w, stdout); Rect b1, b2, truck; cin b1.x1 b1.y1 b1.x2 b1.y2; cin b2.x1 b2.y1 b2.x2 b2.y2; cin truck.x1 truck.y1 truck.x2 truck.y2; int ans area(b1) area(b2) - overlapArea(b1, truck) - overlapArea(b2, truck); cout ans endl; return 0; }这份代码的答案就是 15。整个程序逻辑极其直白先算两块广告牌总面积再分别扣除卡车遮住的部分。2.4 这道题最容易错的两处第一个常见错误是我每次看同学代码都会遇到的overlapArea 里的 max(0, ...) 被漏写。如果不加这个保护当两个矩形没有交集时min 减 max 会得到负数负面积加进答案导致结果错得离谱。第二处是坐标读取顺序输入给的是左下角和右上角但有人想当然认为是任意两个对角又没做排序直接套公式遇到 x1 x2 的输入就翻车。还有一个值得说的点题目保证广告牌互不重叠这是个强假设不要觉得自己聪明去实现一套能处理广告牌也重叠的通用解法。比赛题要的是在给定约束下高效正确而不是过度设计。真有兴趣拓展可以在赛后自己想想如果广告牌重叠该怎么扣减但考场里把题目的每条保证都当作重要条件来用才是青铜组的正确打开方式。3. Milk Measurement按天排序与最高者集合的实时维护第二题是整场我推荐所有新手反复品的一题。它没有难算法但把模拟题最容易踩的坑全部集中在了同一道题里。题意是这样的三头奶牛名字分别是 Bessie、Elsie、Mildred初始产量都是 7 加仑。谷仓墙上挂着一张照片照片上是当前产量最高的所有奶牛注意是所有可以是一头也可以是多头。接下来给你若干条记录每条记录形如天数 名字 变化量你需要在所有记录处理过程中统计照片内容一共变化了多少次。3.1 样例手工推演为什么答案是2样例输入是4 7 Mildred 3 4 Elsie -7 9 Mildred 9 3 Bessie 1如果你不排序直接按读入顺序模拟结果一定会错。正确做法是先把四条记录按天数排序天数名字变化量操作后三头牛产量当前最高者集合是否变化初始--B7, E7, M7{Bessie, Elsie, Mildred}-3Bessie1B8, E7, M7{Bessie}变化答案14Elsie-7B8, E0, M7{Bessie}未变化7Mildred3B8, E0, M10{Mildred}变化答案29Mildred9B8, E0, M19{Mildred}未变化所以答案是 2。注意第 3 天的变化初始照片上是三头牛并列现在变成只有 Bessie 一头牛排第一照片内容变了必须计数。如果只记录当前第一名是谁就会漏掉这种并列集合的变化。3.2 为什么排完序后直接模拟就能通过这题数据范围不大N 不超过 100所以排序后逐条模拟时间复杂度 O(N log N N)完全够用。有些同学一看到变化量就往线段树、树上差分那边想纯属给自己加戏。青铜组的数据范围不需要这些能线性模拟就大胆模拟。但直接模拟并不意味着无脑写。你需要想清楚要维护两个东西三头奶牛的当前产量值以及当前产量最高者的集合。struct Rec { int day; string name; int delta; };排序时按 day 从小到大排。这里有个小技巧把记录定义成结构体排序函数一行搞定比直接拿三个数组对着排要不容易错。3.3 关键设计比较集合而不是比较最大值这道题的正解思路是每次更新完奶量后重新扫描三头牛的产量找出当前最大值然后把所有产量等于这个值的牛都放进一个新的集合拿这个新集合和上一个集合比较不一样就答案加一。这么做的原因是照片显示的是最高者集合。你要判断的是集合是否变化而不是单纯判断最高者是否还是同一头牛。比如旧集合是 {A, B}新集合是 {A}最高者确实还是 A但照片从两头牛变成一头牛了这就算一次变化。用 set 直接比较就能天然处理好这种并列和排序问题不需要自己写一堆 if。mapstring, int milk; milk[Bessie] 7; milk[Elsie] 7; milk[Mildred] 7; setstring curMaxSet {Bessie, Elsie, Mildred};初始化时三个人的产量都是 7所以照片初始集合是三个人都在。这一步很关键我见过有人把初始最高集合写成空集或者只写一个名字样例结果直接偏了 1。3.4 完整AC代码与三个隐蔽细节细节一变化量可能是负数产量降到 0 甚至负数都是合法的所以更新时不能做任何非负剪枝。细节二排序后处理时记录里的名字不是固定的直接用 map 读名字更新。细节三每次重新构造新集合时必须等所有更新完成再做比较。#include bits/stdc.h using namespace std; struct Rec { int day; string name; int delta; }; int main() { freopen(measurement.in, r, stdin); freopen(measurement.out, w, stdout); int n; cin n; vectorRec recs(n); for (int i 0; i n; i) { cin recs[i].day recs[i].name recs[i].delta; } sort(recs.begin(), recs.end(), [](const Rec a, const Rec b) { return a.day b.day; }); mapstring, int milk; milk[Bessie] 7; milk[Elsie] 7; milk[Mildred] 7; setstring curMaxSet {Bessie, Elsie, Mildred}; int ans 0; for (const Rec r : recs) { milk[r.name] r.delta; int best -1; for (auto p : milk) { best max(best, p.second); } setstring newMaxSet; for (auto p : milk) { if (p.second best) newMaxSet.insert(p.first); } if (newMaxSet ! curMaxSet) { ans; curMaxSet newMaxSet; } } cout ans endl; return 0; }如果哪天真遇到数据量巨大的类似题可以把找当前产量最大值这步优化成用有序集合按产量排序每次更新后调整对应奶牛的位置复杂度降为 O(N log N)但核心思想还是比较最高者集合是否变化。青铜组能理解到这一层已经超出要求了。3.5 这种状态模拟题的通用套路这次比赛结束后我把这类题总结成一个模板凡是动态更新 查询全局关系的模拟题只要数据范围不大最稳的写法就是每次更新后全部重算再把新旧状态做比较。不要一开始就去维护一个看似精巧但实际上有一堆边界条件的复杂结构。重算所有东西的代价很低而你把维护逻辑想岔了的代价很高。在竞赛里稳定性永远优先于无意义的炫技。4. Team Tic Tac Toe八条线枚举与无序组合去重第三题是井字棋但主角从棋子变成了奶牛。3×3 的棋盘上9 个位置各自被某头奶牛占据每个位置用一个字母表示。你需要统计两种获胜情况一种是一条线上的三个格子被同一头奶牛占满这算单人获胜另一种是一条线上的三个格子恰好被两头奶牛一起占满这算团队获胜。最后输出两个数字单人获胜的不同奶牛数以及团队获胜的不同奶牛组合数。4.1 题意理解什么算恰好由两头奶牛占满这道题的字符串处理很简单难在理解恰好由两头奶牛这件事。一条线上有三个格子如果三个格子里面只有两种字母那就说明这头线上恰好由两头奶牛占据。注意这里不需要额外判断两头牛是否都出现过一次——三个格子只有两种字母必然有一头出现两次、另一头出现一次所以只要set赋值后 size 等于 2就一定满足条件。但这里还有一个隐藏要求不同的获胜组合只统计一次。比如某条线是 ABB另一条线是 BAA本质都是 A 和 B 的组合只能算一种团队组合。这就是我前面说的无序去重问题。我自己造了一组数据来验证逻辑AAB BCB AAA单人获胜只有最后一行 AAA所以单人的不同奶牛数是 1。团队获胜第一行 AAB 是 AB第二行 BCB 是 BC第一列 ABA 是 AB第二列 ACA 是 AC第三列 BBA 是 AB主对角线 ACA 是 AC副对角线 BCA 三个字母都不同不计。去重后团队组合是 AB、BC、AC一共 3 种。所以输出应该是 1 和 3。4.2 把八条线统一抽象成处理一条线写代码时最怕的是把八条线分八种情况写那样代码又长又容易漏。更聪明的做法是把每一行、每一列、两条对角线都转成一个 string然后统一交给一个函数去处理。#include bits/stdc.h using namespace std; char board[3][3]; setchar solo; setstring team; void processLine(const string line) { setchar s(line.begin(), line.end()); if (s.size() 1) { solo.insert(*s.begin()); } else if (s.size() 2) { auto it s.begin(); char a *it; char b *next(it); if (a b) swap(a, b); string key ; key a; key b; team.insert(key); } } int main() { freopen(tttt.in, r, stdin); freopen(tttt.out, w, stdout); for (int i 0; i 3; i) { for (int j 0; j 3; j) { cin board[i][j]; } } for (int i 0; i 3; i) { string line ; line board[i][0]; line board[i][1]; line board[i][2]; processLine(line); } for (int j 0; j 3; j) { string line ; line board[0][j]; line board[1][j]; line board[2][j]; processLine(line); } string diag1 ; diag1 board[0][0]; diag1 board[1][1]; diag1 board[2][2]; processLine(diag1); string diag2 ; diag2 board[0][2]; diag2 board[1][1]; diag2 board[2][0]; processLine(diag2); cout solo.size() endl; cout team.size() endl; return 0; }注意读取时的细节输入是连续的字母中间没有空格用 cin 读单个 char 是最稳的。如果你用 string 变量按行读三个字符之间没分割符读进来倒也没问题但在后续处理里会多一层转换没必要。4.3 组合去重的两种写法对比我在代码里用的是 set 把两个字母先排序再拼成字符串保证 AB 和 BA 落进同一个 key。这个写法最直观也最不容易写错。另一种常见写法是开一个 bool used[26][26] 数组只在 a b 时把 used[a-A][b-A] 标记为 true最后数一遍有多少个 true。这种写法的好处是省内存、查询快但代码里必须严格保证只标记小写字母在前的情况否则去重逻辑会破功。对比一下方法优点缺点setstring写法简单去重天然正确多建字符串稍有开销bool used[26][26]更接近底层无额外分配需要自己维护排序方向青铜组完全可以用第一种不用犹豫。等你去银组刷了很多题以后再回来看会觉得第二种写法也挺顺手但在现阶段把大量精力花在省一个字符串上不值得。4.4 我复盘时反复看到的三个错误第一个错误是漏掉两条对角线。很多同学能想到行和列但把斜着的两条线忘了白白丢一个测试点。第二个错误是团队组合重复统计。有人把 AB 和 BA 当成两个组合导致 team 数量变大。第三个错误比较隐蔽有人用字母是否出现超过一次来判断团队比如看到某条线是 ABB就说 B 出现了两次所以不是团队——这种理解把规则弄反了AB 这条线里 A 和 B 各承担了至少一个格子整条线只有两个字母恰恰就是团队获胜。5. 从这一场真题看青铜组的备考重点把三道题放在一起看会发现一套很清晰的能力要求几何题的建模能力、模拟题的细节把握能力、枚举题的去重意识。这三样东西都靠练不靠背模板。5.1 三道题的共同思维模式读题之后再问自己三个问题每次做完一道青铜题我都会强制自己回答三个问题这道题的约束条件里哪些被我当成废话跳过我的代码在最极端的数据下会不会崩如果答案是一个集合而不是我直觉里的单个值我有没有处理好并列和去重举个例子Blocked Billboard 里两块广告牌不重叠就是容易跳过的废话条件但它决定了能不能用简单的相加/扣减法。Milk Measurement 里的照片上是所有最高者就是集合思维Team Tic Tac Toe 里的不同组合就是去重思维。这三个小词每一个都能让人在样例全过的情况下爆零。低年级同学写代码常常只关注能跑出样例这是做题和比赛的差别。我自己后来复盘时每次都会故意改掉样例里的一个参数让答案发生变化再手算一遍验证代码对不对。比如数矩形面积时我会把卡车移开让可见面积等于总面积改牛奶变化量让最高集合出现三个人并列的情况改井字棋棋盘让某条线三个字母全相同。这些极端情况才是代码真正的试金石。5.2 我的一个互测方法写暴力程序对拍第三题我曾经担心 processLine 的判定逻辑有隐藏 bug于是写了一个不调用任何集合、单纯数格子的暴力版本然后随机生成棋盘数据让两个程序同时跑一天。对拍几十万组数据后发现两个版本完全一致我才对自己的去重逻辑彻底放心。这个暴力对拍的方法特别适合几何题和模拟题。Blocked Billboard 完全可以写一个逐格填充的暴力程序把两块广告牌按坐标填充到二维标记数组里再模拟卡车遮挡最后统计还有多少格被标记且未被遮挡。用随机坐标数据去对拍公式版比瞪眼找 bug 高效得多。USACO 青铜组没有时间限制压力花十分钟写个暴力对拍好过花两小时在脑内推演。5.3 接下来怎么练如果你刚打完这一场我建议把这三道题按三个层次重写第一遍合上参考代码凭记忆完整复现第二遍限时 30 分钟模拟比赛状态第三遍换一种语言比如用 Python 或 Java 各写一次体会不同语言里集合、排序、字符串处理的差异。完成这三步之后可以接着做 2018 年 1 月的青铜组真题。2018 年之后的题目风格会更强调模拟和排序和这一场有天然衔接。打竞赛最忌讳的是只刷题不复盘一套真题做三遍比囫囵吞枣刷十套新题有效得多。最后说一个我自己的小习惯。每次刷完一套 USACO 真题我不急着看官方题解而是先把自己代码里的每一个判断条件追着问一遍这个 if 成立的前提是什么如果输入是 0、是整个矩形完全盖住、是负的增量程序还成立吗把这三道题按这个标准过一遍比多刷十道题都管用。青铜组的满分从来不靠灵光一闪靠的是把想当然三个字从代码里彻底删掉。