尧图网站开发 
每年12月的USACO月赛都是青铜组选手最熟悉的练兵场。2023年12月这场三道题恰好覆盖了模拟、连续区间分析、排序与分类讨论难度曲线几乎就是青铜组的标准模板特别适合刚接触算法竞赛、想在USACO里拿第一块奖牌的新手反复咀嚼。很多同学刷这套题时卡住的往往不是算法本身而是题意理解、边界处理和代码细节。这篇文章就把这三道题的核心思路、完整代码以及我自己实际踩过的坑一次讲清楚给准备打USACO青铜组、或者已经在青铜组边缘徘徊的读者一份可以直接参考的复盘笔记。先说结论这套题不考高级数据结构不考复杂的图论甚至不需要会二分和动态规划青铜组的定位就是“把问题读懂用最朴素的办法解决它”。只要能熟练掌握循环、数组、排序、简单贪心和分类讨论三道题都能做出正解。难点在于每一道题包装得都比较花哨你需要从故事里把数学结构剥出来这一步往往是新手最缺的。1. 整体拆解2023年12月青铜组到底考了什么1.1 三道题的考察点与难度定位第一题是糖果棒模拟题核心是“按规则模拟奶牛吃糖果”的过程。表面上是个模拟实际考察的是你能不能把题目里的“舔糖果棒”翻译成连续区间上的推进问题同时对数据范围保持敏感。第二题是奶牛感染追踪给定最终感染状态推断最少可能的初始感染牛数量。这道题包装成“流行病学”故事本质是一个连续 1 区间的分析题。只要把每段连续 1 的长度提取出来再枚举统一的传播半径答案就能算出来。第三题是关于奶牛身高排名的判定题问是否存在某个整数天数 T使得每头牛身边恰好有指定数量的牛比它高。这道题考的是排序、分类讨论、以及“候选值枚举”的思想青铜组里算是偏难的压轴题。从难度梯度看第一题是保分题第二题是中档题第三题是区分题。USACO青铜组通常就是这种结构前两题保证基础选手能拿分第三题拉开差距。所以如果你目标是青铜组通过前两题必须稳第三题尽力而为如果你目标是满分青铜第三题就得把“候选点枚举”这种思路练熟。1.2 为什么这组题特别适合当教材我这两年带新手最喜欢拿这组题当第一套“真题试炼”。原因是它的三个考点非常典型往后进阶白银组时还会反复遇到模拟题考验的是“把过程描述变成精确逻辑”的能力这个能力在几乎所有题目里都要用。连续区间题考验的是“把场景问题抽象成数组问题”的建模能力。排序与判定题考验的是“在变化过程中找不变量”的思维习惯。这三个能力恰好是USACO从青铜到白银最核心的三块基石。把这套题吃透再去看白银组的题你会发现自己至少不会因为“读不懂题、不知道从哪下手”而卡住。2. 第一题 Candy Cane Feast别被“糖果”骗了本质是区间模拟2.1 题意还原与手推样例这题说的是 N 头奶牛站成一排每头牛有初始身高 h_i。地上有 M 根糖果棒每根长度为 l_j。处理一根糖果棒时从第 1 头牛开始牛按编号轮流舔这根棒如果这头牛的当前身高大于糖果棒已经被舔掉的高度它就能吃到“自己身高”和“棒顶端”之间那一段吃到的这一段会让它的身高同步增加同时糖果棒被舔掉的高度也对应增加。如果一根棒被完全吃完就直接处理下一根。举个例子假设 N3三头牛身高分别是 1、2、3有两根糖果棒长度都是 4。第一根棒开始时已经舔掉的高度 lo0棒顶端高度 hi4。牛1身高 1 大于 lo所以吃 min(1,4)-01身高变 2lo 变成 1。牛2身高 2 大于 1吃 min(2,4)-11身高变 3lo 变成 2。牛3身高 3 大于 2吃 min(3,4)-21身高变 4lo 变成 3。棒没吃完但所有牛都轮过一遍第一根棒结束。第二根棒同理lo 从 0 重新开始。牛1身高现在是 2吃 2身高变 4lo 变 2牛2身高 3吃 1身高变 4lo 变 3牛3身高 4吃 1身高变 5lo 变 4。此时 lo 等于棒顶端棒被吃完直接结束。最终三头牛身高是 4、4、5。这个手推样例很重要它展示了两个关键细节每根棒处理时 lo 都要重置为 0每头牛在一根棒的处理过程中最多只会吃到一次因为吃过后它的身高至少能达到当前的 lo后续即使再轮到它身高不再大于 lo也就吃不到了。2.2 模拟实现与复杂度讨论理解了过程代码就是很朴素的二重循环#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin N M; vectorll h(N); for (int i 0; i N; i) cin h[i]; vectorll candy(M); for (int j 0; j M; j) cin candy[j]; for (int j 0; j M; j) { ll lo 0; // 已舔掉的高度 ll hi candy[j]; // 棒顶端高度 for (int i 0; i N; i) { if (h[i] lo) { // 注意是大于不是大于等于 ll eat min(h[i], hi) - lo; h[i] eat; lo eat; if (lo hi) break; // 棒被吃完就直接结束 } } } for (ll x : h) cout x \n; return 0; }这里必须用 long long因为身高和糖棒长度的数量级都在 1e9 附近多根棒累积后很容易超出 int 范围。复杂度方面最坏情况是 O(M×N)看起来像是会超时。但实际跑的时候有两个重要剪枝第一lo 一旦等于 hi内层循环立刻结束很多测试点里糖果棒会被某头大个子牛一口吃完第二如果一根棒处理完所有牛之后 lo 没有变化说明后续也不会有牛能吃到但我们的循环本身只扫一遍所有牛不会出现重复无意义扫描。要注意的是USACO 官方数据中这个模拟做法通常能通过但严谨地说如果数据构造得特别刁钻二重循环确实存在极限压力。我在实际写的时候会更倾向于保留这个直观写法因为它最不容易出错如果追求绝对稳妥可以再维护一个“当前最低可吃身高”的指针来减少无效判断但青铜组阶段不必把代码搞得这么复杂。2.3 我踩过的坑等于号与 lo 的更新顺序这题我至少见过三种写错的方式。第一种是判断条件写成 h[i] lo。这会导致牛在身高刚好等于已吃高度时也去吃但题目说的是“如果它身高足够高能舔到更高位置”等于时它其实够不到糖棒顶端更长的部分所以必须是严格大于。第二种是更新 lo 时把顺序写反。先更新 lo 再算 eat或者先改 h[i] 再用原来的 lo都会算出负数或者错误增量。正确的顺序是先算出“能吃多少”再同步更新 h[i] 和 lo。第三种是忘记重置 lo。每根新的糖果棒都是从地面开始放的上一根棒吃剩的部分不会带过来所以 lo 必须在每轮外层循环开始时重置为 0。这个细节手推样例时很容易发现但写代码一着急就容易漏。3. 第二题 Cowntact Tracing从感染扩散到连续区间3.1 问题如何转化为区间长度统计第二题的故事是一排 N 个牛棚每个牛棚要么有牛用 1 表示要么空着用 0 表示。某天晚上一些牛被感染了之后每个夜晚已经感染的牛会把疾病传染给相邻的牛。给定最终所有牛棚的状态问最初至少有多少头牛被感染才能经过若干夜晚变成这个状态。关键信息是所有最初感染的牛经历的夜晚数是同一个 r。你不能给甲算 3 晚、给乙算 5 晚。这个“同一个 r”是整道题的命门。先把最终状态里的连续 1 段全部提取出来。比如 1110011 可以分成两个段长度分别是 3 和 2。为什么可以分段因为 0 隔断了传播路径一段连续 1 只能由它内部的初始感染者产生不同段之间互不影响各自独立。那每段长度是 len 时需要多少头初始感染牛呢假设有一头初始感染牛经过 r 个夜晚它最多能覆盖的长度是 2r1初始自己占 1 格每夜向左右各扩 1 格r 夜后左右各 r 格加起来就是 12r。所以对于长度为 len 的连续 1 段在给定 r 的情况下最少需要的初始感染者数量是 ceil(len / (2r1))。也就是说用若干段长度为 2r1 的覆盖区间去铺满 len 个位置。但 r 不能乱取。如果 2r1 大于 len一头牛覆盖的范围会超出这段连续 1 的边界把旁边的 0 也感染那最终状态就不成立了。所以对于长度 len 的段允许的 r 必须满足 2r1 ≤ len即 r ≤ (len-1)/2。这个值取整后就是该段允许的最大半径。所有段共用一个 r因此全局允许的 r 上限是所有段各自最大半径里的最小值。3.2 枚举半径并计算最小初始感染数算法步骤非常清晰扫描字符串提取所有连续 1 段的长度。计算 Rmax它是每段 (len-1)/2 的最小值。对 r 0, 1, ..., Rmax 分别计算总初始感染数取最小值。计算总感染数时每段需要的初始牛数是 ceil(len / (2r1))。这可以用整数公式 (len 2r) / (2r 1) 计算避免浮点误差。#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; string s; cin N s; vectorint lens; int Rmax N; // 初始给个大值 for (int i 0; i N; ) { if (s[i] 0) { i; continue; } int j i; while (j N s[j] 1) j; int len j - i; lens.push_back(len); Rmax min(Rmax, (len - 1) / 2); i j; } ll ans N; // 上界每个 1 都作为初始感染者 for (int r 0; r Rmax; r) { ll cur 0; for (int len : lens) { cur (len 2LL * r) / (2LL * r 1); } ans min(ans, cur); } cout ans \n; return 0; }这里有个很漂亮的复杂度结论表面上 r 从 0 枚举到 Rmax每轮都要扫所有段像是 O(N × Rmax)。但因为每个段的长度都不小于 2r1段的个数 M 一定满足 M ≤ N / (2Rmax1)。所以总扫描量 M × (Rmax1) 是 O(N) 级别的。换句话说这题的枚举并不慢放心写。3.3 边界条件与容易忽略的细节第一r 的起始值。有的题描述里明确说了“至少经过一个夜晚”那 r 就要从 1 开始枚举如果题意允许 0 个夜晚初始状态就等于最终状态r0 也必须算进候选。稳妥的做法是题目怎么问就怎么来不确定时把 r0 和 r≥1 都算一遍取最小值因为多算一个并不影响正确性但要注意如果题意硬性要求 r≥1把 r0 的情况纳进来会有风险。我自己的习惯是读题时先确认 r 是否限定为正整数再决定枚举起点。第二连续 1 段不能跨越 0。很多新手会把 1110111 当成一整段其实中间 0 破坏了两侧的联系必须分成两段分别计算。第三Rmax 可能很小。比如 s 是 1001两段长度都是 1Rmax 是 0这时答案就是所有 1 都作为初始感染者因为每个点都独自感染没有任何传播发生。这种极端数据是最容易让人怀疑代码是不是写错的但其实是对的。第四整串全是 0。这种情况下没有连续 1 段lens 为空答案应该是 0。代码里要避免对空数组做计算时报错。4. 第三题 Farmer John Actually Farms排名约束与时间窗口4.1 把“恰好有 t_i 头牛比它高”翻译成排名条件第三题是我认为这套题里含金量最高的一道。故事大概是FJ 的 N 头奶牛初始高度是 h_i每天都会长高 a_i。FJ 想在某个未来的第 T 天检查牛群并且对每头牛 i 有一个要求恰好有 t_i 头牛比它高。问是否存在这样的正整数 T。这个“恰好有 t_i 头牛比它高”本质上是在描述 T 天时牛群的排名。如果一头牛上方恰好有 k 头牛比它更高那它在降序排序中应该处在第 k1 个位置如果几头牛高度相等它们互不比对方高所以它们上方比它们高的牛数量是一样的也就是它们的 t 值必须相同。先想清楚一个基本事实第 i 头牛第 T 天的高度是 h_i a_i × T这是关于 T 的一条直线。两条直线的大小关系最多只会在它们相等的那一刻改变一次。这意味着所有牛的相对排名不会频繁变化只会在一系列“交点时刻”发生切换。如果我们把这些交点时刻找出来那么在每两个相邻交点之间的时间段里所有牛的相对顺序是固定不变的。于是问题就变成把时间轴切成若干个区间在每个区间里任取一个整数 T检查牛群的排名是否满足 t_i 的条件。只要有一个区间里的某个整数 T 满足答案就是 YES。4.2 用候选时间点代替完整区间判断理论上需要枚举所有区间但实现上有个更简单的等价做法直接收集所有“可能改变排序”的时间点附近的整数作为候选 T逐个检查。为什么足够因为如果某个开区间 (L, R) 内存在满足条件的整数 T那么排序在这个开区间内不变区间内任意一个整数检查结果都一样如果区间内没有整数那唯一可能的整数就在端点附近而我们把端点附近的整数也收进候选就不会漏掉。对于任意两头牛 i 和 j如果 a_i ≠ a_j它们高度相等的时间是T (h_j - h_i) / (a_i - a_j)如果这个 T 是正数说明未来某个时刻两头牛会“相遇”相遇后谁高谁低反过来。把所有这样的正交点时间收集起来把每个交点时间附近的几个整数比如 floor(T)-2 到 floor(T)2都加入候选集合。最后再补上 T1 和一个超大的稳定时间比如 1e97然后逐个 check。这里要注意T1e97 用来表示“足够远以后”因为所有增速不同的牛在足够远以后排名只会由增长速率决定不会再改变。把一个大时间放进候选相当于固定了无限远处的排名状态。检查函数本身很简单给定 T算出每头牛的身高按身高降序排序然后从左到右记录“严格高于当前牛的牛的数量”再和每头牛的 t_i 对比。#include bits/stdc.h using namespace std; typedef long long ll; int N; vectorll h, a, t; bool check(ll T) { vectorpairll, int cow(N); for (int i 0; i N; i) { cow[i] {h[i] a[i] * T, i}; } sort(cow.rbegin(), cow.rend()); // 身高降序 int higher 0; for (int i 0; i N; i) { if (i 0 cow[i].first cow[i - 1].first) { higher i; // 当前牛严格低于前一头前面的 i 头都严格更高 } // 如果和上一头同高higher 不变因为同高的牛互不比对方高 if (higher ! t[cow[i].second]) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin N; h.resize(N); a.resize(N); t.resize(N); for (int i 0; i N; i) cin h[i]; for (int i 0; i N; i) cin a[i]; for (int i 0; i N; i) cin t[i]; vectorll cand; cand.push_back(1); cand.push_back(1000000007LL); for (int i 0; i N; i) { for (int j i 1; j N; j) { if (a[i] a[j]) continue; // 两条线平行永远不相交 // 交点 T (h[j] - h[i]) / (a[i] - a[j]) double inter 1.0 * (h[j] - h[i]) / (a[i] - a[j]); if (inter 0) { ll base (ll)floor(inter); for (ll k base - 2; k base 2; k) { if (k 1) cand.push_back(k); } } } } sort(cand.begin(), cand.end()); cand.erase(unique(cand.begin(), cand.end()), cand.end()); bool ok false; for (ll T : cand) { if (check(T)) { ok true; break; } } cout (ok ? YES : NO) \n; return 0; }这个做法的时间复杂度很宽松N 很小的情况下候选点数量有限每次 check 是 O(N log N)完全够用。如果 N 更大就需要用更精细的区间扫描法但青铜组没有必要。4.3 这题的思维陷阱与代码细节这题最容易错的地方是把“严格比它高”和“非严格排名”混在一起。如果几头牛高度相等它们各自上方“严格更高”的数量完全一样所以 t 值必须相等但它们在降序排序里的下标却不同你必须用“严格更高数量”去对 t而不是用“排序位置”。另外double 计算交点会带来精度问题。在实际比赛中我建议用分数形式或者 long double 来做候选点因为你只需要在交点附近取整数精度稍微差一点问题不大但如果差太多就可能漏掉正确的候选。最稳的办法是把每个交点附近多取几个整数覆盖掉浮点误差。关于 T 的取值题目问的是正整数所以候选 T 从 1 开始。如果题目改成“非负整数”那 T0 也要纳入。这种细节直接决定答案边界读题时一定要盯死。4.4 顺带聊聊经典题三值排序之所以要在这里提三值排序是因为它和第三题一样都在考察“排序里的结构”第三题研究的是“排名约束随时间变化”三值排序研究的是“有限几类元素如何用最少交换次数排好”。这是USACO题库里非常经典的一道题很多同学在青铜组后期或者升白银前的训练里都会遇到。题目很朴素给定一个只包含 1、2、3 的序列每次可以交换任意两个位置的数字问最少多少次交换能让整个序列变成非递减序列。思路是把最终状态先确定下来统计 1、2、3 各有多少个那么排序后第一段全是 1第二段全是 2第三段全是 3。然后扫描原序列记录每个“目标段”里出现了多少种“错误数字”。比如第一段里出现了 x 个 2第二段里出现了 y 个 1这两个错位数字可以直接交换一次各归各位。所以先处理所有两两直接互换就能消掉的配对。剩下的错位数字会形成长度为 3 的循环比如第一段还有 2、第二段还有 3、第三段还有 1这时候三个数字需要两次交换才能全部归位。累计答案即可。int cnt[4] {0}; for (int v : a) cnt[v]; int bad[4][4] {0}; int pos 0; for (int seg 1; seg 3; seg) { for (int k 0; k cnt[seg]; k, pos) { bad[seg][a[pos]]; } } int ans 0; for (int i 1; i 3; i) { for (int j i 1; j 3; j) { int x min(bad[i][j], bad[j][i]); ans x; bad[i][j] - x; bad[j][i] - x; } } int remain 0; for (int i 1; i 3; i) for (int j 1; j 3; j) if (i ! j) remain bad[i][j]; ans remain / 3 * 2; cout ans \n;第一次交换消除的两两错位每次交换让两个数字都回到正确段第二次处理循环错位时每个循环由三个错位数字组成需要两次交换。这个“先消配对再处理环”的思路其实和第三题里“先观察结构再分类处理”的思维方式一脉相承。5. 青铜组常见失误与备考FAQ5.1 四个最容易翻车的地方第一个是数据类型。青铜组数据量不大但数值可能很大。第三题里 h_i 加上 a_i × T很容易超过 2^31不用 long long 必挂。USACO 的题目不会专门提醒你开 long long这属于基本功。第二个是“大于”和“大于等于”的边界。第一题已经演示过了h[i] lo 和 h[i] lo 是两种完全不同的规则。这种细节只能靠手推样例时逐行核对写代码时尤其要警惕。第三个是只看样例不看极端情况。很多新手样例过了就提交结果挂在这种数据上全是 0、全是 1、只有一个 1、所有牛增速相同、所有牛初始身高相同。比赛前可以在脑子里快速过一遍这些极端输入。第四个是枚举范围没想清楚。第三题如果你直接枚举 T 从 1 到 1e9肯定超时但如果你不枚举候选点又可能漏答案。青铜组的题往往不需要很复杂的优化但需要你把“枚举什么东西”想清楚。5.2 常见问题速查问题原因处理方式第一题输出比预期大可能把等于时也算了进食检查 h[i] lo 是否严格大于第二题答案偏大每段单独取半径而不是统一半径保证所有段共用同一个 r第二题全是 0 时出错没有处理空区间lens 为空时直接输出 0第三题 YES 漏判候选 T 没覆盖到整数区间交点附近多取几个整数加上特大稳定时间第三题把排名搞错混同了并列高度和严格高于用“严格更高数量”去匹配 t_i总溢出int 不够用所有涉及高度和天数的变量用 long long5.3 从这场真题出发下一步怎么规划如果你能独立把这套题的三道题都做出来青铜组的核心能力基本就达标了。接下来往白银组走重点补两件事。第一是时间复杂度分析。青铜组很多题暴力都能过但白银组就不行了你要开始习惯在写代码前先算一下 N 最大是多少、算法复杂度是多少、会不会超时。第二是掌握更系统的算法工具。白银组常考的二分答案、前缀和、简单的图遍历、贪心证明都是青铜组题目的自然延伸。比如第二题感染追踪如果你把枚举半径改成二分查找再套一层更复杂的图论背景就是典型的白银组升级套路。最后说点我自己的体会这套题我前前后后带人刷过好几遍每次都会有新发现。第一次刷的时候我在第一题上栽了跟头因为没注意身高会超过 int 范围第二次刷的时候我在第二题纠结了很久总觉得每个感染区间应该有自己的半径后来才想明白“统一半径”才是题意第三题反而是我后来觉得最有收获的一道因为“候选时间点”这个技巧在后面的月赛里也经常用到学会了它很多带时间参数的问题都有了突破口。如果你正在准备USACO青铜组我的建议很简单不要急着刷难题先把这种中等难度的月赛真题吃透每道题都做到能手写复现再追求速度和拓展。USACO的晋级从来不是靠某个难题突然开窍而是靠一道道真题积累起来的手感和判断力。这场 2023 年 12 月的青铜组就是一个非常不错的起点。 
每年12月的USACO月赛都是青铜组选手最熟悉的练兵场。2023年12月这场三道题恰好覆盖了模拟、连续区间分析、排序与分类讨论难度曲线几乎就是青铜组的标准模板特别适合刚接触算法竞赛、想在USACO里拿第一块奖牌的新手反复咀嚼。很多同学刷这套题时卡住的往往不是算法本身而是题意理解、边界处理和代码细节。这篇文章就把这三道题的核心思路、完整代码以及我自己实际踩过的坑一次讲清楚给准备打USACO青铜组、或者已经在青铜组边缘徘徊的读者一份可以直接参考的复盘笔记。先说结论这套题不考高级数据结构不考复杂的图论甚至不需要会二分和动态规划青铜组的定位就是“把问题读懂用最朴素的办法解决它”。只要能熟练掌握循环、数组、排序、简单贪心和分类讨论三道题都能做出正解。难点在于每一道题包装得都比较花哨你需要从故事里把数学结构剥出来这一步往往是新手最缺的。1. 整体拆解2023年12月青铜组到底考了什么1.1 三道题的考察点与难度定位第一题是糖果棒模拟题核心是“按规则模拟奶牛吃糖果”的过程。表面上是个模拟实际考察的是你能不能把题目里的“舔糖果棒”翻译成连续区间上的推进问题同时对数据范围保持敏感。第二题是奶牛感染追踪给定最终感染状态推断最少可能的初始感染牛数量。这道题包装成“流行病学”故事本质是一个连续 1 区间的分析题。只要把每段连续 1 的长度提取出来再枚举统一的传播半径答案就能算出来。第三题是关于奶牛身高排名的判定题问是否存在某个整数天数 T使得每头牛身边恰好有指定数量的牛比它高。这道题考的是排序、分类讨论、以及“候选值枚举”的思想青铜组里算是偏难的压轴题。从难度梯度看第一题是保分题第二题是中档题第三题是区分题。USACO青铜组通常就是这种结构前两题保证基础选手能拿分第三题拉开差距。所以如果你目标是青铜组通过前两题必须稳第三题尽力而为如果你目标是满分青铜第三题就得把“候选点枚举”这种思路练熟。1.2 为什么这组题特别适合当教材我这两年带新手最喜欢拿这组题当第一套“真题试炼”。原因是它的三个考点非常典型往后进阶白银组时还会反复遇到模拟题考验的是“把过程描述变成精确逻辑”的能力这个能力在几乎所有题目里都要用。连续区间题考验的是“把场景问题抽象成数组问题”的建模能力。排序与判定题考验的是“在变化过程中找不变量”的思维习惯。这三个能力恰好是USACO从青铜到白银最核心的三块基石。把这套题吃透再去看白银组的题你会发现自己至少不会因为“读不懂题、不知道从哪下手”而卡住。2. 第一题 Candy Cane Feast别被“糖果”骗了本质是区间模拟2.1 题意还原与手推样例这题说的是 N 头奶牛站成一排每头牛有初始身高 h_i。地上有 M 根糖果棒每根长度为 l_j。处理一根糖果棒时从第 1 头牛开始牛按编号轮流舔这根棒如果这头牛的当前身高大于糖果棒已经被舔掉的高度它就能吃到“自己身高”和“棒顶端”之间那一段吃到的这一段会让它的身高同步增加同时糖果棒被舔掉的高度也对应增加。如果一根棒被完全吃完就直接处理下一根。举个例子假设 N3三头牛身高分别是 1、2、3有两根糖果棒长度都是 4。第一根棒开始时已经舔掉的高度 lo0棒顶端高度 hi4。牛1身高 1 大于 lo所以吃 min(1,4)-01身高变 2lo 变成 1。牛2身高 2 大于 1吃 min(2,4)-11身高变 3lo 变成 2。牛3身高 3 大于 2吃 min(3,4)-21身高变 4lo 变成 3。棒没吃完但所有牛都轮过一遍第一根棒结束。第二根棒同理lo 从 0 重新开始。牛1身高现在是 2吃 2身高变 4lo 变 2牛2身高 3吃 1身高变 4lo 变 3牛3身高 4吃 1身高变 5lo 变 4。此时 lo 等于棒顶端棒被吃完直接结束。最终三头牛身高是 4、4、5。这个手推样例很重要它展示了两个关键细节每根棒处理时 lo 都要重置为 0每头牛在一根棒的处理过程中最多只会吃到一次因为吃过后它的身高至少能达到当前的 lo后续即使再轮到它身高不再大于 lo也就吃不到了。2.2 模拟实现与复杂度讨论理解了过程代码就是很朴素的二重循环#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin N M; vectorll h(N); for (int i 0; i N; i) cin h[i]; vectorll candy(M); for (int j 0; j M; j) cin candy[j]; for (int j 0; j M; j) { ll lo 0; // 已舔掉的高度 ll hi candy[j]; // 棒顶端高度 for (int i 0; i N; i) { if (h[i] lo) { // 注意是大于不是大于等于 ll eat min(h[i], hi) - lo; h[i] eat; lo eat; if (lo hi) break; // 棒被吃完就直接结束 } } } for (ll x : h) cout x \n; return 0; }这里必须用 long long因为身高和糖棒长度的数量级都在 1e9 附近多根棒累积后很容易超出 int 范围。复杂度方面最坏情况是 O(M×N)看起来像是会超时。但实际跑的时候有两个重要剪枝第一lo 一旦等于 hi内层循环立刻结束很多测试点里糖果棒会被某头大个子牛一口吃完第二如果一根棒处理完所有牛之后 lo 没有变化说明后续也不会有牛能吃到但我们的循环本身只扫一遍所有牛不会出现重复无意义扫描。要注意的是USACO 官方数据中这个模拟做法通常能通过但严谨地说如果数据构造得特别刁钻二重循环确实存在极限压力。我在实际写的时候会更倾向于保留这个直观写法因为它最不容易出错如果追求绝对稳妥可以再维护一个“当前最低可吃身高”的指针来减少无效判断但青铜组阶段不必把代码搞得这么复杂。2.3 我踩过的坑等于号与 lo 的更新顺序这题我至少见过三种写错的方式。第一种是判断条件写成 h[i] lo。这会导致牛在身高刚好等于已吃高度时也去吃但题目说的是“如果它身高足够高能舔到更高位置”等于时它其实够不到糖棒顶端更长的部分所以必须是严格大于。第二种是更新 lo 时把顺序写反。先更新 lo 再算 eat或者先改 h[i] 再用原来的 lo都会算出负数或者错误增量。正确的顺序是先算出“能吃多少”再同步更新 h[i] 和 lo。第三种是忘记重置 lo。每根新的糖果棒都是从地面开始放的上一根棒吃剩的部分不会带过来所以 lo 必须在每轮外层循环开始时重置为 0。这个细节手推样例时很容易发现但写代码一着急就容易漏。3. 第二题 Cowntact Tracing从感染扩散到连续区间3.1 问题如何转化为区间长度统计第二题的故事是一排 N 个牛棚每个牛棚要么有牛用 1 表示要么空着用 0 表示。某天晚上一些牛被感染了之后每个夜晚已经感染的牛会把疾病传染给相邻的牛。给定最终所有牛棚的状态问最初至少有多少头牛被感染才能经过若干夜晚变成这个状态。关键信息是所有最初感染的牛经历的夜晚数是同一个 r。你不能给甲算 3 晚、给乙算 5 晚。这个“同一个 r”是整道题的命门。先把最终状态里的连续 1 段全部提取出来。比如 1110011 可以分成两个段长度分别是 3 和 2。为什么可以分段因为 0 隔断了传播路径一段连续 1 只能由它内部的初始感染者产生不同段之间互不影响各自独立。那每段长度是 len 时需要多少头初始感染牛呢假设有一头初始感染牛经过 r 个夜晚它最多能覆盖的长度是 2r1初始自己占 1 格每夜向左右各扩 1 格r 夜后左右各 r 格加起来就是 12r。所以对于长度为 len 的连续 1 段在给定 r 的情况下最少需要的初始感染者数量是 ceil(len / (2r1))。也就是说用若干段长度为 2r1 的覆盖区间去铺满 len 个位置。但 r 不能乱取。如果 2r1 大于 len一头牛覆盖的范围会超出这段连续 1 的边界把旁边的 0 也感染那最终状态就不成立了。所以对于长度 len 的段允许的 r 必须满足 2r1 ≤ len即 r ≤ (len-1)/2。这个值取整后就是该段允许的最大半径。所有段共用一个 r因此全局允许的 r 上限是所有段各自最大半径里的最小值。3.2 枚举半径并计算最小初始感染数算法步骤非常清晰扫描字符串提取所有连续 1 段的长度。计算 Rmax它是每段 (len-1)/2 的最小值。对 r 0, 1, ..., Rmax 分别计算总初始感染数取最小值。计算总感染数时每段需要的初始牛数是 ceil(len / (2r1))。这可以用整数公式 (len 2r) / (2r 1) 计算避免浮点误差。#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; string s; cin N s; vectorint lens; int Rmax N; // 初始给个大值 for (int i 0; i N; ) { if (s[i] 0) { i; continue; } int j i; while (j N s[j] 1) j; int len j - i; lens.push_back(len); Rmax min(Rmax, (len - 1) / 2); i j; } ll ans N; // 上界每个 1 都作为初始感染者 for (int r 0; r Rmax; r) { ll cur 0; for (int len : lens) { cur (len 2LL * r) / (2LL * r 1); } ans min(ans, cur); } cout ans \n; return 0; }这里有个很漂亮的复杂度结论表面上 r 从 0 枚举到 Rmax每轮都要扫所有段像是 O(N × Rmax)。但因为每个段的长度都不小于 2r1段的个数 M 一定满足 M ≤ N / (2Rmax1)。所以总扫描量 M × (Rmax1) 是 O(N) 级别的。换句话说这题的枚举并不慢放心写。3.3 边界条件与容易忽略的细节第一r 的起始值。有的题描述里明确说了“至少经过一个夜晚”那 r 就要从 1 开始枚举如果题意允许 0 个夜晚初始状态就等于最终状态r0 也必须算进候选。稳妥的做法是题目怎么问就怎么来不确定时把 r0 和 r≥1 都算一遍取最小值因为多算一个并不影响正确性但要注意如果题意硬性要求 r≥1把 r0 的情况纳进来会有风险。我自己的习惯是读题时先确认 r 是否限定为正整数再决定枚举起点。第二连续 1 段不能跨越 0。很多新手会把 1110111 当成一整段其实中间 0 破坏了两侧的联系必须分成两段分别计算。第三Rmax 可能很小。比如 s 是 1001两段长度都是 1Rmax 是 0这时答案就是所有 1 都作为初始感染者因为每个点都独自感染没有任何传播发生。这种极端数据是最容易让人怀疑代码是不是写错的但其实是对的。第四整串全是 0。这种情况下没有连续 1 段lens 为空答案应该是 0。代码里要避免对空数组做计算时报错。4. 第三题 Farmer John Actually Farms排名约束与时间窗口4.1 把“恰好有 t_i 头牛比它高”翻译成排名条件第三题是我认为这套题里含金量最高的一道。故事大概是FJ 的 N 头奶牛初始高度是 h_i每天都会长高 a_i。FJ 想在某个未来的第 T 天检查牛群并且对每头牛 i 有一个要求恰好有 t_i 头牛比它高。问是否存在这样的正整数 T。这个“恰好有 t_i 头牛比它高”本质上是在描述 T 天时牛群的排名。如果一头牛上方恰好有 k 头牛比它更高那它在降序排序中应该处在第 k1 个位置如果几头牛高度相等它们互不比对方高所以它们上方比它们高的牛数量是一样的也就是它们的 t 值必须相同。先想清楚一个基本事实第 i 头牛第 T 天的高度是 h_i a_i × T这是关于 T 的一条直线。两条直线的大小关系最多只会在它们相等的那一刻改变一次。这意味着所有牛的相对排名不会频繁变化只会在一系列“交点时刻”发生切换。如果我们把这些交点时刻找出来那么在每两个相邻交点之间的时间段里所有牛的相对顺序是固定不变的。于是问题就变成把时间轴切成若干个区间在每个区间里任取一个整数 T检查牛群的排名是否满足 t_i 的条件。只要有一个区间里的某个整数 T 满足答案就是 YES。4.2 用候选时间点代替完整区间判断理论上需要枚举所有区间但实现上有个更简单的等价做法直接收集所有“可能改变排序”的时间点附近的整数作为候选 T逐个检查。为什么足够因为如果某个开区间 (L, R) 内存在满足条件的整数 T那么排序在这个开区间内不变区间内任意一个整数检查结果都一样如果区间内没有整数那唯一可能的整数就在端点附近而我们把端点附近的整数也收进候选就不会漏掉。对于任意两头牛 i 和 j如果 a_i ≠ a_j它们高度相等的时间是T (h_j - h_i) / (a_i - a_j)如果这个 T 是正数说明未来某个时刻两头牛会“相遇”相遇后谁高谁低反过来。把所有这样的正交点时间收集起来把每个交点时间附近的几个整数比如 floor(T)-2 到 floor(T)2都加入候选集合。最后再补上 T1 和一个超大的稳定时间比如 1e97然后逐个 check。这里要注意T1e97 用来表示“足够远以后”因为所有增速不同的牛在足够远以后排名只会由增长速率决定不会再改变。把一个大时间放进候选相当于固定了无限远处的排名状态。检查函数本身很简单给定 T算出每头牛的身高按身高降序排序然后从左到右记录“严格高于当前牛的牛的数量”再和每头牛的 t_i 对比。#include bits/stdc.h using namespace std; typedef long long ll; int N; vectorll h, a, t; bool check(ll T) { vectorpairll, int cow(N); for (int i 0; i N; i) { cow[i] {h[i] a[i] * T, i}; } sort(cow.rbegin(), cow.rend()); // 身高降序 int higher 0; for (int i 0; i N; i) { if (i 0 cow[i].first cow[i - 1].first) { higher i; // 当前牛严格低于前一头前面的 i 头都严格更高 } // 如果和上一头同高higher 不变因为同高的牛互不比对方高 if (higher ! t[cow[i].second]) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin N; h.resize(N); a.resize(N); t.resize(N); for (int i 0; i N; i) cin h[i]; for (int i 0; i N; i) cin a[i]; for (int i 0; i N; i) cin t[i]; vectorll cand; cand.push_back(1); cand.push_back(1000000007LL); for (int i 0; i N; i) { for (int j i 1; j N; j) { if (a[i] a[j]) continue; // 两条线平行永远不相交 // 交点 T (h[j] - h[i]) / (a[i] - a[j]) double inter 1.0 * (h[j] - h[i]) / (a[i] - a[j]); if (inter 0) { ll base (ll)floor(inter); for (ll k base - 2; k base 2; k) { if (k 1) cand.push_back(k); } } } } sort(cand.begin(), cand.end()); cand.erase(unique(cand.begin(), cand.end()), cand.end()); bool ok false; for (ll T : cand) { if (check(T)) { ok true; break; } } cout (ok ? YES : NO) \n; return 0; }这个做法的时间复杂度很宽松N 很小的情况下候选点数量有限每次 check 是 O(N log N)完全够用。如果 N 更大就需要用更精细的区间扫描法但青铜组没有必要。4.3 这题的思维陷阱与代码细节这题最容易错的地方是把“严格比它高”和“非严格排名”混在一起。如果几头牛高度相等它们各自上方“严格更高”的数量完全一样所以 t 值必须相等但它们在降序排序里的下标却不同你必须用“严格更高数量”去对 t而不是用“排序位置”。另外double 计算交点会带来精度问题。在实际比赛中我建议用分数形式或者 long double 来做候选点因为你只需要在交点附近取整数精度稍微差一点问题不大但如果差太多就可能漏掉正确的候选。最稳的办法是把每个交点附近多取几个整数覆盖掉浮点误差。关于 T 的取值题目问的是正整数所以候选 T 从 1 开始。如果题目改成“非负整数”那 T0 也要纳入。这种细节直接决定答案边界读题时一定要盯死。4.4 顺带聊聊经典题三值排序之所以要在这里提三值排序是因为它和第三题一样都在考察“排序里的结构”第三题研究的是“排名约束随时间变化”三值排序研究的是“有限几类元素如何用最少交换次数排好”。这是USACO题库里非常经典的一道题很多同学在青铜组后期或者升白银前的训练里都会遇到。题目很朴素给定一个只包含 1、2、3 的序列每次可以交换任意两个位置的数字问最少多少次交换能让整个序列变成非递减序列。思路是把最终状态先确定下来统计 1、2、3 各有多少个那么排序后第一段全是 1第二段全是 2第三段全是 3。然后扫描原序列记录每个“目标段”里出现了多少种“错误数字”。比如第一段里出现了 x 个 2第二段里出现了 y 个 1这两个错位数字可以直接交换一次各归各位。所以先处理所有两两直接互换就能消掉的配对。剩下的错位数字会形成长度为 3 的循环比如第一段还有 2、第二段还有 3、第三段还有 1这时候三个数字需要两次交换才能全部归位。累计答案即可。int cnt[4] {0}; for (int v : a) cnt[v]; int bad[4][4] {0}; int pos 0; for (int seg 1; seg 3; seg) { for (int k 0; k cnt[seg]; k, pos) { bad[seg][a[pos]]; } } int ans 0; for (int i 1; i 3; i) { for (int j i 1; j 3; j) { int x min(bad[i][j], bad[j][i]); ans x; bad[i][j] - x; bad[j][i] - x; } } int remain 0; for (int i 1; i 3; i) for (int j 1; j 3; j) if (i ! j) remain bad[i][j]; ans remain / 3 * 2; cout ans \n;第一次交换消除的两两错位每次交换让两个数字都回到正确段第二次处理循环错位时每个循环由三个错位数字组成需要两次交换。这个“先消配对再处理环”的思路其实和第三题里“先观察结构再分类处理”的思维方式一脉相承。5. 青铜组常见失误与备考FAQ5.1 四个最容易翻车的地方第一个是数据类型。青铜组数据量不大但数值可能很大。第三题里 h_i 加上 a_i × T很容易超过 2^31不用 long long 必挂。USACO 的题目不会专门提醒你开 long long这属于基本功。第二个是“大于”和“大于等于”的边界。第一题已经演示过了h[i] lo 和 h[i] lo 是两种完全不同的规则。这种细节只能靠手推样例时逐行核对写代码时尤其要警惕。第三个是只看样例不看极端情况。很多新手样例过了就提交结果挂在这种数据上全是 0、全是 1、只有一个 1、所有牛增速相同、所有牛初始身高相同。比赛前可以在脑子里快速过一遍这些极端输入。第四个是枚举范围没想清楚。第三题如果你直接枚举 T 从 1 到 1e9肯定超时但如果你不枚举候选点又可能漏答案。青铜组的题往往不需要很复杂的优化但需要你把“枚举什么东西”想清楚。5.2 常见问题速查问题原因处理方式第一题输出比预期大可能把等于时也算了进食检查 h[i] lo 是否严格大于第二题答案偏大每段单独取半径而不是统一半径保证所有段共用同一个 r第二题全是 0 时出错没有处理空区间lens 为空时直接输出 0第三题 YES 漏判候选 T 没覆盖到整数区间交点附近多取几个整数加上特大稳定时间第三题把排名搞错混同了并列高度和严格高于用“严格更高数量”去匹配 t_i总溢出int 不够用所有涉及高度和天数的变量用 long long5.3 从这场真题出发下一步怎么规划如果你能独立把这套题的三道题都做出来青铜组的核心能力基本就达标了。接下来往白银组走重点补两件事。第一是时间复杂度分析。青铜组很多题暴力都能过但白银组就不行了你要开始习惯在写代码前先算一下 N 最大是多少、算法复杂度是多少、会不会超时。第二是掌握更系统的算法工具。白银组常考的二分答案、前缀和、简单的图遍历、贪心证明都是青铜组题目的自然延伸。比如第二题感染追踪如果你把枚举半径改成二分查找再套一层更复杂的图论背景就是典型的白银组升级套路。最后说点我自己的体会这套题我前前后后带人刷过好几遍每次都会有新发现。第一次刷的时候我在第一题上栽了跟头因为没注意身高会超过 int 范围第二次刷的时候我在第二题纠结了很久总觉得每个感染区间应该有自己的半径后来才想明白“统一半径”才是题意第三题反而是我后来觉得最有收获的一道因为“候选时间点”这个技巧在后面的月赛里也经常用到学会了它很多带时间参数的问题都有了突破口。如果你正在准备USACO青铜组我的建议很简单不要急着刷难题先把这种中等难度的月赛真题吃透每道题都做到能手写复现再追求速度和拓展。USACO的晋级从来不是靠某个难题突然开窍而是靠一道道真题积累起来的手感和判断力。这场 2023 年 12 月的青铜组就是一个非常不错的起点。