如果要我用一句话形容 2020 年 2 月的 USACO 青铜组我会说这是一套把“暴力美学”发挥到极致的题目。Triangles 靠枚举Mad Scientist 靠数段Swapity Swap 靠循环分解三道题没有一道需要高级数据结构但你要是只会套模板反而容易被最后一题的巨大 K 值吓住。这套题非常适合两类人一类是刚刷完入门语法、准备接触算法竞赛的新手另一类是马上要打 USACO 月赛、想检验基本功的选手。跟着我完整过一遍你会明白青铜组真正想考察的从来不是复杂算法而是“把问题看透再动手实现”的能力。1. 2020年2月青铜组三道题到底在考你什么1.1 先看一眼三道题的考点分布在动手写代码之前我习惯先把一套题的“骨架”摸清楚。2020 年 2 月的青铜组三题恰好对应了青铜组最容易出现的三大主题暴力枚举、贪心计数、模拟抽象。把题目、考点和核心思路列在一张表里整个赛季的复习方向也会清楚很多。题目核心考察点核心思路参考复杂度P1 Triangles几何 枚举每个点作为直角顶点分别找水平、竖直方向的最大距离O(N^2) 或 O(N^3)N ≤ 100P2 Mad Scientist贪心 连续段把两个字符串的差异映射成 01 数组统计连续 1 段数量O(N)P3 Swapity Swap置换 循环节一轮操作是一个置换K 次就是沿置换走 K 步O(N·M N)K 再大也不怕这三题的代码量都不大真正的难点在于你能不能看出题目背后的结构。比如 Swapity Swap表面上是“模拟区间翻转”实际上是一个置换求幂的问题Mad Scientist 表面上是“翻转字符串”实际上是一个区间覆盖的贪心计数。这种“脱掉题面外衣看本质”的能力就是青铜组最想训练你的东西。1.2 这套题在青铜组里的定位从 2020 年 12 月开始USACO 青铜组的题目风格明显发生了变化题面变长、输入输出变复杂、部分题目甚至需要一点数据结构思维。相比之下2020 年 2 月这套题保留了老青铜组最经典的味道——所有问题都能用非常朴素的手段解决但前提是你想清楚了。我自己的经验是新赛季的铜组选手如果直接刷新版真题很容易被长题面劝退先拿这套题入门把“枚举、贪心、循环节”这三个基本功打牢后面再看新题型会轻松很多。做题顺序上我也建议先写 P2 Mad Scientist再写 P1 Triangles最后啃 P3 Swapity Swap。不是按题号来的而是按思维深度排的P2 读完就能动手P1 需要一点几何直觉P3 需要你主动做一个数学抽象。2. Triangles枚举直角点就是最优解2.1 先读懂题目里的几何限制Triangles 的题面说平面直角坐标系里有 N 个点农夫约翰想选三个点搭一个三角形帐篷要求三角形的两条边分别平行于 x 轴和 y 轴求能搭出的最大三角形面积的两倍。注意这句话“两条边分别平行于 x 轴和 y 轴”。这意味着这个三角形必然是一个直角三角形而且直角边是水平和竖直的。换句话说三个点中必须有两点共 x 坐标有两点共 y 坐标并且这两个“共坐标”的关系要有一个交点这个交点就是直角顶点。面积两倍的计算公式很干净设竖直边的长度为 |dy|水平边的长度为 |dx|那么三角形面积是 |dx · dy| / 2面积的两倍直接就是 |dx · dy|整数运算连浮点数都不用碰。我当年第一次做这道题时第一反应是枚举三个点检查它们是否满足条件然后算面积。N ≤ 100 的时候 O(N^3) 完全可行大约 100 万次操作一秒内绝对跑完。但如果你只是为了过题写 O(N^3) 没问题如果想把思路练得更干净下面这个“枚举直角顶点”的做法更值得学。2.2 为什么枚举直角点就够了对于任意一个满足条件的直角三角形它的直角顶点是唯一的。也就是说只要确定了直角顶点另外两个点一定分布在经过这个点的竖直线和水平线上一个点与直角顶点共 x形成竖直边另一个点与直角顶点共 y形成水平边。所以我们可以把问题拆成两步先枚举直角顶点 p再找以 p 为交点时能构成的最大三角形。固定 p 之后竖直边能取多长只取决于“和 p 有相同 x 坐标的点”中谁离 p 最远水平边能取多长只取决于“和 p 有相同 y 坐标的点”中谁离 p 最远。这两个条件互不干扰所以直接对每个 p 取两个方向的最大距离乘起来更新答案就行。复杂度从 O(N^3) 降到了 O(N^2)在 N 更大的变体题里也能直接套。这个思路背后的“贪心直觉”是你想让面积最大就得让两条直角边都尽量长由于水平边和竖直边互不影响所以分别取最大就是全局最优。这种“拆分互不干扰的维度再各自最大化”的思想以后做几何类题目会经常用到值得记下来。2.3 完整代码与复杂度说明下面给出我常用的 C17 实现。USACO 要求文件读写所以我直接用了ifstream/ofstream。如果是在本地 IDE 里调试把 fin / fout 临时改成 cin / cout 就可以。#include bits/stdc.h using namespace std; int main() { ifstream fin(triangles.in); ofstream fout(triangles.out); int n; fin n; vectorint x(n), y(n); for (int i 0; i n; i) { fin x[i] y[i]; } long long ans 0; for (int i 0; i n; i) { long long maxDy 0, maxDx 0; for (int j 0; j n; j) { if (i j) continue; if (x[j] x[i]) { maxDy max(maxDy, abs(1LL * y[j] - y[i])); } if (y[j] y[i]) { maxDx max(maxDx, abs(1LL * x[j] - x[i])); } } if (maxDy 0 maxDx 0) { ans max(ans, maxDy * maxDx); } } fout ans \n; return 0; }代码里有两个细节需要解释。第一abs(1LL * y[j] - y[i])里面的1LL是把差值先提升成 long long 再取绝对值否则如果坐标范围很大int 乘法会溢出。第二maxDy和maxDx初始化为 0只要存在共 x 或共 y 的点它们的值一定会大于 0因为题目保证所有点坐标互不相同。如果某个点既没有同 x 的点也没有同 y 的点那它不可能成为直角顶点直接跳过。2.4 这道题最容易错的地方第一是输出面积还是面积两倍。题目明确要求“面积的两倍”如果你按面积输出要么用浮点要么答案错一半正确做法是直接输出maxDy * maxDx。第二是坐标数据类型。坐标可以是负的两个点之间的距离要用绝对值坐标差值的乘积可能很大超过 int 的范围所以乘积和答案都要用 long long。很多人在本地小数据测试时没问题一到官方大数据就爆原因就是没注意类型。第三是条件写反。“共 x 找竖直边、共 y 找水平边”这个对应关系我在初学时就写反过一次。你可以在草稿纸上画一个直角坐标系直角顶点在左下角水平边延长到 (4,0)竖直边延长到 (0,3)。水平边两个点 y 相同竖直边两个点 x 相同对照着写就不会搞混。3. Mad Scientist一次翻转覆盖一整段3.1 把字符串问题抽象成 01 数组Mad Scientist 的题面讲的是一个“疯科学家”和奶牛的基因特征。给定两个由 G 和 H 组成的等长字符串 A 和 B每次操作可以翻转一个连续区间内的所有字符G 变 HH 变 G。问最少操作多少次才能把 A 变成 B。字符串操作题的第一反应通常是直接模拟翻转。但这里不用真的翻转因为每次翻转一个区间本质上是把区间内“已经不同”的字符变成“相同”把“相同”的字符变成“不同”。如果你定义一个差异数组diff[i] 1表示A[i] ! B[i]diff[i] 0表示相同那么一次区间翻转就是把diff数组这个区间里所有的 0 和 1 互换。我们的目标就变成了给定一个 01 数组每次可以把某个连续区间的 0/1 全部翻转问最少操作多少次能让它全变成 0。这样一来字符串这个外壳就被剥掉了剩下的问题非常干净。类似“三值排序”这类经典入门题也是这样表面上是序列操作实际上一旦建立正确的差异模型答案往往就是一个简单的计数问题。3.2 答案为什么等于连续 1 段的数量现在我们要想清楚最少操作次数是多少先看下界。diff数组连续的一段 1表示这段位置上的字符确实需要被改变。一次翻转操作作用在一个连续区间上它最多只能覆盖到一个完整的连续 1 段如果要同时消除两段不相邻的 1 段区间中间必然经过一段 0翻转后这段 0 会变成 1相当于给问题增加麻烦。所以至少需要“连续 1 段的数量”次操作才能把所有 1 清零。再看上界。我们可以每次选择一个连续 1 段把它单独翻转成 0这样做完所有段次数正好等于段数。于是上界和下界相等答案就是连续 1 段的数量。这个过程可以用一个更严谨的说法包装一下把diff数组看成一串 0/1每遇到一次从 0 到 1 的“上升沿”就说明新开了一个连续段上升沿的数量就是段数。我自己验证过一些小数据比如 A GGGGGB GHGHGdiff 是 01010连续 1 段有两个最少操作次数确实是 2第一次翻转第 2 个字符第二次翻转第 4 个字符。如果试图一次翻转第 2 到第 4 个字符反而会把中间已经对的字符改成错的得不偿失。3.3 代码实现与边界处理这道题的代码可以写得非常短。我的实现是维护一个inSegment标记当遇到A[i] ! B[i]且当前不在任何一个 1 段内时答案加一然后进入段内遇到相同字符时把标记清掉。#include bits/stdc.h using namespace std; int main() { ifstream fin(breedflip.in); ofstream fout(breedflip.out); int n; string a, b; fin n a b; int ans 0; bool inSegment false; for (int i 0; i n; i) { if (a[i] ! b[i]) { if (!inSegment) { ans; inSegment true; } } else { inSegment false; } } fout ans \n; return 0; }上面的写法等价于统计“上升沿”数量ans (a[i] ! b[i]) (i 0 || a[i-1] b[i-1])。我个人觉得inSegment写法可读性更好一些尤其在比赛紧张的时候不容易写错边界。注意一下文件名USACO 的官方文件名不一定和题目标题完全一致像这道 Mad Scientist 的提交文件名通常是breedflip.in/breedflip.out你以题目页面标注为准即可。本地调试时如果不想碰文件直接把fin/fout替换成cin/cout就行。3.4 现场容易踩的坑最容易犯的错误是把答案统计成“不同字符的总数”。比如 diff 是 111000111不同字符总数是 6但连续段数是 2正确答案是 2。原因就是一次翻转可以同时改变一整个连续段里的所有不同字符。我见过不少初学者卡在这个点上所以写代码前一定提醒自己题目问的是操作次数不是需要改变的字符个数。第二个容易错的地方是连续段的边界。假设整个数组全都是 1 段比如 diff 11111那么正确答案是 1不是很多如果数组全都是 0那么正确答案是 0。上面的代码通过inSegment标记自然处理了这两种情况。第三个需要注意的地方是不要真的去模拟翻转。翻转操作在这里只是我们推导用的概念实际代码只需要统计段数不需要修改字符串否则既浪费时间又容易写错。4. Swapity SwapK 次操作背后的置换逻辑4.1 先跑一轮把操作变成置换Swapity Swap 的题意很直观有 N 头牛排成一排初始从左到右编号是 1 到 N。农夫约翰给出 M 个区间操作每个操作把当前排列中某个区间整体翻转。所有 M 个操作按顺序执行一遍算作一轮整个一轮要重复 K 轮最后输出每个位置上的奶牛编号。最容易想到的做法是直接循环 K 轮每轮模拟 M 次翻转。但 K 最大可以到 1e9这个方法在时间上完全不可行。注意到 N 和 M 都很小所以必然存在某种周期性可以利用。我的做法是先把一轮完整操作的结果抽出来变成一个“置换”然后再处理 K 次幂。具体来说用一个数组f[i]表示初始位于位置 i 的奶牛经过一轮完整操作后跑到了哪个位置。开始时f[i] i每遇到一个区间[L, R]把f数组中下标 L 到 R 的部分做一次reverse。一轮结束后f数组就完整记录了这个置换的映射关系。比如 N 4只有一条操作[1, 4]一轮后f[1] 4f[2] 3f[3] 2f[4] 1。这意味着初始在 1 号位的牛最终到了 4 号位初始在 2 号位的牛到了 3 号位。这里为什么要用“初始位置”作为下标而不是模拟当前排列因为一旦把问题看成“每个初始位置经过一轮后去哪里”重复 K 轮就变成了“把这个函数应用 K 次”。这是处理超大操作次数的标准思想大厂笔试里的字符串轮换、数组置换类题目也经常用到同一套逻辑。4.2 循环分解大 K 的克星一个置换一定可以分解成若干个循环cycle。什么意思呢从任意一个位置出发反复应用f你会绕回起点这个闭环就是循环。比如上面的例子中1 - 4 - 12 - 3 - 2就是两个长度为 2 的循环。对于循环里的每个元素走 K 步之后的位置是可以直接算出来的如果循环长度是len那么在循环里前进 K 步和前进K % len步是等价的。这就是解决巨大 K 的关键。我先找到所有循环然后对每个循环单独处理。具体实现时用vis数组标记访问过的位置。从 1 到 N 扫一遍遇到没访问过的点就沿着f走下去把沿途的点存成一个cycle数组同时标记访问。得到循环后对循环中第 j 个元素cycle[j]它走 K 步之后的位置就是cycle[(j K) % len]。最后我们把它放回最终排列的对应位置。这里的方向逻辑需要特别小心cycle[j]表示“初始位置”cycle[(j K) % len]表示“经过 K 轮之后所在的位置”而我们最终要输出的数组下标是位置值是该位置上的奶牛编号。初始位置 i 上的奶牛编号就是 i所以赋值语句应该是finalPos[终点位置] 初始位置。4.3 完整代码与一个验证用小例子下面是我提交过的 C17 完整代码附带了注释帮助理清方向。#include bits/stdc.h using namespace std; int main() { ifstream fin(swapity.in); ofstream fout(swapity.out); int n, m, k; fin n m k; vectorpairint, int ops(m); for (int i 0; i m; i) { int l, r; fin l r; ops[i] {l, r}; } // f[i]初始位置 i 的奶牛经过一轮完整操作后的位置 vectorint f(n 1); for (int i 1; i n; i) f[i] i; for (auto [l, r] : ops) { reverse(f.begin() l, f.begin() r 1); } vectorint finalPos(n 1, 0); vectorbool vis(n 1, false); for (int i 1; i n; i) { if (vis[i]) continue; vectorint cycle; int cur i; while (!vis[cur]) { vis[cur] true; cycle.push_back(cur); cur f[cur]; } int len (int)cycle.size(); for (int j 0; j len; j) { int startPos cycle[j]; // 初始位置 int endPos cycle[(j k) % len]; // 走 K 步后的位置 finalPos[endPos] startPos; } } for (int i 1; i n; i) { fout finalPos[i] \n; } return 0; }验证方向有没有搞反我建议用小数据手算一遍。还是 N 4只有操作[1, 4]K 2。手动模拟第一轮[4, 3, 2, 1]第二轮又翻转回来[1, 2, 3, 4]所以答案应该是 1 2 3 4。用上面的代码跑一遍f [0, 4, 3, 2, 1]循环是 (1 4) 和 (2 3)K 2 取模后每个点都回到自己finalPos 是 1 2 3 4和手算一致。如果 K 3手动模拟第三轮是[4, 3, 2, 1]代码输出 4 3 2 1也对。这样验证过一次方向就不会记错。4.4 方向性陷阱与调试建议这道题是整套题里最容易写反方向的。很多人的第一版代码会写成finalPos[startPos] endPos这样输出的其实是“每个初始位置上的最终奶牛编号”但奶牛编号等于初始位置所以你会发现输出结果完全错乱。我的建议是牢牢记住两个概念数组下标是位置数组值是奶牛编号赋值时永远问自己“我现在是拿了谁放到哪里”。调试时还有一个很实用的技巧写一个暴力版本直接循环 K 轮模拟用它和循环分解版本对拍。K 取小一点比如 5随机生成几组 N 和 M 都很小的数据两边输出一致基本就说明逻辑正确。我当年写这种置换题目时对拍帮我把方向错误从半小时里救了出来强烈推荐养成这个习惯。另外要注意K % len的边界如果 K 刚好是 len 的整数倍每个点会回到自己的初始位置这是符合直觉的如果 len 为 1也就是某个点在置换下不动那么(j K) % 1永远等于 0也不会有问题。代码里没有用快速幂是因为 N 很小循环分解就够了等以后做到 Silver 和 Gold 的置换题可以再学二进制快速幂来求置换的 K 次幂思路也是一脉相通的。5. 青铜组比赛最容易被忽视的几个实战细节5.1 拿到题目先做的三件事青铜组的题目读起来往往很直白但你急着写代码之前我建议先把三件事做完第一把数据范围圈出来特别是 K、N、M 这些可能影响复杂度的数字第二在草稿纸上按题目样例手动跑一遍保证自己对“每一步操作改变了什么”有画面感第三想清楚答案大概是什么量级有没有可能超过 int需不需要开 long long。这套 2020 年 2 月的题目里Triangles 的答案可能很大Swapity Swap 的 K 大得离谱这两题如果没提前做这些准备写代码时一定会卡住。尤其是数据范围USACO 每道题都会明确写出来它不是摆设而是解题提示的一部分K 大到 1e9就是告诉你别直接模拟N 小到 100就是告诉你暴力枚举完全可行。学会从数据范围反向推断预期算法是竞赛里很重要的一项能力。5.2 文件读写和 long long 的肌肉记忆USACO 的提交系统要求程序从.in文件读入把答案写到.out文件。如果你在本地直接跑cin/cout版本代码没问题但提交后会 Runtime Error。我自己的做法是把文件读写固定成一个模板新建题目时直接复制避免每次手敲。代码中的文件名以题目页面上的说明为准不要盲猜比如 Mad Scientist 这一题很多同学想当然用mad scientist.in但文件名里不能有空格实际提交文件名可能是breedflip.in。另一个肌肉记忆是 long long。青铜组的题目虽然简单但坐标、答案都可能超出 32 位整数的范围。我的习惯是所有可能做乘法的中间变量直接声明成 long long如果看到坐标范围写了 1e5 以上或者题目要求输出“两倍面积”之类的乘积那更是必须用 long long。多写一个1LL *不会损失什么但漏掉一次可能就是一次 WA。5.3 用对拍和小样例验证思路对拍听起来很高级其实做法很简单你写一个保证正确的暴力版本再写一个你认为是正解的优化版本生成随机小数据让两个版本跑同样的输入比较输出。青铜组的数据范围都很小暴力版本通常就是真正的模拟比如 Swapity Swap 的暴力就是循环 K 轮翻转K 取小值即可。一旦输出不一致就把那组数据拿来人工分析定位是哪一步出了问题。这套题的很多陷阱都可以靠小样例暴露。Triangles 可以测只有 3 个点且构成最小三角形的情况Mad Scientist 可以测 A 和 B 完全相同、以及全部字符都不相同的边界Swapity Swap 可以测 K 1、K 为循环长度的整数倍、以及只有一个翻转区间的情况。把这些边界样例在本地跑熟比赛时的心态会稳很多。5.4 我对这套题的个人体会带过不少零基础选手之后我发现大家在三道题上的卡点很有规律卡 P1 的人通常是不敢把问题拆成“直角点 两条边”去枚举卡 P2 的人通常是没想到用差异数组抽象卡 P3 的人几乎全都是在巨大的 K 面前慌了神。这套题其实一直在传达同一个信息青铜组不考偏题怪题它考的是你把一个表面复杂的问题简化成已知模型的能力。以后你再遇到“某操作重复很多次”的题目应该立刻想到置换、循环节和取模再遇到“最少操作次数”的题目应该先想想答案是不是一个简单的计数值。能把这一步做好青铜组对你来说就不再是障碍而是迈向银组的第一块跳板。