USACO青铜组做了几套题之后你会发现一个特别有意思的现象很多题不是不会写代码而是卡在“第一步怎么想”上。2022年OPEN的这道 Photoshoot 就是典型代表它代码不到20行但能把人绕进去。这篇我打算把这道题从题意到推导、从代码到复盘完整拆一遍把我当时踩过的坑和后来想明白的点都写出来。正在刷青铜组的朋友或者准备冲银组但总差一口气的选手这篇文章应该能帮你们把“枚举验证”这个套路吃透。1. 2022年OPEN青铜组为什么这一年的题目值得反复做先给不熟悉USACO的朋友交代一下背景。USACO每个赛季从12月开始中间有1月、2月两场月赛最后以3月底到4月初的OPEN公开赛收尾。OPEN作为整个赛季的收官战出题风格通常比前几场更活题目不会在算法难度上为难你但会在思维绕弯上做文章。2022年OPEN青铜组的三道题里最值得反复琢磨的就是第一题Photoshoot。这题表面看起来是一道数学题——给你一堆相邻和让你还原排列。很多人在考场上第一反应是列方程、解方程组甚至有人往高斯消元方向想。但实际上它考察的是青铜组最核心的一种能力找到那个“一旦确定整条链都确定”的钥匙变量然后按从小到大的顺序去尝试。说得直白点就是枚举加验证。我个人觉得Photoshoot这道题值得反复做的原因有三个。第一它的结构非常干净整道题只有一层相邻关系没有多余的条件干扰非常适合用来学习“从递推关系入手”的思考方式。第二它把“字典序最小”这个在USACO里反复出现的诉求演得很标准——不是让你把所有答案列出来排序而是让你发现枚举顺序本身就是字典序顺序。第三它的代码量极短但每一行都有实际作用没有一行是凑数的这种题拿来练代码准确率特别合适。另外从备考角度看2022年OPEN这道题和同赛季12月、1月、2月的题目放在一起对比能看到很清晰的出题脉络青铜组从不考冷门算法翻来覆去就是模拟、枚举、贪心、简单数学这几板斧但每次都会换一个包装。Photoshoot就是“枚举贪心”这板斧的标准示范吃透它再去做类似的题比如给前缀和还原数组、给差分数组还原原数组思路会顺很多。2. Photoshoot 完整题意与样例推演2.1 题面到底在说什么先用自己的话把题目说清楚免得有人被原题的长篇故事带偏。有N头奶牛排队拍照每头奶牛身上贴了一个编号这N个编号恰好是1到N的一个排列也就是说每个编号出现且只出现一次。摄影师记下了每对相邻奶牛的编号之和得到一个有N-1个数的数组b其中b_i a_i a_{i1}。现在的问题是给你这个b数组让你还原出字典序最小的排列a。三个关键点必须拎清楚。第一a是1到N的排列不能有重复数字这一点决定了后面所有合法性判断第二b的长度只有N-1说明相邻关系形成了一条链而不是环第三题目要的是字典序最小的那个排列不是随便一个合法解。题面里还有个容易被忽略的细节输入输出走文件输入是photo.in输出是photo.out。在USACO的评测环境里如果你忘了写freopen本地跑得再对也拿不到分这个坑每年都有人踩后面讲代码的时候我会再强调。2.2 手推样例能发现什么规律这里我不照搬原题样例用一个自己构造的例子来推演效果一样还更能看出门道。假设N5b数组是[4, 6, 7, 6]。也就是说a1 a2 4 a2 a3 6 a3 a4 7 a4 a5 6现在我们把a1从1开始一个一个试。a11时由第一个等式推出a23再由第二个等式推出a33。到这里就已经出问题了a2和a3都等于3违反了排列不能重复的规则所以a11不合法。a12时a22又和a1撞了直接排除。a13时a21a35a42a54合起来是[3, 1, 5, 2, 4]五个数正好是1到5各出现一次合法。a14时a20这个数字根本不在1到N的范围内排除。a15时a2-1更不可能。所以唯一合法解是[3, 1, 5, 2, 4]它同时也是字典序最小的解。不知道大家注意到没有整个推演过程有个非常明显的规律只要a1的值一确定后面每个数就像多米诺骨牌一样被推着走完中间没有任何选择余地。a2由a1和b1唯一确定a3由a2和b2唯一确定后面全部同理。这个规律就是整道题的命门。3. 从“瞎枚举”到“有依据的枚举”解题思路推导3.1 为什么不能直接枚举完整排列很多初学者拿到这题的第一反应是把所有可能的排列全枚举出来逐个检查是否符合b数组。这个思路在N很小的时候确实能跑通N5时有120种排列N8时有40320种都还能接受。但N一大就完全失控了。我记得原题的数据范围是N不超过1000。1000的阶乘是什么概念这个数字比宇宙中已知的原子总数还要多无数倍计算机再快也枚举不完。就算不用全排列用递归加剪枝硬搜最坏情况下仍然是指数级复杂度跑到比赛结束也出不来结果。这里其实暴露了一个通用思维看到“排列”两个字先别急着枚举排列本身要想想能不能枚举一个更小的东西。USACO青铜组的题几乎都是这个套路直接枚举目标对象通常超时但枚举一个关键的“入口变量”然后O(N)推出整个答案就能把复杂度降下来。3.2 相邻和是一条递推链为什么b_i a_i a_{i1}这个结构这么关键因为它把一个看似整体的排列拆成了一条可以逐步推进的链。我们把等式稍微变一下形a_{i1} b_i - a_i。注意这个式子里只要知道a_i和b_ia_{i1}就被唯一确定了。而a_1和b_1知道之后a_2就定了a_2定了之后和b_2一结合a_3又定了。一个接一个一直到a_N。这个结构可以类比成连环锁每一节锁链和下一节共用一个关键点只要第一节的位置定了整条锁链的形状就完全确定了中间不会出现“这里能有两种选择”的情况。所以整道题的搜索空间本质上不是N!个排列而只有N个可能的a1。这个降维幅度是巨大的。从这个角度看题目的名字Photoshoot也挺贴切——奶牛站成一排拍照相邻两头牛的编号和形成了天然的链条关系而我们要做的是从这串相邻和里倒推出每个人的编号。3.3 正确性证明为什么固定a1后一切都确定了这一步值得单独拿出来说因为它涉及一道题能不能“确定做对”而不是“碰巧做对”。我们要证明一个结论如果a1固定那么整个序列a被唯一确定且我们可以通过递推逐项构造它。证明其实很直观用归纳法走一遍当i1时a2 b1 - a1这是唯一的。假设a_i已经确定那么a_{i1} b_i - a_i又由b_i给出所以a_{i1}也唯一确定。依此类推从1到N的每一项都被唯一确定。因此每个合法的a1最多对应一个合法排列不存在“同一个a1下面有好几种排列”的情况。接下来处理字典序最小这个需求。字典序比较排列时先比较第一个元素第一个元素小的排列整体一定更小第一个元素相同才比较第二个以此类推。既然每个a1只对应一个排列那么我只要按a1从小到大的顺序去尝试第一个能成功推出完整合法排列的a1它的排列一定就是字典序最小的。这一步的思维价值在于它把“在所有合法排列里找字典序最小”这个看起来要排序的问题简化成了“从1到N按顺序试a1找到第一个合法解”这个线性问题。不用存所有答案不用写自定义比较函数甚至连排序都不用做。4. C实现与三个经典坑位4.1 参考代码直接上代码USACO主流的C写法文件输入输出已经带上。#include bits/stdc.h using namespace std; int main() { freopen(photo.in, r, stdin); freopen(photo.out, w, stdout); int n; cin n; vectorint b(n 1); for (int i 1; i n - 1; i) { cin b[i]; } for (int a1 1; a1 n; a1) { vectorint a(n 1); vectorbool used(n 1, false); a[1] a1; used[a1] true; bool ok true; for (int i 2; i n; i) { a[i] b[i - 1] - a[i - 1]; if (a[i] 1 || a[i] n || used[a[i]]) { ok false; break; } used[a[i]] true; } if (ok) { for (int i 1; i n; i) { if (i 1) cout ; cout a[i]; } cout \n; return 0; } } return 0; }代码思路就是前面推导的落地外层循环枚举a1内层循环用递推生成后续所有数每生成一个就检查范围是否越界、数字是否重复。全部通过就输出并结束程序。复杂度上外层枚举最多N次每次内层跑N步总共O(N^2)。N1000的时候也就一百万次运算在USACO的时限内跑得轻轻松松。代码里每个数组都开了N1的大小从1开始用下标主要是为了方便理解也让b[i-1]这种对应关系更清晰。4.2 坑位1a1的枚举起点这题a1的枚举范围是1到N这个看起来显然但实际写的时候有些同学会惯性从0开始枚举。一从0开始要么WA要么白白多跑一轮因为奶牛编号是1到Na1根本不可能等于0。反过来也不要为了“保险”把枚举范围扩大比如从1到1000以外或者其他什么值。编号范围就是1到N超出这个范围的a1一定不合法枚举了也是白费时间。写的时候直接把for循环定成for (int a1 1; a1 n; a1)干净利落。4.3 坑位2合法排列必须判重这是很多人第一次交这道题WA掉的头号原因。有的同学觉得只要每个a[i]算出来都在1到N范围内那就合法了。大错特错。举个例子如果某个序列算出来是[1, 2, 1, 2]每个数字都在1到N范围内但它显然不是排列因为1重复了2也重复了。原题要求的是1到N每个数恰好出现一次所以除了检查范围还必须用一个布尔数组used记录哪些数字已经出现过。每次算出新的a[i]先查used[a[i]]如果是true就说明重复了直接判定不合法。这个坑之所以容易踩是因为小数据时碰巧不重复的情况很多但一旦N稍微大一点不判重就会放出大量非法解。我当年自己写的时候也栽过后来养成了习惯只要是“生成一个序列”的题不管题目有没有明说排列只要涉及“每个数出现一次”立刻想到布尔判重绝不偷懒。4.4 坑位3下标错位与字典序思维第三个坑藏在细节里。b数组的长度是N-1如果从0开始存那么b[i-1]这种映射关系就特别容易错。我在代码里故意让b从下标1开始存a也从1开始存这样b[i-1]对应的是a[i-1]和a[i]的和逻辑上非常直接。下标错位这类问题在USACO里特别常见尤其是数组长度和原题目给的长度不一致时一定要在草稿纸上把对应关系写清楚再动手。还有一个思维上的坑不算代码bug但会影响思路效率不要在枚举过程中收集所有合法排列最后再统一排序找字典序最小。完全没有必要而且浪费空间。因为a1从小到大枚举第一个合法解就是字典序最小解。这一点在3.3里证明过写代码时要敢于直接相信它不要画蛇添足加一个vector去存所有答案。5. 从这道题反推USACO青铜组的出题套路5.1 青铜组最常考的四类思维把Photoshoot放到整个USACO青铜组的真题池里看你会发现它身上的特征非常典型。青铜组考来考去基本困在四类思维里思维类型典型特征Photoshoot的表现模拟题目描述一个过程按步骤执行递推生成序列就是一种过程模拟枚举在有限候选里逐个尝试枚举a1而不是枚举全排列贪心每一步选当前最优从小到大试a1找最小合法解简单数学奇偶性、整除、等式变换b_i a_i a_{i1}移项得递推式很多青铜组题目的难点不在于你懂多少高深算法而在于你能不能识别出这道题包装之下真正要考的是哪类思维。Photoshoot把四类都沾了一点但又都不难正好用来做“识别题型”的训练素材。5.2 拿到一道青铜题的正确思考顺序刷多了之后我总结出一套适用于大多数青铜组题目的思考流程分享给大家参考。第一步先看数据范围。N到1000还是N到10万直接决定了你能不能用O(N^2)的算法。Photoshoot的N到1000就是在暗示O(N^2)枚举可行——这本身就是出题人留下的线索。第二步小数据手推。别急着写代码拿题目给的样例或者在草稿纸上构造几个小例子把过程完整推一遍。手推的过程中你会自然而然地发现规律Photoshoot的“a1定了后面全定”就是这个阶段浮现出来的。第三步找“钥匙量”。也就是问自己有没有一个变量一旦确定整个答案就唯一确定了这道题是a1很多题是第一个数或者某个边界值。这个钥匙量往往是问题的核心入口。第四步设计验证逻辑。确定了钥匙量之后剩下的就是沿着题目条件一步步生成并在生成过程中加各种合法性检查。检查通常包括范围、重复、奇偶性等具体看题目要求。这套流程听起来简单但真正形成肌肉记忆需要大量练习。每次做题都按这个顺序走一遍而不是拿到题就开始瞎写循环效率会高非常多。5.3 训练建议怎么把真题用透最后聊点实际的备考建议。很多人刷USACO真题的方式是“刷完看题解看懂了就算过”这种刷法对青铜组来说效率偏低因为看懂和自己能想到之间差距极大。我比较推荐一道题做三遍。第一遍拿到题先独立思考不查任何资料能写多少写多少哪怕只写出一个超时的暴力代码也算数先把思考过程和代码存档。第二遍隔一周再拿出来重写这时候一边写一边想上次卡在哪、这次有没有进步。第三遍给自己限时比如25分钟内独立完成模拟考场节奏。三遍下来这道题的题眼和坑位基本就刻进脑子里了。具体到Photoshoot这道题重写的时候可以顺带想想如果题目改成给差分数组怎么还原原数组如果b_i表示的是a_i到a_{i1}的差枚举入口变量还成立吗这种举一反三比多做三套新题更有价值因为USACO青铜组反复考的就是同一批底层思维换包装不换内核。踩过几次坑之后我的体会是Photoshoot这种题最怕的不是代码写不出来而是思路一直停留在“枚举全排列”的层面被卡住。一旦想明白“枚举入口变量递推验证”这个模式青铜组一大半类似题目都会豁然开朗。把这题的思路彻底消化再去刷往年的青铜组真题你会明显感觉看题的角度不一样了。
USACO青铜组Photoshoot：枚举+递推破解排列还原
USACO青铜组做了几套题之后你会发现一个特别有意思的现象很多题不是不会写代码而是卡在“第一步怎么想”上。2022年OPEN的这道 Photoshoot 就是典型代表它代码不到20行但能把人绕进去。这篇我打算把这道题从题意到推导、从代码到复盘完整拆一遍把我当时踩过的坑和后来想明白的点都写出来。正在刷青铜组的朋友或者准备冲银组但总差一口气的选手这篇文章应该能帮你们把“枚举验证”这个套路吃透。1. 2022年OPEN青铜组为什么这一年的题目值得反复做先给不熟悉USACO的朋友交代一下背景。USACO每个赛季从12月开始中间有1月、2月两场月赛最后以3月底到4月初的OPEN公开赛收尾。OPEN作为整个赛季的收官战出题风格通常比前几场更活题目不会在算法难度上为难你但会在思维绕弯上做文章。2022年OPEN青铜组的三道题里最值得反复琢磨的就是第一题Photoshoot。这题表面看起来是一道数学题——给你一堆相邻和让你还原排列。很多人在考场上第一反应是列方程、解方程组甚至有人往高斯消元方向想。但实际上它考察的是青铜组最核心的一种能力找到那个“一旦确定整条链都确定”的钥匙变量然后按从小到大的顺序去尝试。说得直白点就是枚举加验证。我个人觉得Photoshoot这道题值得反复做的原因有三个。第一它的结构非常干净整道题只有一层相邻关系没有多余的条件干扰非常适合用来学习“从递推关系入手”的思考方式。第二它把“字典序最小”这个在USACO里反复出现的诉求演得很标准——不是让你把所有答案列出来排序而是让你发现枚举顺序本身就是字典序顺序。第三它的代码量极短但每一行都有实际作用没有一行是凑数的这种题拿来练代码准确率特别合适。另外从备考角度看2022年OPEN这道题和同赛季12月、1月、2月的题目放在一起对比能看到很清晰的出题脉络青铜组从不考冷门算法翻来覆去就是模拟、枚举、贪心、简单数学这几板斧但每次都会换一个包装。Photoshoot就是“枚举贪心”这板斧的标准示范吃透它再去做类似的题比如给前缀和还原数组、给差分数组还原原数组思路会顺很多。2. Photoshoot 完整题意与样例推演2.1 题面到底在说什么先用自己的话把题目说清楚免得有人被原题的长篇故事带偏。有N头奶牛排队拍照每头奶牛身上贴了一个编号这N个编号恰好是1到N的一个排列也就是说每个编号出现且只出现一次。摄影师记下了每对相邻奶牛的编号之和得到一个有N-1个数的数组b其中b_i a_i a_{i1}。现在的问题是给你这个b数组让你还原出字典序最小的排列a。三个关键点必须拎清楚。第一a是1到N的排列不能有重复数字这一点决定了后面所有合法性判断第二b的长度只有N-1说明相邻关系形成了一条链而不是环第三题目要的是字典序最小的那个排列不是随便一个合法解。题面里还有个容易被忽略的细节输入输出走文件输入是photo.in输出是photo.out。在USACO的评测环境里如果你忘了写freopen本地跑得再对也拿不到分这个坑每年都有人踩后面讲代码的时候我会再强调。2.2 手推样例能发现什么规律这里我不照搬原题样例用一个自己构造的例子来推演效果一样还更能看出门道。假设N5b数组是[4, 6, 7, 6]。也就是说a1 a2 4 a2 a3 6 a3 a4 7 a4 a5 6现在我们把a1从1开始一个一个试。a11时由第一个等式推出a23再由第二个等式推出a33。到这里就已经出问题了a2和a3都等于3违反了排列不能重复的规则所以a11不合法。a12时a22又和a1撞了直接排除。a13时a21a35a42a54合起来是[3, 1, 5, 2, 4]五个数正好是1到5各出现一次合法。a14时a20这个数字根本不在1到N的范围内排除。a15时a2-1更不可能。所以唯一合法解是[3, 1, 5, 2, 4]它同时也是字典序最小的解。不知道大家注意到没有整个推演过程有个非常明显的规律只要a1的值一确定后面每个数就像多米诺骨牌一样被推着走完中间没有任何选择余地。a2由a1和b1唯一确定a3由a2和b2唯一确定后面全部同理。这个规律就是整道题的命门。3. 从“瞎枚举”到“有依据的枚举”解题思路推导3.1 为什么不能直接枚举完整排列很多初学者拿到这题的第一反应是把所有可能的排列全枚举出来逐个检查是否符合b数组。这个思路在N很小的时候确实能跑通N5时有120种排列N8时有40320种都还能接受。但N一大就完全失控了。我记得原题的数据范围是N不超过1000。1000的阶乘是什么概念这个数字比宇宙中已知的原子总数还要多无数倍计算机再快也枚举不完。就算不用全排列用递归加剪枝硬搜最坏情况下仍然是指数级复杂度跑到比赛结束也出不来结果。这里其实暴露了一个通用思维看到“排列”两个字先别急着枚举排列本身要想想能不能枚举一个更小的东西。USACO青铜组的题几乎都是这个套路直接枚举目标对象通常超时但枚举一个关键的“入口变量”然后O(N)推出整个答案就能把复杂度降下来。3.2 相邻和是一条递推链为什么b_i a_i a_{i1}这个结构这么关键因为它把一个看似整体的排列拆成了一条可以逐步推进的链。我们把等式稍微变一下形a_{i1} b_i - a_i。注意这个式子里只要知道a_i和b_ia_{i1}就被唯一确定了。而a_1和b_1知道之后a_2就定了a_2定了之后和b_2一结合a_3又定了。一个接一个一直到a_N。这个结构可以类比成连环锁每一节锁链和下一节共用一个关键点只要第一节的位置定了整条锁链的形状就完全确定了中间不会出现“这里能有两种选择”的情况。所以整道题的搜索空间本质上不是N!个排列而只有N个可能的a1。这个降维幅度是巨大的。从这个角度看题目的名字Photoshoot也挺贴切——奶牛站成一排拍照相邻两头牛的编号和形成了天然的链条关系而我们要做的是从这串相邻和里倒推出每个人的编号。3.3 正确性证明为什么固定a1后一切都确定了这一步值得单独拿出来说因为它涉及一道题能不能“确定做对”而不是“碰巧做对”。我们要证明一个结论如果a1固定那么整个序列a被唯一确定且我们可以通过递推逐项构造它。证明其实很直观用归纳法走一遍当i1时a2 b1 - a1这是唯一的。假设a_i已经确定那么a_{i1} b_i - a_i又由b_i给出所以a_{i1}也唯一确定。依此类推从1到N的每一项都被唯一确定。因此每个合法的a1最多对应一个合法排列不存在“同一个a1下面有好几种排列”的情况。接下来处理字典序最小这个需求。字典序比较排列时先比较第一个元素第一个元素小的排列整体一定更小第一个元素相同才比较第二个以此类推。既然每个a1只对应一个排列那么我只要按a1从小到大的顺序去尝试第一个能成功推出完整合法排列的a1它的排列一定就是字典序最小的。这一步的思维价值在于它把“在所有合法排列里找字典序最小”这个看起来要排序的问题简化成了“从1到N按顺序试a1找到第一个合法解”这个线性问题。不用存所有答案不用写自定义比较函数甚至连排序都不用做。4. C实现与三个经典坑位4.1 参考代码直接上代码USACO主流的C写法文件输入输出已经带上。#include bits/stdc.h using namespace std; int main() { freopen(photo.in, r, stdin); freopen(photo.out, w, stdout); int n; cin n; vectorint b(n 1); for (int i 1; i n - 1; i) { cin b[i]; } for (int a1 1; a1 n; a1) { vectorint a(n 1); vectorbool used(n 1, false); a[1] a1; used[a1] true; bool ok true; for (int i 2; i n; i) { a[i] b[i - 1] - a[i - 1]; if (a[i] 1 || a[i] n || used[a[i]]) { ok false; break; } used[a[i]] true; } if (ok) { for (int i 1; i n; i) { if (i 1) cout ; cout a[i]; } cout \n; return 0; } } return 0; }代码思路就是前面推导的落地外层循环枚举a1内层循环用递推生成后续所有数每生成一个就检查范围是否越界、数字是否重复。全部通过就输出并结束程序。复杂度上外层枚举最多N次每次内层跑N步总共O(N^2)。N1000的时候也就一百万次运算在USACO的时限内跑得轻轻松松。代码里每个数组都开了N1的大小从1开始用下标主要是为了方便理解也让b[i-1]这种对应关系更清晰。4.2 坑位1a1的枚举起点这题a1的枚举范围是1到N这个看起来显然但实际写的时候有些同学会惯性从0开始枚举。一从0开始要么WA要么白白多跑一轮因为奶牛编号是1到Na1根本不可能等于0。反过来也不要为了“保险”把枚举范围扩大比如从1到1000以外或者其他什么值。编号范围就是1到N超出这个范围的a1一定不合法枚举了也是白费时间。写的时候直接把for循环定成for (int a1 1; a1 n; a1)干净利落。4.3 坑位2合法排列必须判重这是很多人第一次交这道题WA掉的头号原因。有的同学觉得只要每个a[i]算出来都在1到N范围内那就合法了。大错特错。举个例子如果某个序列算出来是[1, 2, 1, 2]每个数字都在1到N范围内但它显然不是排列因为1重复了2也重复了。原题要求的是1到N每个数恰好出现一次所以除了检查范围还必须用一个布尔数组used记录哪些数字已经出现过。每次算出新的a[i]先查used[a[i]]如果是true就说明重复了直接判定不合法。这个坑之所以容易踩是因为小数据时碰巧不重复的情况很多但一旦N稍微大一点不判重就会放出大量非法解。我当年自己写的时候也栽过后来养成了习惯只要是“生成一个序列”的题不管题目有没有明说排列只要涉及“每个数出现一次”立刻想到布尔判重绝不偷懒。4.4 坑位3下标错位与字典序思维第三个坑藏在细节里。b数组的长度是N-1如果从0开始存那么b[i-1]这种映射关系就特别容易错。我在代码里故意让b从下标1开始存a也从1开始存这样b[i-1]对应的是a[i-1]和a[i]的和逻辑上非常直接。下标错位这类问题在USACO里特别常见尤其是数组长度和原题目给的长度不一致时一定要在草稿纸上把对应关系写清楚再动手。还有一个思维上的坑不算代码bug但会影响思路效率不要在枚举过程中收集所有合法排列最后再统一排序找字典序最小。完全没有必要而且浪费空间。因为a1从小到大枚举第一个合法解就是字典序最小解。这一点在3.3里证明过写代码时要敢于直接相信它不要画蛇添足加一个vector去存所有答案。5. 从这道题反推USACO青铜组的出题套路5.1 青铜组最常考的四类思维把Photoshoot放到整个USACO青铜组的真题池里看你会发现它身上的特征非常典型。青铜组考来考去基本困在四类思维里思维类型典型特征Photoshoot的表现模拟题目描述一个过程按步骤执行递推生成序列就是一种过程模拟枚举在有限候选里逐个尝试枚举a1而不是枚举全排列贪心每一步选当前最优从小到大试a1找最小合法解简单数学奇偶性、整除、等式变换b_i a_i a_{i1}移项得递推式很多青铜组题目的难点不在于你懂多少高深算法而在于你能不能识别出这道题包装之下真正要考的是哪类思维。Photoshoot把四类都沾了一点但又都不难正好用来做“识别题型”的训练素材。5.2 拿到一道青铜题的正确思考顺序刷多了之后我总结出一套适用于大多数青铜组题目的思考流程分享给大家参考。第一步先看数据范围。N到1000还是N到10万直接决定了你能不能用O(N^2)的算法。Photoshoot的N到1000就是在暗示O(N^2)枚举可行——这本身就是出题人留下的线索。第二步小数据手推。别急着写代码拿题目给的样例或者在草稿纸上构造几个小例子把过程完整推一遍。手推的过程中你会自然而然地发现规律Photoshoot的“a1定了后面全定”就是这个阶段浮现出来的。第三步找“钥匙量”。也就是问自己有没有一个变量一旦确定整个答案就唯一确定了这道题是a1很多题是第一个数或者某个边界值。这个钥匙量往往是问题的核心入口。第四步设计验证逻辑。确定了钥匙量之后剩下的就是沿着题目条件一步步生成并在生成过程中加各种合法性检查。检查通常包括范围、重复、奇偶性等具体看题目要求。这套流程听起来简单但真正形成肌肉记忆需要大量练习。每次做题都按这个顺序走一遍而不是拿到题就开始瞎写循环效率会高非常多。5.3 训练建议怎么把真题用透最后聊点实际的备考建议。很多人刷USACO真题的方式是“刷完看题解看懂了就算过”这种刷法对青铜组来说效率偏低因为看懂和自己能想到之间差距极大。我比较推荐一道题做三遍。第一遍拿到题先独立思考不查任何资料能写多少写多少哪怕只写出一个超时的暴力代码也算数先把思考过程和代码存档。第二遍隔一周再拿出来重写这时候一边写一边想上次卡在哪、这次有没有进步。第三遍给自己限时比如25分钟内独立完成模拟考场节奏。三遍下来这道题的题眼和坑位基本就刻进脑子里了。具体到Photoshoot这道题重写的时候可以顺带想想如果题目改成给差分数组怎么还原原数组如果b_i表示的是a_i到a_{i1}的差枚举入口变量还成立吗这种举一反三比多做三套新题更有价值因为USACO青铜组反复考的就是同一批底层思维换包装不换内核。踩过几次坑之后我的体会是Photoshoot这种题最怕的不是代码写不出来而是思路一直停留在“枚举全排列”的层面被卡住。一旦想明白“枚举入口变量递推验证”这个模式青铜组一大半类似题目都会豁然开朗。把这题的思路彻底消化再去刷往年的青铜组真题你会明显感觉看题的角度不一样了。
