USACO 2022年的OPENUS Open是那个赛季的最后一场月赛青铜组三道题分别是 Photoshoot、Counting Liars、Alchemy。这套题可以说把青铜组最典型的几种考察方式都凑齐了一题考“枚举加递推”一题考“把文字描述翻译成区间统计”还有一题考“依赖关系下的递归搜索”。很多选手平时刷题不少但一到月赛就卡住问题往往就出在不会把故事题还原成算法模型。这篇不打算照着官方题解念一遍而是按我平时带人的思路把每道题从读题、建模、写代码到踩坑的完整过程捋一遍。看完你应该能明白青铜组真正需要的不是高深算法而是把问题拆小的能力。1. 2022 OPEN青铜组三题考了什么1.1 题目与考点总览先说结论2022 OPEN青铜组整体难度不算高但区分度很足。三题的核心考点分别落在枚举、区间覆盖统计和递归依赖处理都是青铜组最高频的几类模型。题号题目核心问题主要方法数据范围1Photoshoot已知相邻两数之和还原一个排列枚举第一个数 递推 校验N ≤ 10002Counting Liars选一个位置让说真话的牛最多枚举候选位置或排序后二分统计N ≤ 10003Alchemy用配方依赖关系最大化某种产物的数量递归DFS或反复模拟合成N ≤ 100从这三道题能明显看出USACO青铜组的出题套路数据范围普遍很小N基本都在1000以内这意味着你不需要掌握什么高级数据结构O(N^2)甚至O(N^3)的算法往往都够用。真正的难点从来不是算法本身而是你能不能把题目里花里胡哨的农场故事翻译成一个明确的数学或图论模型。1.2 这套题的难度梯度和时间分配虽然三题都是青铜级别但体感难度是逐题上升的。Photoshoot基本属于送分题只要想到枚举a[1]十分钟之内就能写完。Counting Liars的难点在读题题面里“G”和“L”的判定方向非常容易搞反一旦方向错了样例可能都过不了。Alchemy相对最麻烦因为你要处理的是多个配方之间的共享原料关系这里既考验递归能力也考验代码的鲁棒性。我给学生的建议是第一题控制在20分钟以内第二题不要超过40分钟第三题哪怕花一个小时也值得。青铜组三道题的分数权重相同所以千万不要在第一题上反复纠结优化先把能拿的分全部拿到再说。实际比赛中我看到太多人栽在第二题的方向判断上或者死在第三题忘了回溯导致死循环这些都是完全可以规避的。2. Photoshoot从相邻和中还原排列2.1 题目到底在说什么Photoshoot的题面包装得很简单农场主有N头奶牛编号分别是1到N每头牛的编号都不重复。Bessie记得的是相邻两头牛编号之和并且把这个信息记成了一个长度为N-1的数组b也就是说b[i] a[i] a[i1]。现在给你这个数组b你需要还原出原本的排列a并且要求字典序最小。题目给的样例是这样的N 5 b [4, 6, 7, 6]如果排列a [3, 1, 5, 2, 4]那么相邻和就是314156527246正好对应b。这个样例有两个合法解但3开头的是字典序最小的所以输出它。有一个点需要特别注意这里还原的对象是1到N的一个排列也就是说每个数字必须恰好出现一次。很多新手容易忽略这一点只验证了递推出来的数字范围却没有验证“不重复”结果就会在隐藏数据上翻车。2.2 为什么枚举第一个数就够了这道题最核心的观察是整个序列是“牵一发而动全身”的。如果你知道了a[1]那么a[2]可以直接算出来a[2] b[1] - a[1]知道了a[2]a[3]也能算出来a[3] b[2] - a[2]以此类推整条序列都会被唯一确定。所以根本不需要搜索整个排列空间只需要枚举a[1]等于多少。a[1]的取值范围只有1到N最多1000种可能每次从a[1]推到a[N]只需要O(N)的时间。总复杂度O(N^2)对于N≤1000来说非常轻松。这个思想在竞赛里叫“由第一个变量锁定整条链”本质上是一种递推。它之所以成立是因为题目给出的相邻依赖关系是一个没有分支的线性链。类似的手法在USACO其他题目里也经常出现比如知道差分数组还原原数组或者知道前缀和数组还原原序列。2.3 参考代码与代码要点下面是一份完整的C实现使用文件输入输出文件名为photoshoot.in和photoshoot.out#include bits/stdc.h using namespace std; int main() { ifstream fin(photoshoot.in); ofstream fout(photoshoot.out); int n; fin n; vectorint b(n 1); for (int i 1; i n - 1; i) { fin b[i]; } for (int first 1; first n; first) { vectorint a(n 1); vectorbool used(n 1, false); a[1] first; used[first] true; bool ok true; for (int i 1; i n - 1; i) { int nxt b[i] - a[i]; if (nxt 1 || nxt n || used[nxt]) { ok false; break; } a[i 1] nxt; used[nxt] true; } if (ok) { for (int i 1; i n; i) { fout a[i] (i n ? \n : ); } break; } } return 0; }这段代码有三个关键点。第一每次枚举新的first时都要重新声明used数组保证上一轮留下的标记不会干扰这一轮。第二在递推的过程中nxt不仅要检查是否落在1到N的范围内还要检查有没有被用过这两个条件缺一不可。第三一旦某一步发现不合法要立刻break掉内层循环不要继续往下推否则会把不合法的序列当成合法序列输出。2.4 这题最容易踩的坑Photoshoot虽然简单但我在实际带学生的过程中发现几乎有一半的人会在细节上出错。最常见的错误是漏掉对“重复使用”的检查只判断nxt是否在1到N之间结果跑出来的序列里有重复数字但是在小样例上很难看出来。第二个常见错误是把递推公式写成a[i] - b[i]符号方向反了。第三个错误是输出格式少了一个空格或者换行导致Presentation Error。另外提醒一点题目保证一定有解所以代码里不需要处理“找不到合法排列”的情况但如果你自己写对拍程序建议加上一个兜底输出方便调试。你可以在本地多试几组随机生成的排列用程序生成b数组再跑你的还原代码看看能不能还原出原排列。这种对拍方式对青铜组题目的练习非常有效。3. Counting Liars把说真话变成区间覆盖3.1 题面翻译与建模思路Counting Liars这个题名翻译过来是“数说谎者”但题目里并没有直接告诉你谁在说谎。真实情况是有N头奶牛每头奶牛都会对干草堆的位置做一个陈述。陈述分两种字母G加一个整数x表示“干草堆的位置至少是x”也就是说真实位置p满足p ≥ x字母L加一个整数x表示“干草堆的位置至多是x”也就是说真实位置p满足p ≤ x。FJ不知道哪里才是真正的干草堆位置但他想知道如果自己选一个位置放干草堆最少会有多少头牛在说谎。换句话说要找到一个位置p让尽可能多的牛的陈述成立然后用总量减去这个最大真话数就是最少说谎数。从数学上看每头牛的陈述其实对应一个“半无限区间”G x 对应区间[x, ∞)L x 对应区间(-∞, x]。一头牛说真话当且仅当你选择的那个位置p落在它对应的区间里。于是问题就变成了在数轴上找一个点让它被尽可能多的区间覆盖。这就是非常经典的区间覆盖统计问题。3.2 候选位置为什么只需要看整数点一个新手容易纠结的点是干草堆的位置是不是一定要是整数p能不能落在两个陈述点之间的小数位置答案是不需要。因为每头牛的真假判断只会在某个x值处发生突变。举例来说一头说G 3的牛只要p≥3就说真话那么p从2.9变到3.0时状态会改变但在3.0之后的任何一个数无论整数还是小数对它来说没区别。所以你真要考虑的决策点就是所有奶牛陈述里出现过的那些x值。枚举这些x就足够找到最优解。我建议把所有候选位置放进一个set里因为set既能去重又能让候选点有序。当然如果你只做O(N^2)枚举用vector然后手动去重也完全没问题。3.3 O(N²)枚举做法与完整代码这道题的N最大值是1000所以最简单的做法是两层循环枚举外层枚举候选位置内层枚举所有牛统计在当前位置下有多少头牛说真话。总计算量最多100万次运行时间不到0.1秒。下面是完整代码文件名使用liars.in和liars.out具体文件名以你OJ上的要求为准#include bits/stdc.h using namespace std; int main() { ifstream fin(liars.in); ofstream fout(liars.out); int n; fin n; vectorpairchar, int cows(n); setint candidates; for (int i 0; i n; i) { fin cows[i].first cows[i].second; candidates.insert(cows[i].second); } int best 0; for (int pos : candidates) { int truth 0; for (auto c : cows) { char ch c.first; int x c.second; if (ch G x pos) truth; if (ch L x pos) truth; } best max(best, truth); } fout n - best \n; return 0; }注意判定条件的方向。字母G表示“至少是x”所以真实位置pos必须比x大也就是x ≤ pos时真话字母L表示“至多是x”所以真实位置pos必须比x小也就是x ≥ pos时真话。这个方向非常容易记反我自己第一次做这道题时就是在这里卡了十分钟。3.4 排序加二分的进阶做法如果你的目标不只是过青铜组而是为后面的Silver甚至Gold打基础我建议顺便把排序加二分的做法掌握一下。这个方法的核心是把G和L两类陈述分别装进两个数组分别排序。对于给定的候选位置posG类陈述中说真话的数量等于Gs里小于等于pos的个数也就是upper_bound(Gs.begin(), Gs.end(), pos) - Gs.begin()L类陈述中说真话的数量等于Ls里大于等于pos的个数也就是Ls.size() - (lower_bound(Ls.begin(), Ls.end(), pos) - Ls.begin())。把这两个数相加就是当前位置下的真话总数。这样处理每个候选位置只需要O(log N)的时间总体复杂度O(N log N)。代码片段如下vectorint Gs, Ls; for (auto c : cows) { if (c.first G) Gs.push_back(c.second); else Ls.push_back(c.second); } sort(Gs.begin(), Gs.end()); sort(Ls.begin(), Ls.end()); int best 0; for (int pos : candidates) { int truthG upper_bound(Gs.begin(), Gs.end(), pos) - Gs.begin(); int truthL Ls.size() - (lower_bound(Ls.begin(), Ls.end(), pos) - Ls.begin()); best max(best, truthG truthL); } cout n - best \n;青铜组没要求你写出这个优化版本但理解这个思路对你以后处理区间覆盖类问题非常有帮助。尤其是“upper_bound找小于等于”“lower_bound找大于等于”这种边界技巧在后续比赛中会反复用到。4. Alchemy配方依赖与最大化产量4.1 题目模型与依赖关系Alchemy的题面同样是个农场故事有N种材料编号从1到N材料1是你最终想要的药水。初始时每种材料都有一定的库存然后你有一些配方每个配方描述的是消耗某些原料各一份就能生产出新的一份产物。目标很简单就是尽可能多地制作材料1。这题的难点不是模拟本身而是理解配方之间可能存在“链式依赖”。比如你想做材料1但配方需要材料2和材料3而材料2的库存不足你又需要用更底层的材料4和材料5合成材料2。这样一来整个合成关系就构成了一张有向图甚至可能是一棵复杂的树。解决这类问题有两个常用视角。视角一是顺着做不断尝试所有配方只要某个配方需要的一整套原料都有库存就立刻执行一次消耗原料增加产物直到再也无法进行任何合成为止最后输出材料1的库存。视角二是倒着想每次判断“我现在还能不能再做出一份材料1”递归地去检查原料是否可得能得到就真消耗得不到就回退。4.2 用DFS判断能否再造一份产物我推荐用递归搜索的方式来实现因为它在逻辑上更贴近“目标导向”的思考方式。定义函数dfs(x)它的含义是尝试从当前库存中拿出一份材料x。如果库存里本来就有x直接消耗一份库存并返回true如果库存里没有就看有没有能合成x的配方有的话递归地尝试让每一种原料都“拿到一份”。万一某一种原料拿不到就说明这条路走不通需要把这次递归尝试中消耗掉的库存全部恢复然后换下一个配方继续尝试。下面是完整的参考实现#include bits/stdc.h using namespace std; struct Recipe { int product; vectorint ingredients; }; int n; vectorint cnt; vectorRecipe recipes; bool dfs(int x) { if (cnt[x] 0) { cnt[x]--; return true; } for (auto r : recipes) { if (r.product ! x) continue; vectorint backup cnt; bool ok true; for (int ing : r.ingredients) { if (!dfs(ing)) { ok false; break; } } if (ok) return true; cnt backup; } return false; } int main() { ifstream fin(alchemy.in); ofstream fout(alchemy.out); fin n; cnt.assign(n 1, 0); for (int i 1; i n; i) fin cnt[i]; int m; fin m; for (int i 0; i m; i) { int p, k; fin p k; Recipe r; r.product p; r.ingredients.resize(k); for (int j 0; j k; j) { fin r.ingredients[j]; } recipes.push_back(r); } int ans 0; while (dfs(1)) { ans; } fout ans \n; return 0; }这段代码里有一个非常关键的机制变量backup保存了递归尝试开始前的完整库存一旦某个配方路径走不通就通过cnt backup把库存恢复到原来的状态。没有这一步前面分支消耗掉的原料就会污染后续分支的判断导致算法产生错误结果。我在代码里采用的输入约定是第一行N第二行N个初始库存第三行M接下来M行每行第一个数是产物编号第二个数k表示这个配方需要k种原料随后跟着k个原料编号。如果你在别的OJ上遇到这题输入格式可能有细微差异核心的递归回退逻辑原理是一样的只需要调整解析部分。4.3 反复扫描配方的模拟版本如果你觉得递归版本理解起来有负担还有一个更直观的模拟写法不停扫描所有配方只要某个配方的全部原料库存都至少是1就立刻执行合成然后从头重新扫描直到没法再合成为止。最后cnt[1]就是答案。这种模拟写法的优点是代码短缺点是它隐含了一个假设任何一次可行合成都不会影响最终最优产量。在很多依赖图是树形结构的题目里这个假设成立但如果配方分支复杂选择哪个配方先执行可能会影响后续产量。因此我仍然建议用DFS版本至少它能通过回退机制处理分支选择。另外题目在设计时通常保证了配方依赖不会成环而且材料1不会作为其他配方的原料。如果题目出现环比如合成A需要B合成B又需要A那dfs就会无限递归下去。稳妥的做法是在递归函数里加一个栈标记检测到环就返回false。4.4 处理配方依赖的三个提醒第一个提醒是回溯别偷懒。有些同学觉得只要原料不够就返回false没必要保存和恢复库存但这样一旦递归深了几层前面成功消耗的原料就全部变成“白消耗”最终结果会偏大。回溯是DFS处理资源分配问题的生命线。第二个提醒是小心重复使用同一种原料。一个配方可能消耗两种原料而这两种原料可能又共享同一个更低级原料。递归搜索时如果你不仔细跟踪库存很容易出现“把同一份低级原料算成两份”的错觉。DFS每次消耗都真实修改cnt数组能避免这种问题。第三个提醒是复杂度控制。N只有100初始库存总和也不大所以每次成功生产一份材料1都会消耗一些原料循环次数不会太多。但如果你发现递归搜索特别慢可以先判断是否存在环也可以给dfs增加一个记忆化对某个x已经确认过“当前库存下无法得到”那就不需要反复尝试同一个x。5. 从2022 OPEN看青铜组冲刺建议5.1 青铜组真正考的是建模能力把三道题放在一起看你会发现一个规律代码本身都很短核心逻辑没有超过三十行。Photoshoot是枚举一个变量后递推Counting Liars是枚举位置后统计Alchemy是递归搜索加回溯。这些都算不上什么算法但它们有一个共同点需要你先在脑子里完成建模把题目描述变成一个明确的数学结构。这也是青铜组最劝退新人的地方。很多选手不是不会写代码而是读题之后不知道从何下手。比如Counting Liars如果你只是盯着“说谎者”这三个字很容易往逻辑推理的方向想想半天也不知道怎么处理。但一旦你意识到每头牛的陈述都是一个半无限区间问题立刻变成了“求被覆盖最多的点”那就简单多了。所以我建议你在刷题时不要急着打开代码编辑器。先把题面用自己的话复述一遍然后写下这个问题的输入是什么、输出是什么、抽象成什么模型。等模型清楚了代码往往水到渠成。5.2 针对这三类题型的训练方法如果你现在正在为下一次月赛准备可以按照今天这套题的分类去做针对性训练。排列枚举类题目重点练“确定第一个变量后推导整条链”的思路。USACO历年青铜组里大量题目都可以用这种思路解决比如已知前缀关系还原原数组、已知相邻差还原排列等。每道题你都试着一口气写出O(N²)的版本再想有没有更快的写法。区间统计类题目重点练“把文字约束变成区间”的建模能力。你可以找一些Silver级别的简单区间题把数据范围改成1000用O(N²)去做体会枚举和统计的过程。等你觉得熟练了再学习排序加二分的优化版本。递归依赖类题目重点练DFS和回溯。不需要做太难的题树的遍历、括号匹配、数独填数这类基础的DFS题目就够用了。关键是养成一个习惯每次递归进入下一层之前先想清楚这个分支失败之后现场的哪些状态需要恢复。5.3 考场上的时间管理和自测习惯青铜组比赛没有想象中那么紧张四个小时做三道题绰绰有余。但很多选手还是会在某一题上卡到崩溃。我的建议是拿到题面后先把三道题全部读一遍按难度排个序先做最确定的送分题。每道题想不出解法的时间不要超过45分钟超过就先写一个暴力版本能拿部分分也总比空着强。另外比赛结束前一定要留出时间自测边界数据。以今天这三道题为例Photoshoot你要测N2的情况因为此时b数组只有一个数最容易暴露下标错误Counting Liars你要测所有牛都朝一个方向说话的情况Alchemy你要测没有任何配方可用的情况。这些边界数据能帮你发现很多隐藏bug。文件读写也值得单独提一句。USACO要求每道题用对应的文件输入输出经常有人把文件名拼错或者忘记关闭文件导致输出为空。建议你在本地维护一个固定的模板考试时只需要替换题目名能省去很多不必要的失误。最后分享一个我自己坚持了很多年的习惯每次月赛结束不管成绩如何我会把当次的三道题按“枚举、统计、递归、图论”之类的标签归档并在旁边用一句话写下核心思路。下一场月赛前先花半小时翻一遍这个归档比盲目刷十道新题都管用。2022 OPEN这套青铜题如果你能独立把三道题的建模过程都想明白那你已经有能力在下一场月赛里稳定拿满分了。
USACO 2022 OPEN青铜组全解析：枚举、区间统计与递归建模
USACO 2022年的OPENUS Open是那个赛季的最后一场月赛青铜组三道题分别是 Photoshoot、Counting Liars、Alchemy。这套题可以说把青铜组最典型的几种考察方式都凑齐了一题考“枚举加递推”一题考“把文字描述翻译成区间统计”还有一题考“依赖关系下的递归搜索”。很多选手平时刷题不少但一到月赛就卡住问题往往就出在不会把故事题还原成算法模型。这篇不打算照着官方题解念一遍而是按我平时带人的思路把每道题从读题、建模、写代码到踩坑的完整过程捋一遍。看完你应该能明白青铜组真正需要的不是高深算法而是把问题拆小的能力。1. 2022 OPEN青铜组三题考了什么1.1 题目与考点总览先说结论2022 OPEN青铜组整体难度不算高但区分度很足。三题的核心考点分别落在枚举、区间覆盖统计和递归依赖处理都是青铜组最高频的几类模型。题号题目核心问题主要方法数据范围1Photoshoot已知相邻两数之和还原一个排列枚举第一个数 递推 校验N ≤ 10002Counting Liars选一个位置让说真话的牛最多枚举候选位置或排序后二分统计N ≤ 10003Alchemy用配方依赖关系最大化某种产物的数量递归DFS或反复模拟合成N ≤ 100从这三道题能明显看出USACO青铜组的出题套路数据范围普遍很小N基本都在1000以内这意味着你不需要掌握什么高级数据结构O(N^2)甚至O(N^3)的算法往往都够用。真正的难点从来不是算法本身而是你能不能把题目里花里胡哨的农场故事翻译成一个明确的数学或图论模型。1.2 这套题的难度梯度和时间分配虽然三题都是青铜级别但体感难度是逐题上升的。Photoshoot基本属于送分题只要想到枚举a[1]十分钟之内就能写完。Counting Liars的难点在读题题面里“G”和“L”的判定方向非常容易搞反一旦方向错了样例可能都过不了。Alchemy相对最麻烦因为你要处理的是多个配方之间的共享原料关系这里既考验递归能力也考验代码的鲁棒性。我给学生的建议是第一题控制在20分钟以内第二题不要超过40分钟第三题哪怕花一个小时也值得。青铜组三道题的分数权重相同所以千万不要在第一题上反复纠结优化先把能拿的分全部拿到再说。实际比赛中我看到太多人栽在第二题的方向判断上或者死在第三题忘了回溯导致死循环这些都是完全可以规避的。2. Photoshoot从相邻和中还原排列2.1 题目到底在说什么Photoshoot的题面包装得很简单农场主有N头奶牛编号分别是1到N每头牛的编号都不重复。Bessie记得的是相邻两头牛编号之和并且把这个信息记成了一个长度为N-1的数组b也就是说b[i] a[i] a[i1]。现在给你这个数组b你需要还原出原本的排列a并且要求字典序最小。题目给的样例是这样的N 5 b [4, 6, 7, 6]如果排列a [3, 1, 5, 2, 4]那么相邻和就是314156527246正好对应b。这个样例有两个合法解但3开头的是字典序最小的所以输出它。有一个点需要特别注意这里还原的对象是1到N的一个排列也就是说每个数字必须恰好出现一次。很多新手容易忽略这一点只验证了递推出来的数字范围却没有验证“不重复”结果就会在隐藏数据上翻车。2.2 为什么枚举第一个数就够了这道题最核心的观察是整个序列是“牵一发而动全身”的。如果你知道了a[1]那么a[2]可以直接算出来a[2] b[1] - a[1]知道了a[2]a[3]也能算出来a[3] b[2] - a[2]以此类推整条序列都会被唯一确定。所以根本不需要搜索整个排列空间只需要枚举a[1]等于多少。a[1]的取值范围只有1到N最多1000种可能每次从a[1]推到a[N]只需要O(N)的时间。总复杂度O(N^2)对于N≤1000来说非常轻松。这个思想在竞赛里叫“由第一个变量锁定整条链”本质上是一种递推。它之所以成立是因为题目给出的相邻依赖关系是一个没有分支的线性链。类似的手法在USACO其他题目里也经常出现比如知道差分数组还原原数组或者知道前缀和数组还原原序列。2.3 参考代码与代码要点下面是一份完整的C实现使用文件输入输出文件名为photoshoot.in和photoshoot.out#include bits/stdc.h using namespace std; int main() { ifstream fin(photoshoot.in); ofstream fout(photoshoot.out); int n; fin n; vectorint b(n 1); for (int i 1; i n - 1; i) { fin b[i]; } for (int first 1; first n; first) { vectorint a(n 1); vectorbool used(n 1, false); a[1] first; used[first] true; bool ok true; for (int i 1; i n - 1; i) { int nxt b[i] - a[i]; if (nxt 1 || nxt n || used[nxt]) { ok false; break; } a[i 1] nxt; used[nxt] true; } if (ok) { for (int i 1; i n; i) { fout a[i] (i n ? \n : ); } break; } } return 0; }这段代码有三个关键点。第一每次枚举新的first时都要重新声明used数组保证上一轮留下的标记不会干扰这一轮。第二在递推的过程中nxt不仅要检查是否落在1到N的范围内还要检查有没有被用过这两个条件缺一不可。第三一旦某一步发现不合法要立刻break掉内层循环不要继续往下推否则会把不合法的序列当成合法序列输出。2.4 这题最容易踩的坑Photoshoot虽然简单但我在实际带学生的过程中发现几乎有一半的人会在细节上出错。最常见的错误是漏掉对“重复使用”的检查只判断nxt是否在1到N之间结果跑出来的序列里有重复数字但是在小样例上很难看出来。第二个常见错误是把递推公式写成a[i] - b[i]符号方向反了。第三个错误是输出格式少了一个空格或者换行导致Presentation Error。另外提醒一点题目保证一定有解所以代码里不需要处理“找不到合法排列”的情况但如果你自己写对拍程序建议加上一个兜底输出方便调试。你可以在本地多试几组随机生成的排列用程序生成b数组再跑你的还原代码看看能不能还原出原排列。这种对拍方式对青铜组题目的练习非常有效。3. Counting Liars把说真话变成区间覆盖3.1 题面翻译与建模思路Counting Liars这个题名翻译过来是“数说谎者”但题目里并没有直接告诉你谁在说谎。真实情况是有N头奶牛每头奶牛都会对干草堆的位置做一个陈述。陈述分两种字母G加一个整数x表示“干草堆的位置至少是x”也就是说真实位置p满足p ≥ x字母L加一个整数x表示“干草堆的位置至多是x”也就是说真实位置p满足p ≤ x。FJ不知道哪里才是真正的干草堆位置但他想知道如果自己选一个位置放干草堆最少会有多少头牛在说谎。换句话说要找到一个位置p让尽可能多的牛的陈述成立然后用总量减去这个最大真话数就是最少说谎数。从数学上看每头牛的陈述其实对应一个“半无限区间”G x 对应区间[x, ∞)L x 对应区间(-∞, x]。一头牛说真话当且仅当你选择的那个位置p落在它对应的区间里。于是问题就变成了在数轴上找一个点让它被尽可能多的区间覆盖。这就是非常经典的区间覆盖统计问题。3.2 候选位置为什么只需要看整数点一个新手容易纠结的点是干草堆的位置是不是一定要是整数p能不能落在两个陈述点之间的小数位置答案是不需要。因为每头牛的真假判断只会在某个x值处发生突变。举例来说一头说G 3的牛只要p≥3就说真话那么p从2.9变到3.0时状态会改变但在3.0之后的任何一个数无论整数还是小数对它来说没区别。所以你真要考虑的决策点就是所有奶牛陈述里出现过的那些x值。枚举这些x就足够找到最优解。我建议把所有候选位置放进一个set里因为set既能去重又能让候选点有序。当然如果你只做O(N^2)枚举用vector然后手动去重也完全没问题。3.3 O(N²)枚举做法与完整代码这道题的N最大值是1000所以最简单的做法是两层循环枚举外层枚举候选位置内层枚举所有牛统计在当前位置下有多少头牛说真话。总计算量最多100万次运行时间不到0.1秒。下面是完整代码文件名使用liars.in和liars.out具体文件名以你OJ上的要求为准#include bits/stdc.h using namespace std; int main() { ifstream fin(liars.in); ofstream fout(liars.out); int n; fin n; vectorpairchar, int cows(n); setint candidates; for (int i 0; i n; i) { fin cows[i].first cows[i].second; candidates.insert(cows[i].second); } int best 0; for (int pos : candidates) { int truth 0; for (auto c : cows) { char ch c.first; int x c.second; if (ch G x pos) truth; if (ch L x pos) truth; } best max(best, truth); } fout n - best \n; return 0; }注意判定条件的方向。字母G表示“至少是x”所以真实位置pos必须比x大也就是x ≤ pos时真话字母L表示“至多是x”所以真实位置pos必须比x小也就是x ≥ pos时真话。这个方向非常容易记反我自己第一次做这道题时就是在这里卡了十分钟。3.4 排序加二分的进阶做法如果你的目标不只是过青铜组而是为后面的Silver甚至Gold打基础我建议顺便把排序加二分的做法掌握一下。这个方法的核心是把G和L两类陈述分别装进两个数组分别排序。对于给定的候选位置posG类陈述中说真话的数量等于Gs里小于等于pos的个数也就是upper_bound(Gs.begin(), Gs.end(), pos) - Gs.begin()L类陈述中说真话的数量等于Ls里大于等于pos的个数也就是Ls.size() - (lower_bound(Ls.begin(), Ls.end(), pos) - Ls.begin())。把这两个数相加就是当前位置下的真话总数。这样处理每个候选位置只需要O(log N)的时间总体复杂度O(N log N)。代码片段如下vectorint Gs, Ls; for (auto c : cows) { if (c.first G) Gs.push_back(c.second); else Ls.push_back(c.second); } sort(Gs.begin(), Gs.end()); sort(Ls.begin(), Ls.end()); int best 0; for (int pos : candidates) { int truthG upper_bound(Gs.begin(), Gs.end(), pos) - Gs.begin(); int truthL Ls.size() - (lower_bound(Ls.begin(), Ls.end(), pos) - Ls.begin()); best max(best, truthG truthL); } cout n - best \n;青铜组没要求你写出这个优化版本但理解这个思路对你以后处理区间覆盖类问题非常有帮助。尤其是“upper_bound找小于等于”“lower_bound找大于等于”这种边界技巧在后续比赛中会反复用到。4. Alchemy配方依赖与最大化产量4.1 题目模型与依赖关系Alchemy的题面同样是个农场故事有N种材料编号从1到N材料1是你最终想要的药水。初始时每种材料都有一定的库存然后你有一些配方每个配方描述的是消耗某些原料各一份就能生产出新的一份产物。目标很简单就是尽可能多地制作材料1。这题的难点不是模拟本身而是理解配方之间可能存在“链式依赖”。比如你想做材料1但配方需要材料2和材料3而材料2的库存不足你又需要用更底层的材料4和材料5合成材料2。这样一来整个合成关系就构成了一张有向图甚至可能是一棵复杂的树。解决这类问题有两个常用视角。视角一是顺着做不断尝试所有配方只要某个配方需要的一整套原料都有库存就立刻执行一次消耗原料增加产物直到再也无法进行任何合成为止最后输出材料1的库存。视角二是倒着想每次判断“我现在还能不能再做出一份材料1”递归地去检查原料是否可得能得到就真消耗得不到就回退。4.2 用DFS判断能否再造一份产物我推荐用递归搜索的方式来实现因为它在逻辑上更贴近“目标导向”的思考方式。定义函数dfs(x)它的含义是尝试从当前库存中拿出一份材料x。如果库存里本来就有x直接消耗一份库存并返回true如果库存里没有就看有没有能合成x的配方有的话递归地尝试让每一种原料都“拿到一份”。万一某一种原料拿不到就说明这条路走不通需要把这次递归尝试中消耗掉的库存全部恢复然后换下一个配方继续尝试。下面是完整的参考实现#include bits/stdc.h using namespace std; struct Recipe { int product; vectorint ingredients; }; int n; vectorint cnt; vectorRecipe recipes; bool dfs(int x) { if (cnt[x] 0) { cnt[x]--; return true; } for (auto r : recipes) { if (r.product ! x) continue; vectorint backup cnt; bool ok true; for (int ing : r.ingredients) { if (!dfs(ing)) { ok false; break; } } if (ok) return true; cnt backup; } return false; } int main() { ifstream fin(alchemy.in); ofstream fout(alchemy.out); fin n; cnt.assign(n 1, 0); for (int i 1; i n; i) fin cnt[i]; int m; fin m; for (int i 0; i m; i) { int p, k; fin p k; Recipe r; r.product p; r.ingredients.resize(k); for (int j 0; j k; j) { fin r.ingredients[j]; } recipes.push_back(r); } int ans 0; while (dfs(1)) { ans; } fout ans \n; return 0; }这段代码里有一个非常关键的机制变量backup保存了递归尝试开始前的完整库存一旦某个配方路径走不通就通过cnt backup把库存恢复到原来的状态。没有这一步前面分支消耗掉的原料就会污染后续分支的判断导致算法产生错误结果。我在代码里采用的输入约定是第一行N第二行N个初始库存第三行M接下来M行每行第一个数是产物编号第二个数k表示这个配方需要k种原料随后跟着k个原料编号。如果你在别的OJ上遇到这题输入格式可能有细微差异核心的递归回退逻辑原理是一样的只需要调整解析部分。4.3 反复扫描配方的模拟版本如果你觉得递归版本理解起来有负担还有一个更直观的模拟写法不停扫描所有配方只要某个配方的全部原料库存都至少是1就立刻执行合成然后从头重新扫描直到没法再合成为止。最后cnt[1]就是答案。这种模拟写法的优点是代码短缺点是它隐含了一个假设任何一次可行合成都不会影响最终最优产量。在很多依赖图是树形结构的题目里这个假设成立但如果配方分支复杂选择哪个配方先执行可能会影响后续产量。因此我仍然建议用DFS版本至少它能通过回退机制处理分支选择。另外题目在设计时通常保证了配方依赖不会成环而且材料1不会作为其他配方的原料。如果题目出现环比如合成A需要B合成B又需要A那dfs就会无限递归下去。稳妥的做法是在递归函数里加一个栈标记检测到环就返回false。4.4 处理配方依赖的三个提醒第一个提醒是回溯别偷懒。有些同学觉得只要原料不够就返回false没必要保存和恢复库存但这样一旦递归深了几层前面成功消耗的原料就全部变成“白消耗”最终结果会偏大。回溯是DFS处理资源分配问题的生命线。第二个提醒是小心重复使用同一种原料。一个配方可能消耗两种原料而这两种原料可能又共享同一个更低级原料。递归搜索时如果你不仔细跟踪库存很容易出现“把同一份低级原料算成两份”的错觉。DFS每次消耗都真实修改cnt数组能避免这种问题。第三个提醒是复杂度控制。N只有100初始库存总和也不大所以每次成功生产一份材料1都会消耗一些原料循环次数不会太多。但如果你发现递归搜索特别慢可以先判断是否存在环也可以给dfs增加一个记忆化对某个x已经确认过“当前库存下无法得到”那就不需要反复尝试同一个x。5. 从2022 OPEN看青铜组冲刺建议5.1 青铜组真正考的是建模能力把三道题放在一起看你会发现一个规律代码本身都很短核心逻辑没有超过三十行。Photoshoot是枚举一个变量后递推Counting Liars是枚举位置后统计Alchemy是递归搜索加回溯。这些都算不上什么算法但它们有一个共同点需要你先在脑子里完成建模把题目描述变成一个明确的数学结构。这也是青铜组最劝退新人的地方。很多选手不是不会写代码而是读题之后不知道从何下手。比如Counting Liars如果你只是盯着“说谎者”这三个字很容易往逻辑推理的方向想想半天也不知道怎么处理。但一旦你意识到每头牛的陈述都是一个半无限区间问题立刻变成了“求被覆盖最多的点”那就简单多了。所以我建议你在刷题时不要急着打开代码编辑器。先把题面用自己的话复述一遍然后写下这个问题的输入是什么、输出是什么、抽象成什么模型。等模型清楚了代码往往水到渠成。5.2 针对这三类题型的训练方法如果你现在正在为下一次月赛准备可以按照今天这套题的分类去做针对性训练。排列枚举类题目重点练“确定第一个变量后推导整条链”的思路。USACO历年青铜组里大量题目都可以用这种思路解决比如已知前缀关系还原原数组、已知相邻差还原排列等。每道题你都试着一口气写出O(N²)的版本再想有没有更快的写法。区间统计类题目重点练“把文字约束变成区间”的建模能力。你可以找一些Silver级别的简单区间题把数据范围改成1000用O(N²)去做体会枚举和统计的过程。等你觉得熟练了再学习排序加二分的优化版本。递归依赖类题目重点练DFS和回溯。不需要做太难的题树的遍历、括号匹配、数独填数这类基础的DFS题目就够用了。关键是养成一个习惯每次递归进入下一层之前先想清楚这个分支失败之后现场的哪些状态需要恢复。5.3 考场上的时间管理和自测习惯青铜组比赛没有想象中那么紧张四个小时做三道题绰绰有余。但很多选手还是会在某一题上卡到崩溃。我的建议是拿到题面后先把三道题全部读一遍按难度排个序先做最确定的送分题。每道题想不出解法的时间不要超过45分钟超过就先写一个暴力版本能拿部分分也总比空着强。另外比赛结束前一定要留出时间自测边界数据。以今天这三道题为例Photoshoot你要测N2的情况因为此时b数组只有一个数最容易暴露下标错误Counting Liars你要测所有牛都朝一个方向说话的情况Alchemy你要测没有任何配方可用的情况。这些边界数据能帮你发现很多隐藏bug。文件读写也值得单独提一句。USACO要求每道题用对应的文件输入输出经常有人把文件名拼错或者忘记关闭文件导致输出为空。建议你在本地维护一个固定的模板考试时只需要替换题目名能省去很多不必要的失误。最后分享一个我自己坚持了很多年的习惯每次月赛结束不管成绩如何我会把当次的三道题按“枚举、统计、递归、图论”之类的标签归档并在旁边用一句话写下核心思路。下一场月赛前先花半小时翻一遍这个归档比盲目刷十道新题都管用。2022 OPEN这套青铜题如果你能独立把三道题的建模过程都想明白那你已经有能力在下一场月赛里稳定拿满分了。
