1. 先把这个老问题翻译成代码能理解的条件B3836这个编号在GESP二级的题库里挺出名本质就是一道活了一千五百多年的老题——百鸡问题。每次带学生备战GESP二级我都会拿它当枚举思想的入门例题。这道题表面上是个数学题实际上考的是你有没有能力把文字条件拆成循环和if。很多孩子一看公鸡母鸡小鸡就慌了其实读完题你会发现需要写的代码不超过三十行。先把原题的意思捋一遍。题目出自中国古代数学著作《张邱建算经》原话是鸡翁一值钱五鸡母一值钱三鸡雏三值钱一。凡百钱买鸡百只问翁、母、雏各几何。GESP二级的B3836就是把这个故事数字化公鸡每只5文钱母鸡每只3文钱小鸡3只共1文钱。现在手里有100文钱要刚好买到100只鸡问公鸡、母鸡、小鸡分别多少只。按公鸡数量从小到大输出所有满足条件的方案如果没有方案输出None。这道题没有输入直接输出结果。我习惯让学生先别碰电脑拿笔把答案算出来然后再去想代码怎么写。因为只有你先知道答案长什么样后面写程序验证起来才有底。1.1 把题目条件翻译成数学表达式设公鸡为a只母鸡为b只小鸡为c只条件其实就两条数量条件a b c 100价格条件5a 3b c / 3 100价格条件里为什么是c/3而不是别的因为三只小鸡才一文钱所以c只小鸡的总价就是c除以3。但这里藏着一个很容易被忽略的前提鸡只能整只买不可能出现买半只小鸡的情况。所以c必须是3的倍数也就是c % 3 0否则这一组数据根本不成立。这个条件在翻译成代码时一定要写出来很多人的第一版程序就是漏了它导致把不该输出的方案也输出了。还有一个隐含要求是a、b、c都是非负整数。虽然题目没直接说可以一只公鸡都不买但数学上买0只是合法的。后面我们会看到这个0恰恰是最容易漏掉的一类答案。1.2 为什么GESP二级会拿它当压轴GESP二级的考纲很明确顺序结构、分支结构、循环结构。不考数组、不考字符串处理、不考函数递归。在这么小的知识范围内能出的有区分度的题目其实不多百鸡问题就是其中最典型的一类不需要任何高级数据结构只要你会写for循环和if判断再有一点把所有可能性都试一遍的枚举意识就能做出来。我把这道题定位成枚举思想的试金石。它考的不是你会不会某个语法而是拿到一个条件之后能不能想到用多层循环把解空间完整地扫一遍再用if把符合条件的方案筛出来。这个思路在二级阶段能救命在后面三级、四级的模拟题里更是常客。很多学生有个误区觉得这种题要先解数学方程解出来再输出答案。但对信息学竞赛来说枚举才是更通用的解法因为万一题目把100改成127方程可能就不好解了而枚举程序只要改一个数还能跑。1.3 输出结果到底长什么样无输入直接打印四行0 25 75 4 18 78 8 11 81 12 4 84这是我让学生先手算出来的结果每组三个数依次是公鸡、母鸡、小鸡。我经常提醒他们注意第一行公鸡数量是0。很多孩子潜意识里觉得买鸡至少得买一只公鸡结果把这一组漏了最后只输出三行白白丢分。题目要求按公鸡数量从小到大输出0、4、8、12正好是升序待会写程序的时候只要让公鸡的循环从小到大走输出顺序就天然满足。2. 最稳妥的思路从三重循环到二重循环的降维现在进入正题。我见过太多初学者一上来就试图用数学技巧直接推导结果把自己绕晕。信息学竞赛里最忌讳的就是想太多写太少。考试时间有限先把一个能跑出正确答案的版本写出来再考虑优化这才是正确节奏。2.1 三重循环先跑通再谈优化最直观的做法是让a、b、c都从0枚举到100把所有组合都试一遍把满足条件的打印出来。代码长这样#include cstdio int main() { for (int a 0; a 100; a) { for (int b 0; b 100; b) { for (int c 0; c 100; c) { if (a b c ! 100) continue; if (c % 3 ! 0) continue; if (5 * a 3 * b c / 3 ! 100) continue; printf(%d %d %d\n, a, b, c); } } } return 0; }这段代码总共循环了101乘101乘101次约103万次。听起来挺大但对现代评测机来说就是几十毫秒的事。GESP二级的评测环境跑这段程序毫无压力哪怕你完全不优化也能拿满分。所以我的建议是如果你在考场上脑子一时转不过弯写三重循环保底完全没问题至少比推导错数学公式导致全盘皆输要强得多。这里有一点要注意判断条件为什么用continue而不是用if包住整个输出两种写法效果一样但我更推荐用continue因为它能让不满足条件就跳过的思路更清晰代码少了嵌套不容易把大括号配对搞错。对刚开始学循环嵌套的孩子来说这个习惯能省掉很多排查错误的时间。2.2 循环边界的学问不是越大越安全上面代码里三个循环都写的是a 100其实这个范围可以缩小得更多。公鸡5文一只100文最多买20只所以a最大就是20母鸡3文一只最多买33只所以b最大是33小鸡不管多便宜总数不能超过100所以c最大是100。把上限改小之后循环次数变成21乘34乘101大概7.2万次比原来快了一个数量级。但我要提醒一句缩小循环范围的前提是你对条件确实理解透了否则很容易出错。有些人图省事把公鸡循环写成a 20这就漏掉了a20这一层。虽然a20时价格已经花光100文不可能还有母鸡和小鸡这组解不存在但万一题目数据变了这种写法就有可能漏解。稳妥起见边界一律用别在这种地方赌运气。还有一个更隐蔽的边界问题a虽然最多20但当a取到20时b其实只能是0。如果你不把b的上限改成100-a而是直接让b从0枚举到33程序也不会出错因为c100-a-b会自动变成负数后面的判断会把它筛掉。这个c可能为负的情况一定要处理否则会出现幽灵方案。2.3 用总数关系砍掉一层循环三重循环的思路简单但不够优雅。既然题目已经给了abc100这个硬条件那c就没必要再枚举了直接用c100-a-b算出来就行。这就是方程约束消元的思想。#include cstdio int main() { for (int a 0; a 20; a) { for (int b 0; b 33; b) { int c 100 - a - b; if (c 0 || c % 3 ! 0) continue; if (5 * a 3 * b c / 3 100) { printf(%d %d %d\n, a, b, c); } } } return 0; }这段代码里有两个细节值得停下来想一想。第一为什么先判断c 0因为如果a和b加起来已经超过100c就变成负数了负数不可能是鸡的数量直接跳过。第二c % 3 ! 0的判断为什么放在价格判断前面因为如果c不是3的倍数c/3在整数除法里会丢掉余数可能导致价格判断产生错误结果。所以先把c的合法性检查完再去做价格比较。这个二重循环版本基本就是我推荐的考场最终版了。它不但代码短逻辑也清楚更重要的是体现了利用约束减少枚举维度的思维方式。别小看这一层优化它把循环次数从103万次降到了不到700次整个程序肉眼可见地嗖一下出结果。3. 用数学把枚举条件再压缩推导出7a4b100如果你对枚举已经玩得比较熟练可以再往前走一步从数学上把解空间直接压缩到一维。这一步不是GESP二级的必须要求但能帮你彻底理解这道题的本质也是为后面学二分、学搜索剪枝打地基。3.1 消元推导从两个等式到7a4b100把前面那组方程搬过来a b c 1005a 3b c/3 100第二个方程两边同时乘以3得到15a 9b c 300。然后用这个式子减去第一个方程c就被消掉了(15a - a) (9b - b) (c - c) 300 - 100也就是14a 8b 200。两边同时除以2就得到非常漂亮的结果7a 4b 100这个式子意味着什么b根本不需要循环枚举它由a唯一决定b (100 - 7a) / 4。只要枚举ab就算出来了c再用100-a-b算出来。3.2 a为什么必须是4的倍数既然b (100 - 7a) / 4那么b要是整数100 - 7a就必须能被4整除。怎么看这个条件我们只用看模4的余数100除以4余07除以4余3。所以100 - 7a能不能被4整除等价于0 - 3a ≡ 0 (mod 4)也就是3a必须是4的倍数。3和4互质所以a必须是4的倍数。同时b不能为负也就是100 - 7a 0所以a最多到14。在这个范围内是4的倍数的数有0、4、8、12。就这四个。逐个代入a0b(100-0)/425c100-0-2575a4b(100-28)/418c100-4-1878a8b(100-56)/411c100-8-1181a12b(100-84)/44c100-12-484于是四组解全部出来了。整个过程不需要计算机一张草稿纸就能写完。这也是为什么很多老选手看到这道题会心一笑因为它的数学本质非常干净。3.3 三种实现的取舍说了三种做法到底用哪种我整理了一张表方案循环次数代码难度出错风险推荐场景三重循环约103万次最低低刚学枚举、考场上求稳二重循环约700次低低考场首选效率与清晰度兼顾数学推导一重循环约14次中较高数学功底好用来验算或炫技我的建议很明确二级考试用二重循环。三重循环虽然也能过但代码稍长容易在三个循环的边界上出纰漏数学推导虽然优雅但万一你推错一步整道题就完了。二重循环正好卡在够简单和够快的平衡点上就算放在GESP三级、四级的场景里也完全够用。4. 考场实战代码这样写才不会被扣分题目本身不难但每年GESP考完还是有人在这道题上丢分。丢分点基本集中在几个非常具体的地方我一个个说。4.1 浮点数判等看似很对其实在赌运气我见过不少学生把价格条件写成这样if (5 * a 3 * b c / 3.0 100.0)看起来挺严谨价格精确到小数再用浮点数判等。但这个写法在原理上就站不住脚。计算机里的浮点数没法精确表示1/3这种无限循环小数c/3.0的二进制结果是个近似值。在某些取值下这个近似值恰好让整个表达式算出来等于100.0在另一些取值下可能就差那么一点点导致本该成立的方案被错误地过滤掉。整数问题就不要引入浮点数这是竞赛里的铁律。正确做法是先把c % 3 ! 0的情况排除掉然后放心大胆地用c / 3做整数除法参与运算。整数除法不会丢精度而且c能被3整除时c / 3就是准确的。4.2 空行、空格和None的大小写输出格式是很多人不注意的隐形扣分点。题目要求每行三个整数用空格分隔行末换行。有些孩子习惯在输出语句里多加一个空格变成a b c 或者用逗号分隔最后全被评测机判成格式错误。GESP的评测对格式要求比较严格宁可少写代码也别在多出来的空格上栽跟头。再看无解分支。题目明确说了如果不存在满足条件的方案输出None。注意是None不是none不是NONE也不是No Solution更不是无解。这种地方就是送命题答案对了字符串大小写错了照样零分。虽然B3836这道题有解用不到这个分支但你不能因为用不到就不写。万一出题人把条件一改或者考场上遇到变体题这个分支就是你的保命符。4.3 考场自查把答案代回去算一遍程序写完别急着交花十秒钟做一次自查。把输出的第一组数据拿回来验证0只公鸡花0文25只母鸡花75文75只小鸡花25文总数2575100只总价7525100文完全吻合。再抽查最后一组12只公鸡花60文4只母鸡花12文84只小鸡花28文总数100只总价100文。能自查出答案是合理的这题基本就稳了。我还习惯在代码里临时加一句输出方案总数的语句确认一共打印了4行。如果只有3行那一定是漏了某个边界情况比如公鸡0只的那组。检查完再把这句临时输出删掉别让它影响到正常输出。5. 完整代码与这套思路往后怎么用最后给出一个可以直接提交的完整版本。我用C17语法头文件只包含cstdio用printf输出全程整数运算。5.1 最终提交版代码#include cstdio int main() { bool found false; for (int a 0; a 20; a) { for (int b 0; b 33; b) { int c 100 - a - b; if (c 0 || c % 3 ! 0) continue; if (5 * a 3 * b c / 3 100) { printf(%d %d %d\n, a, b, c); found true; } } } if (!found) puts(None); return 0; }这段代码里我把上一个版本漏掉的found标记补上了。它的作用就是记录到底有没有找到过方案。如果整个循环跑完一次都没进入过输出分支说明无解这时才输出None。没有这个标记的话无解情况就不知道什么时候该输出None了。这个模式在后续很多输出所有方案无解时输出XXX的题目里都会用到建议直接记下来。5.2 题目改成输入n怎么办有些变体题会把100改成读入的n表示用n文钱买n只鸡或者用100文钱买n只鸡。处理思路完全不变只要把代码里的100全部换掉把循环边界也按n调整即可。比如公鸡最多n/5只母鸡最多n/3只而c的合法范围依赖n。我曾经让学生做过一个练习把这道题的100改成127让他们重新跑程序结果四组解变成了别的组合不少人这才真正理解枚举是跟着条件走而不是背答案。5.3 这套枚举→消元→剪枝的思路后面还要用很久很多人搜GESP七级、八级的备考资料总觉得要学什么高深算法。实际上不管四级考的排序和二分还是五级的递归回溯底层都是枚举。二分本质上是利用单调性加速枚举范围回溯本质上是带剪枝的深度优先枚举。你在百鸡问题里学会的先用最朴素循环跑通再用等式约束减维度最后用数学条件剪枝这条优化链会在之后所有算法题里反复出现。我个人的看法这道GESP二级的百鸡问题值得你花一下午把它玩透。从三重循环写到二重循环再亲手推一遍7a4b100你收获的不只是这一题的满分而是一套处理约束条件的思维习惯。考场上真遇到它直接二重循环稳扎稳打打完收工剩下的时间留给别的题比什么都强。