企业官网建设流程全解析

USACO 2022年的OPEN（US Open）是那个赛季的最后一场月赛，青铜组三道题分别是 Photoshoot、Counting Liars、Alchemy。这套题可以说把青铜组最典型的几种考察方式都凑齐了：一题考“枚举加递推”，一题考“把文字描述翻译成区间统计”，还有一题考“依赖关系下的递归搜索”。很多选手平时刷题不少，但一到月赛就卡住，问题往往就出在不会把故事题还原成算法模型。这篇不打算照着官方题解念一遍，而是按我平时带人的思路，把每道题从读题、建模、写代码到踩坑的完整过程捋一遍。看完你应该能明白，青铜组真正需要的不是高深算法，而是把问题拆小的能力。

1. 2022 OPEN青铜组：三题考了什么

1.1 题目与考点总览

先说结论：2022 OPEN青铜组整体难度不算高，但区分度很足。三题的核心考点分别落在枚举、区间覆盖统计和递归依赖处理，都是青铜组最高频的几类模型。

从这三道题能明显看出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[i+1]。现在给你这个数组b，你需要还原出原本的排列a，并且要求字典序最小。

题目给的样例是这样的：

N = 5 b = [4, 6, 7, 6]

如果排列a = [3, 1, 5, 2, 4]，那么相邻和就是3+1=4，1+5=6，5+2=7，2+4=6，正好对应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; vector<int> b(n + 1); for (int i = 1; i <= n - 1; i++) { fin >> b[i]; } for (int first = 1; first <= n; first++) { vector<int> a(n + 1); vector<bool> 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; vector<pair<char, int>> cows(n); set<int> 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两类陈述分别装进两个数组，分别排序。

对于给定的候选位置pos：

• G类陈述中，说真话的数量等于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)。代码片段如下：

vector<int> 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; vector<int> ingredients; }; int n; vector<int> cnt; vector<Recipe> recipes; bool dfs(int x) { if (cnt[x] > 0) { cnt[x]--; return true; } for (auto &r : recipes) { if (r.product != x) continue; vector<int> 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你要测N=2的情况，因为此时b数组只有一个数，最容易暴露下标错误；Counting Liars你要测所有牛都朝一个方向说话的情况；Alchemy你要测没有任何配方可用的情况。这些边界数据能帮你发现很多隐藏bug。

文件读写也值得单独提一句。USACO要求每道题用对应的文件输入输出，经常有人把文件名拼错，或者忘记关闭文件导致输出为空。建议你在本地维护一个固定的模板，考试时只需要替换题目名，能省去很多不必要的失误。

最后分享一个我自己坚持了很多年的习惯：每次月赛结束，不管成绩如何，我会把当次的三道题按“枚举、统计、递归、图论”之类的标签归档，并在旁边用一句话写下核心思路。下一场月赛前，先花半小时翻一遍这个归档，比盲目刷十道新题都管用。2022 OPEN这套青铜题，如果你能独立把三道题的建模过程都想明白，那你已经有能力在下一场月赛里稳定拿满分了。