1. 这道深基题卡住了多少人的第一次提交如果你在洛谷搜索框里输入P5727大概率会看到两种帖子一种人贴出自己正序输出的代码然后配一句为什么全WA另一种人在评论区回复你把输出反过来就过了。这道题作为《深入浅出程序设计竞赛》数组章节的例3表面上是模拟冰雹猜想的变化过程实际上真正想让你练的是用数组存下中间结果再反着打印。很多刚接触信息学奥赛的新手前面几道题做得顺风顺水到这一题突然被倒序输出卡住其实不是不会模拟而是没读懂题面想要什么。先把这个题的核心价值说清楚P5727是一道纯粹练递推/模拟 容器存储的入门题适合刚学完循环、正准备接触数组的同学。它不考任何高深算法时间复杂度几乎可以忽略但它在读题和边界处理两个维度上非常典型。你只要能把这题吃透后面遇到先计算再逆序输出这类问题基本上不用再花时间琢磨。1.1 冰雹猜想到底是什么冰雹猜想也叫科拉茨猜想、3n1猜想、角谷猜想。规则很简单给出一个正整数如果它是奇数就乘以3再加1如果它是偶数就直接除以2。重复执行这两条规则最终一定会落到1。举个例子从20开始20是偶数除以2得1010是偶数除以2得55是奇数乘3加1得1616是偶数除以2得88除以2得44除以2得22除以2得1。整个过程写下来就是20→10→5→16→8→4→2→1。这个数列跳来跳去一会儿冲高一会儿回落很像冰雹在云层里上下翻滚所以叫冰雹猜想。虽然数学家到现在都没完全证明所有正整数最终都会到1但在洛谷这道题给定的数据范围内这个性质是必然成立的所以放心大胆模拟就可以了不需要担心循环跳不出来。1.2 为什么叫深基5.例3熟悉洛谷的同学都知道深基指的是《深入浅出程序设计竞赛》这套教材。第5章讲的是数组例3就是这一题。教材把它放在数组章节意图特别明显希望你能把每一轮变化后的数字按顺序存起来最后用数组的逆序遍历把结果倒过来输出。如果你只用一个变量从头算到尾边算边输出那你得到的是正序结果正好和题目要求相反。这道题的数据范围我记得是1到10的9次方这个级别。这个范围很有意思正好踩在C里int类型可能溢出的边缘上后面我会专门花一章讲这个坑。入门选手如果只盯着模拟过程这件事很可能在本地测试小数据时全都对一提交就超时或WA根源往往不在算法而在数据类型的选用。2. 题面真正的要求不是把过程算出来而是倒着说出来读题是信息学竞赛里最容易翻车的一步P5727就是活生生的例子。很多人看完题目描述觉得哦不就是把变化过程输出嘛直接写一个while循环每变化一步就打印一个数结果样例都过不了。2.1 规则拆分与最容易写错的循环先把规则拆成机械的步骤读入正整数n把n放入过程序列只要n不等于1就重复如果n是奇数把n改成3*n1如果n是偶数把n改成n/2把新的n放入过程序列把过程序列倒序输出有一个细节值得提醒判断奇偶的依据是当前这一轮的n值而不是初始值。也就是说n在变化过程中可能一会儿奇一会儿偶循环体内每次进入都要重新判断。有的新手会把奇偶判断放在循环外面只根据初始n决定后面一路怎么变这显然是错的。还有一个新手很容易忽略的点先把初始的n存进序列再进入循环。如果你先把n算一步再存或者完全忘了存初始值输出结果就会少一个数字。不信你试一下输入20如果忘记存初始的20最终输出就少了一项提交必WA。2.2 倒序输出为什么这道题放在数组这一章我们继续拿20做例子。整个过程是20→10→5→16→8→4→2→1按照题目的输出要求你需要输出的是1 2 4 8 16 5 10 20。很多第一次做这题的人会不理解凭什么要倒着输出其实你看题面给的样例输出就知道了这个题目要求的就是倒序。为什么教材要这样设计因为正序输出太简单了边算边打印就行根本用不到数组。一旦要求倒序输出你就必须把中间每一步存下来等算完以后再从后往前访问。这正是数组最典型的应用场景。换句话说这道题不是考你冰雹猜想的数学性质而是考你会不会用一个容器装数据并且按指定方向遍历输出。这里我建议新手养成一个习惯拿到题先看样例把样例的输入输出手动推一遍。以20为例自己在草稿纸上写出变化链条再对照样例输出的顺序你立刻就会发现原来要倒着输出。这个习惯能帮你避开至少一半的读题坑。3. 可直接提交的代码C、Python与递归写法思路捋清楚以后实现就很直接了。用一个动态数组C的vector或者Python的list记录每一步的结果循环结束后从最后一个元素往前打印。3.1 C版vector存储与倒序打印我直接给出一个稳妥的C写法#include bits/stdc.h using namespace std; int main() { long long n; cin n; vectorlong long seq; seq.push_back(n); while (n ! 1) { if (n 1) { n 3 * n 1; } else { n / 2; } seq.push_back(n); } for (int i (int)seq.size() - 1; i 0; --i) { cout seq[i]; if (i 0) cout ; } cout \n; return 0; }几个细节说一下。判断奇数我用的是n 1这个位运算的意思是看二进制最低位是不是1等价于n % 2 1速度略快写法也干净。新人如果看不惯写成if (n % 2 1)完全没问题效果一样。输出的时候我在每个数后面判断一下如果不是最后一个数就输出空格否则输出换行。这样能保证行尾没有多余空格避免一些比较严苛的评测系统报Presentation Error。如果你懒得判断直接每个数后面跟一个空格大部分评测系统也能过但我不建议养成这种习惯。3.2 Python版注意整除运算Python写起来更短n int(input()) seq [n] while n ! 1: if n % 2 1: n 3 * n 1 else: n // 2 seq.append(n) print(*reversed(seq))Python这里有一个经典坑整除必须用//不能用/。/在Python3里得到的是浮点数一旦出现小数整个运算链就毁了。我用//保证结果一直是整数。另外print(*reversed(seq))会把列表展开成空格分隔的一行非常方便。Python的int没有固定位数限制不太存在C那种溢出问题但我在Python里也选择把所有中间结果放进列表因为Python同样需要倒序输出用列表天然合适。3.3 不用数组也能倒序递归写法这一节算一个延伸思考。如果你学过递归会发现在这里也可以不用数组靠递归的回溯特性实现倒序输出void dfs(long long n) { cout n; if (n 1) { cout \n; return; } cout ; if (n 1) dfs(3 * n 1); else dfs(n / 2); }调用dfs(20)会先打印20然后递归进去打印10再递归进去打印5……一直到打印1之后开始回溯。因为每一层都在进入下一层之前先打印了当前数所以最终屏幕上出现的顺序是20、10、5、16、8、4、2、1——注意这是正序不是题目要求的倒序。如果你非要靠递归实现倒序可以把输出语句放到递归调用之后也就是先递归到底再一层层回来的时候打印这样就能得到1、2、4、8、16、5、10、20的顺序。不过这道题我并不建议新手用递归。它放在数组章节核心考点就是数组的逆序访问用递归属于炫技而且递归初学时容易绕晕不如老老实实开个vector。等以后你熟练了再回头品味这些不同写法之间的联系也不迟。4. 最多的WA来源隐藏在3n1里的整数溢出这道题最大的坑不是输出顺序而是数据类型。我见过大量提交记录卡在这里小数据全对一提交不是WA就是TLE最后发现是int溢出。4.1 int上限与溢出后的诡异行为C里int是32位有符号整数上限是2147483647也就是大约21亿。题目给的n可能到10的9次方也就是10亿看起来10亿小于21亿读入没问题。但问题在于冰雹猜想变化过程中有一个关键操作奇数变3n1。假设n是10亿零1这是一个奇数。下一步需要计算3×10000000011结果是3000000004。这个数值已经超过了int能表示的最大正值2147483647。在常见的补码机器上这个值会环绕成一个负数。从语言标准的角度说有符号整数溢出属于未定义行为但在绝大多数实际编译环境中你看到的就是这个数字变成负数然后程序的行为开始失控。一旦n变成负数事情就麻烦了。下一次循环判断奇数时负数按位与1的结果仍然可能是1程序会继续执行3n1在负数的世界里越陷越深永远收敛不到1。你的while(n ! 1)会变成一个死循环最后评测系统报Time Limit Exceeded。这也是为什么有些同学测试小数据时没问题因为小数据的中间结果根本碰不到int上限一旦数据范围一大立刻翻车。4.2 溢出的边界值计算我帮你算一下这个溢出的临界点。int能表示的最大值是21474836473n1小于等于这个值的条件是3n1≤2147483647也就是n≤715827882。换句话说当n是奇数且大于715827882时第一步就会突破int上限。这个数字并不遥远。洛谷这题的数据范围如果给到10的9次方那么大量输入从一开始就会触发溢出。更麻烦的是冰雹猜想的中间值并不一定是先增大后减小那么温和它会在序列中反复冲高峰值可能远高于初始值。即使初始n只有几百万序列中间也可能出现比较大的数字。所以不管你输入是多少把所有中间变量和存储容器都放宽到long long是最稳妥的选择。4.3 从变量到容器全程long long不少新手认为只要循环里的n用long long数组用int存没事反正最终结果都是正数。这个想法是错的。你vector里存的虽然是long long计算出来的结果但如果vector 每个元素在存入时都会被截断成int溢出数据照样丢失后面的逆序输出自然也是错的。正确的做法是全程统一读入用long long循环变量用long longvector 递归参数也用long long。一层都不能漏。还有一点如果你用printf输出long long格式要写成%lld而不是%d漏了会得到莫名其妙的输出。如果不想纠结格式串直接用cout最省心。5. 提交失败对照表从输出顺序到边界特判做题最烦的不是不会而是本地全对一交就WA。我在洛谷讨论区看到过太多P5727的求助帖问题来来回回就那么几个。这里我整理一份对照表你提交前逐条检查能省下不少冤枉时间。症状大概率原因修复方式输出是正序样例都对不上没理解倒序输出用数组存储最后从后往前遍历输入1时输出为空先进入循环再存数先把初始n存入序列再开始循环输出结果少了初始数字忘记把起始n push进去循环前先push_back(n)运行超时int溢出导致负数死循环全程改用long long答案错误且数值很大很怪vector元素还是int发生截断容器类型也改成long long行尾多空格被判格式错输出循环逻辑不严谨最后一个元素后换行而非空格小数据全对大数据WA边界条件没覆盖手动测n1、n715827883等5.1 常见错误与修复方式第2条输入1时输出为空值得单独说一下。如果代码写成这样先while(n ! 1)再存结果那么当n本来就等于1时循环体一次都不执行序列为空输出自然什么都没有。实际题目要求输出1因为变化过程就一个数1。解决方法是先把初始的n存进序列或者对n1单独特判输出1。关于正序输出这个问题我当年第一次做也踩了。我当时的想法是题面明明说输出变化过程那我一步一步打印有什么问题后来看了样例输出才发现它给的是反过来的。这个经历让我养成一个习惯任何题目先看样例再动手写代码。样例不会骗人它比题面的大段描述更容易暴露真实要求。5.2 一套完整的自测流程我推荐新手在提交前按下面的流程自测一遍尤其是对于P5727这种入口简单但细节多的题第一步先在草稿纸上手推一个简单样例。比如输入20手动算出20→10→5→16→8→4→2→1然后模拟代码输出看看是否得到1 2 4 8 16 5 10 20。如果这一步对不上说明思路就有问题先别急着提交。第二步测试边界n1。期望输出是1。第三步测试一个稍微大一点的奇数比如n1000000001。这一步是为了检查你的程序是否会死循环如果用的是long long很快就能出结果。第四步把代码里的调试输出全部删掉。有些同学喜欢在循环里加cerr n endl来看中间过程这个可以但提交前记得清理。cerr的输出会走标准错误流虽然不影响答案但是会在评测系统里留下多余内容万一把错误流和答案流混在一起后果很麻烦。6. 这类模拟递推题学会一个套路就能秒一片P5727做完以后我强烈建议你别急着继续往下刷停下来复盘一下这道题背后的通用解法。信息学竞赛里有一大类题目可以归为模拟递推 反序输出它们的套路几乎完全一样。6.1 通用三步法第一步把题目规则机械翻译成循环。不要思考任何优化先把把奇数变3n1、偶数除以2直到1这种规则一字不落地写成代码。模拟题最忌讳自作聪明跳过某些轮次你就是老实按规则走结果通常不会错。第二步根据数据范围确定类型。这是很多人直接忽略的一步。看到数据范围可能超过int就要立刻把long long拿出来。我建议新手开一个习惯只要是洛谷题除非确定范围很小否则变量类型一律往大里开。反正long long在64位机器上和int性能差距很小不存在超时风险。第三步判断输出方向。题目要求正序输出你就边算边打印题目要求倒序输出你就开一个数组或vector存下来最后逆序遍历。很多题目会把输出顺序当成一个隐含考点你多留一个心眼就能少错一次。6.2 后续可以怎么扩展这套先存储再逆序的套路本质上是在练习结果的呈现顺序不一定要等于计算顺序。你以后会遇到很多变形题有的要求把计算过程存下来后按奇偶分组输出有的要求把中间结果插入到某个特定位置再输出还有的会要求你同时记录每一步的序号。举个很常见的例子类似P5727的题目题目不会明说请倒序输出而是给一个看起来莫名其妙的样例输出让你自己推断。这时候读样例就成了最重要的能力。我见过不少选手不是不会代码而是花了半小时还没搞懂样例为什么长那样。信息学竞赛里读题能力本身就是一道隐形的坎。另外如果哪天你学到递归可以回来看看这题。你会发现用递归做倒序输出比数组更优雅但你要理解递归的调用栈本质上也是一个数组它同样是在保存每一层的信息最后从栈顶一层层弹出来。数据结构学到后面你会越来越觉得数组存一下再倒着看这个思想极其基础极其重要几乎所有领域都在用。最后分享一点我个人的做题体会。P5727这种入门题你花一下午把各种奇怪写法都试一遍其实比快速AC更有价值。试着用int写一版亲眼看看它怎么爆试着边算边打印看看正序和倒序的区别试着把vector换成固定长度数组看看越界报错是什么样的。这题考的不是你能不能AC而是你有没有真正理解模拟、存储和输出之间的配合逻辑。刷题数量固然重要但像这种信息量集中的好题多折腾几次比盲目刷十道简单题管用。