1. 這道深基題卡住了多少人的第一次提交如果你在洛谷搜索框里輸入P5727大概率會看到兩種帖子一種人貼出自己正序輸出的代碼然后配一句為什么全WA另一種人在評論區(qū)回復(fù)你把輸出反過來就過了。這道題作為《深入淺出程序設(shè)計競賽》數(shù)組章節(jié)的例3表面上是模擬冰雹猜想的變化過程實際上真正想讓你練的是用數(shù)組存下中間結(jié)果再反著打印。很多剛接觸信息學(xué)奧賽的新手前面幾道題做得順風(fēng)順水到這一題突然被倒序輸出卡住其實不是不會模擬而是沒讀懂題面想要什么。先把這個題的核心價值說清楚P5727是一道純粹練遞推/模擬 容器存儲的入門題適合剛學(xué)完循環(huán)、正準備接觸數(shù)組的同學(xué)。它不考任何高深算法時間復(fù)雜度幾乎可以忽略但它在讀題和邊界處理兩個維度上非常典型。你只要能把這題吃透后面遇到先計算再逆序輸出這類問題基本上不用再花時間琢磨。1.1 冰雹猜想到底是什么冰雹猜想也叫科拉茨猜想、3n1猜想、角谷猜想。規(guī)則很簡單給出一個正整數(shù)如果它是奇數(shù)就乘以3再加1如果它是偶數(shù)就直接除以2。重復(fù)執(zhí)行這兩條規(guī)則最終一定會落到1。舉個例子從20開始20是偶數(shù)除以2得1010是偶數(shù)除以2得55是奇數(shù)乘3加1得1616是偶數(shù)除以2得88除以2得44除以2得22除以2得1。整個過程寫下來就是20→10→5→16→8→4→2→1。這個數(shù)列跳來跳去一會兒沖高一會兒回落很像冰雹在云層里上下翻滾所以叫冰雹猜想。雖然數(shù)學(xué)家到現(xiàn)在都沒完全證明所有正整數(shù)最終都會到1但在洛谷這道題給定的數(shù)據(jù)范圍內(nèi)這個性質(zhì)是必然成立的所以放心大膽模擬就可以了不需要擔心循環(huán)跳不出來。1.2 為什么叫深基5.例3熟悉洛谷的同學(xué)都知道深基指的是《深入淺出程序設(shè)計競賽》這套教材。第5章講的是數(shù)組例3就是這一題。教材把它放在數(shù)組章節(jié)意圖特別明顯希望你能把每一輪變化后的數(shù)字按順序存起來最后用數(shù)組的逆序遍歷把結(jié)果倒過來輸出。如果你只用一個變量從頭算到尾邊算邊輸出那你得到的是正序結(jié)果正好和題目要求相反。這道題的數(shù)據(jù)范圍我記得是1到10的9次方這個級別。這個范圍很有意思正好踩在C里int類型可能溢出的邊緣上后面我會專門花一章講這個坑。入門選手如果只盯著模擬過程這件事很可能在本地測試小數(shù)據(jù)時全都對一提交就超時或WA根源往往不在算法而在數(shù)據(jù)類型的選用。2. 題面真正的要求不是把過程算出來而是倒著說出來讀題是信息學(xué)競賽里最容易翻車的一步P5727就是活生生的例子。很多人看完題目描述覺得哦不就是把變化過程輸出嘛直接寫一個while循環(huán)每變化一步就打印一個數(shù)結(jié)果樣例都過不了。2.1 規(guī)則拆分與最容易寫錯的循環(huán)先把規(guī)則拆成機械的步驟讀入正整數(shù)n把n放入過程序列只要n不等于1就重復(fù)如果n是奇數(shù)把n改成3*n1如果n是偶數(shù)把n改成n/2把新的n放入過程序列把過程序列倒序輸出有一個細節(jié)值得提醒判斷奇偶的依據(jù)是當前這一輪的n值而不是初始值。也就是說n在變化過程中可能一會兒奇一會兒偶循環(huán)體內(nèi)每次進入都要重新判斷。有的新手會把奇偶判斷放在循環(huán)外面只根據(jù)初始n決定后面一路怎么變這顯然是錯的。還有一個新手很容易忽略的點先把初始的n存進序列再進入循環(huán)。如果你先把n算一步再存或者完全忘了存初始值輸出結(jié)果就會少一個數(shù)字。不信你試一下輸入20如果忘記存初始的20最終輸出就少了一項提交必WA。2.2 倒序輸出為什么這道題放在數(shù)組這一章我們繼續(xù)拿20做例子。整個過程是20→10→5→16→8→4→2→1按照題目的輸出要求你需要輸出的是1 2 4 8 16 5 10 20。很多第一次做這題的人會不理解憑什么要倒著輸出其實你看題面給的樣例輸出就知道了這個題目要求的就是倒序。為什么教材要這樣設(shè)計因為正序輸出太簡單了邊算邊打印就行根本用不到數(shù)組。一旦要求倒序輸出你就必須把中間每一步存下來等算完以后再從后往前訪問。這正是數(shù)組最典型的應(yīng)用場景。換句話說這道題不是考你冰雹猜想的數(shù)學(xué)性質(zhì)而是考你會不會用一個容器裝數(shù)據(jù)并且按指定方向遍歷輸出。這里我建議新手養(yǎng)成一個習(xí)慣拿到題先看樣例把樣例的輸入輸出手動推一遍。以20為例自己在草稿紙上寫出變化鏈條再對照樣例輸出的順序你立刻就會發(fā)現(xiàn)原來要倒著輸出。這個習(xí)慣能幫你避開至少一半的讀題坑。3. 可直接提交的代碼C、Python與遞歸寫法思路捋清楚以后實現(xiàn)就很直接了。用一個動態(tài)數(shù)組C的vector或者Python的list記錄每一步的結(jié)果循環(huán)結(jié)束后從最后一個元素往前打印。3.1 C版vector存儲與倒序打印我直接給出一個穩(wěn)妥的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; }幾個細節(jié)說一下。判斷奇數(shù)我用的是n 1這個位運算的意思是看二進制最低位是不是1等價于n % 2 1速度略快寫法也干凈。新人如果看不慣寫成if (n % 2 1)完全沒問題效果一樣。輸出的時候我在每個數(shù)后面判斷一下如果不是最后一個數(shù)就輸出空格否則輸出換行。這樣能保證行尾沒有多余空格避免一些比較嚴苛的評測系統(tǒng)報Presentation Error。如果你懶得判斷直接每個數(shù)后面跟一個空格大部分評測系統(tǒng)也能過但我不建議養(yǎng)成這種習(xí)慣。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這里有一個經(jīng)典坑整除必須用//不能用/。/在Python3里得到的是浮點數(shù)一旦出現(xiàn)小數(shù)整個運算鏈就毀了。我用//保證結(jié)果一直是整數(shù)。另外print(*reversed(seq))會把列表展開成空格分隔的一行非常方便。Python的int沒有固定位數(shù)限制不太存在C那種溢出問題但我在Python里也選擇把所有中間結(jié)果放進列表因為Python同樣需要倒序輸出用列表天然合適。3.3 不用數(shù)組也能倒序遞歸寫法這一節(jié)算一個延伸思考。如果你學(xué)過遞歸會發(fā)現(xiàn)在這里也可以不用數(shù)組靠遞歸的回溯特性實現(xiàn)倒序輸出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); }調(diào)用dfs(20)會先打印20然后遞歸進去打印10再遞歸進去打印5……一直到打印1之后開始回溯。因為每一層都在進入下一層之前先打印了當前數(shù)所以最終屏幕上出現(xiàn)的順序是20、10、5、16、8、4、2、1——注意這是正序不是題目要求的倒序。如果你非要靠遞歸實現(xiàn)倒序可以把輸出語句放到遞歸調(diào)用之后也就是先遞歸到底再一層層回來的時候打印這樣就能得到1、2、4、8、16、5、10、20的順序。不過這道題我并不建議新手用遞歸。它放在數(shù)組章節(jié)核心考點就是數(shù)組的逆序訪問用遞歸屬于炫技而且遞歸初學(xué)時容易繞暈不如老老實實開個vector。等以后你熟練了再回頭品味這些不同寫法之間的聯(lián)系也不遲。4. 最多的WA來源隱藏在3n1里的整數(shù)溢出這道題最大的坑不是輸出順序而是數(shù)據(jù)類型。我見過大量提交記錄卡在這里小數(shù)據(jù)全對一提交不是WA就是TLE最后發(fā)現(xiàn)是int溢出。4.1 int上限與溢出后的詭異行為C里int是32位有符號整數(shù)上限是2147483647也就是大約21億。題目給的n可能到10的9次方也就是10億看起來10億小于21億讀入沒問題。但問題在于冰雹猜想變化過程中有一個關(guān)鍵操作奇數(shù)變3n1。假設(shè)n是10億零1這是一個奇數(shù)。下一步需要計算3×10000000011結(jié)果是3000000004。這個數(shù)值已經(jīng)超過了int能表示的最大正值2147483647。在常見的補碼機器上這個值會環(huán)繞成一個負數(shù)。從語言標準的角度說有符號整數(shù)溢出屬于未定義行為但在絕大多數(shù)實際編譯環(huán)境中你看到的就是這個數(shù)字變成負數(shù)然后程序的行為開始失控。一旦n變成負數(shù)事情就麻煩了。下一次循環(huán)判斷奇數(shù)時負數(shù)按位與1的結(jié)果仍然可能是1程序會繼續(xù)執(zhí)行3n1在負數(shù)的世界里越陷越深永遠收斂不到1。你的while(n ! 1)會變成一個死循環(huán)最后評測系統(tǒng)報Time Limit Exceeded。這也是為什么有些同學(xué)測試小數(shù)據(jù)時沒問題因為小數(shù)據(jù)的中間結(jié)果根本碰不到int上限一旦數(shù)據(jù)范圍一大立刻翻車。4.2 溢出的邊界值計算我?guī)湍闼阋幌逻@個溢出的臨界點。int能表示的最大值是21474836473n1小于等于這個值的條件是3n1≤2147483647也就是n≤715827882。換句話說當n是奇數(shù)且大于715827882時第一步就會突破int上限。這個數(shù)字并不遙遠。洛谷這題的數(shù)據(jù)范圍如果給到10的9次方那么大量輸入從一開始就會觸發(fā)溢出。更麻煩的是冰雹猜想的中間值并不一定是先增大后減小那么溫和它會在序列中反復(fù)沖高峰值可能遠高于初始值。即使初始n只有幾百萬序列中間也可能出現(xiàn)比較大的數(shù)字。所以不管你輸入是多少把所有中間變量和存儲容器都放寬到long long是最穩(wěn)妥的選擇。4.3 從變量到容器全程long long不少新手認為只要循環(huán)里的n用long long數(shù)組用int存沒事反正最終結(jié)果都是正數(shù)。這個想法是錯的。你vector里存的雖然是long long計算出來的結(jié)果但如果vector 每個元素在存入時都會被截斷成int溢出數(shù)據(jù)照樣丟失后面的逆序輸出自然也是錯的。正確的做法是全程統(tǒng)一讀入用long long循環(huán)變量用long longvector 遞歸參數(shù)也用long long。一層都不能漏。還有一點如果你用printf輸出long long格式要寫成%lld而不是%d漏了會得到莫名其妙的輸出。如果不想糾結(jié)格式串直接用cout最省心。5. 提交失敗對照表從輸出順序到邊界特判做題最煩的不是不會而是本地全對一交就WA。我在洛谷討論區(qū)看到過太多P5727的求助帖問題來來回回就那么幾個。這里我整理一份對照表你提交前逐條檢查能省下不少冤枉時間。癥狀大概率原因修復(fù)方式輸出是正序樣例都對不上沒理解倒序輸出用數(shù)組存儲最后從后往前遍歷輸入1時輸出為空先進入循環(huán)再存數(shù)先把初始n存入序列再開始循環(huán)輸出結(jié)果少了初始數(shù)字忘記把起始n push進去循環(huán)前先push_back(n)運行超時int溢出導(dǎo)致負數(shù)死循環(huán)全程改用long long答案錯誤且數(shù)值很大很怪vector元素還是int發(fā)生截斷容器類型也改成long long行尾多空格被判格式錯輸出循環(huán)邏輯不嚴謹最后一個元素后換行而非空格小數(shù)據(jù)全對大數(shù)據(jù)WA邊界條件沒覆蓋手動測n1、n715827883等5.1 常見錯誤與修復(fù)方式第2條輸入1時輸出為空值得單獨說一下。如果代碼寫成這樣先while(n ! 1)再存結(jié)果那么當n本來就等于1時循環(huán)體一次都不執(zhí)行序列為空輸出自然什么都沒有。實際題目要求輸出1因為變化過程就一個數(shù)1。解決方法是先把初始的n存進序列或者對n1單獨特判輸出1。關(guān)于正序輸出這個問題我當年第一次做也踩了。我當時的想法是題面明明說輸出變化過程那我一步一步打印有什么問題后來看了樣例輸出才發(fā)現(xiàn)它給的是反過來的。這個經(jīng)歷讓我養(yǎng)成一個習(xí)慣任何題目先看樣例再動手寫代碼。樣例不會騙人它比題面的大段描述更容易暴露真實要求。5.2 一套完整的自測流程我推薦新手在提交前按下面的流程自測一遍尤其是對于P5727這種入口簡單但細節(jié)多的題第一步先在草稿紙上手推一個簡單樣例。比如輸入20手動算出20→10→5→16→8→4→2→1然后模擬代碼輸出看看是否得到1 2 4 8 16 5 10 20。如果這一步對不上說明思路就有問題先別急著提交。第二步測試邊界n1。期望輸出是1。第三步測試一個稍微大一點的奇數(shù)比如n1000000001。這一步是為了檢查你的程序是否會死循環(huán)如果用的是long long很快就能出結(jié)果。第四步把代碼里的調(diào)試輸出全部刪掉。有些同學(xué)喜歡在循環(huán)里加cerr n endl來看中間過程這個可以但提交前記得清理。cerr的輸出會走標準錯誤流雖然不影響答案但是會在評測系統(tǒng)里留下多余內(nèi)容萬一把錯誤流和答案流混在一起后果很麻煩。6. 這類模擬遞推題學(xué)會一個套路就能秒一片P5727做完以后我強烈建議你別急著繼續(xù)往下刷停下來復(fù)盤一下這道題背后的通用解法。信息學(xué)競賽里有一大類題目可以歸為模擬遞推 反序輸出它們的套路幾乎完全一樣。6.1 通用三步法第一步把題目規(guī)則機械翻譯成循環(huán)。不要思考任何優(yōu)化先把把奇數(shù)變3n1、偶數(shù)除以2直到1這種規(guī)則一字不落地寫成代碼。模擬題最忌諱自作聰明跳過某些輪次你就是老實按規(guī)則走結(jié)果通常不會錯。第二步根據(jù)數(shù)據(jù)范圍確定類型。這是很多人直接忽略的一步。看到數(shù)據(jù)范圍可能超過int就要立刻把long long拿出來。我建議新手開一個習(xí)慣只要是洛谷題除非確定范圍很小否則變量類型一律往大里開。反正long long在64位機器上和int性能差距很小不存在超時風(fēng)險。第三步判斷輸出方向。題目要求正序輸出你就邊算邊打印題目要求倒序輸出你就開一個數(shù)組或vector存下來最后逆序遍歷。很多題目會把輸出順序當成一個隱含考點你多留一個心眼就能少錯一次。6.2 后續(xù)可以怎么擴展這套先存儲再逆序的套路本質(zhì)上是在練習(xí)結(jié)果的呈現(xiàn)順序不一定要等于計算順序。你以后會遇到很多變形題有的要求把計算過程存下來后按奇偶分組輸出有的要求把中間結(jié)果插入到某個特定位置再輸出還有的會要求你同時記錄每一步的序號。舉個很常見的例子類似P5727的題目題目不會明說請倒序輸出而是給一個看起來莫名其妙的樣例輸出讓你自己推斷。這時候讀樣例就成了最重要的能力。我見過不少選手不是不會代碼而是花了半小時還沒搞懂樣例為什么長那樣。信息學(xué)競賽里讀題能力本身就是一道隱形的坎。另外如果哪天你學(xué)到遞歸可以回來看看這題。你會發(fā)現(xiàn)用遞歸做倒序輸出比數(shù)組更優(yōu)雅但你要理解遞歸的調(diào)用棧本質(zhì)上也是一個數(shù)組它同樣是在保存每一層的信息最后從棧頂一層層彈出來。數(shù)據(jù)結(jié)構(gòu)學(xué)到后面你會越來越覺得數(shù)組存一下再倒著看這個思想極其基礎(chǔ)極其重要幾乎所有領(lǐng)域都在用。最后分享一點我個人的做題體會。P5727這種入門題你花一下午把各種奇怪寫法都試一遍其實比快速AC更有價值。試著用int寫一版親眼看看它怎么爆試著邊算邊打印看看正序和倒序的區(qū)別試著把vector換成固定長度數(shù)組看看越界報錯是什么樣的。這題考的不是你能不能AC而是你有沒有真正理解模擬、存儲和輸出之間的配合邏輯。刷題數(shù)量固然重要但像這種信息量集中的好題多折騰幾次比盲目刷十道簡單題管用。