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