含章信競周賽J01題解

含章信競周賽HanZJ01題解本周競賽題目難度為CSP_J組復(fù)賽T1/T2難度。算法為模擬算法。三道題，用時120分鐘。題目名稱：謝弗涅的猜想題號：HanZJ01T1算法分類：模擬算法聰明的謝弗涅在學(xué)習(xí)數(shù)列的時候發(fā)現(xiàn)一個有趣的現(xiàn)象：從正整數(shù)n開始，如果n是偶數(shù)，就將它除以2；如果n是奇數(shù)，就將它乘以3再加1。用得到的新值不斷重復(fù)上述步驟，最終都會得到1。例如，n=22時，會得到如下序列：22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1。謝弗涅猜想，對于任意正整數(shù)n，該算法總能終止于n=1。到目前位置該算法在1e6的數(shù)值內(nèi)都是正確的。對于給定的n，該序列中的元素的個數(shù)，包括1，被稱為該數(shù)字的循環(huán)節(jié)長度。如上例中的22，其循環(huán)節(jié)長度為16。輸入兩個正整數(shù)i,j（0<i<j<=1e6）。計算區(qū)間[i,j]內(nèi)整數(shù)的循環(huán)節(jié)長度最大值。輸入由多組樣例組成，第一行為正整數(shù)T（1<=T<=100）。第二行為兩個正整數(shù)i,j，定義如題。對于每個輸入，在不同的行輸出一個正整數(shù)。輸入樣例：21101030輸出樣例：20112解題思路：此題為角谷猜想得板子題。唯一變化是角谷猜想常態(tài)下會要求輸出路徑，此題僅要求輸出路徑長度，即循環(huán)節(jié)。此題解題時須注意多樣例初始化問題。解題代碼如下：題目名稱：謝弗涅的掃雷游戲題號：HanZJ01T2算法分類：模擬算法最近謝弗涅迷戀上了掃雷游戲。游戲的目標(biāo)是找到一個n*m矩陣中的所有地雷。在游戲中，每個單元格有8個相鄰的各自，謝弗涅需要計算出每個單元格周圍地雷的個數(shù)。如下例是一個4*4的單元格，用*表示地雷，左側(cè)為游戲初始的樣子，右側(cè)為計算出的結(jié)果。輸入將包含若干個矩陣。對于每一個矩陣，第一行將包含兩個正整數(shù)n,m(0<n,m<=100)，表示矩陣的行列數(shù)。接下來n行，表示矩陣。其中*表示地雷，#表示安全區(qū)。當(dāng)n=m=0時，輸入結(jié)束。程序不應(yīng)處理這一行。對于每個輸入的矩陣，同樣輸出一個矩陣。輸出矩陣中，以數(shù)字代替#，數(shù)字要求如題意。*單元還以*表示。兩個矩陣之間應(yīng)以一個空行隔開。*注：本編譯器不支持while(1)寫法。輸入樣例：44*########*######35**#########*###00輸出樣例：*10022101*101110**100332001*100解題思路：此題為模擬算法，解法就是將題目文字描述的掃雷過程代碼復(fù)原即可。需要注意的是，8個方向的坐標(biāo)調(diào)整系不要寫錯。同時需要注意，多樣例中圖形矩陣的初始化問題。解題代碼如下：題目名稱：謝弗涅的猜想（J01T3）題號：HanZJ01T3算法分類：模擬算法謝弗涅學(xué)校每年的組織同學(xué)去不同的地方旅游。學(xué)生們要均攤所有的旅費。同學(xué)們在旅行中會墊付一些費用，并在旅行結(jié)束后計算。計費原則是多退少補，每個同學(xué)的支出差距在1分錢以內(nèi)。同學(xué)們互相轉(zhuǎn)錢是件很麻煩的事，所以你的任務(wù)是在一份清單的基礎(chǔ)上，計算出為了平攤費用所必須進(jìn)行的最小總“交易”額。輸入由若干組組成。每組第一行一個正整數(shù)n(1<=n<=1000)，表示這次旅行由n名同學(xué)組成。一下n行，包含了每一個同學(xué)墊付的費用pi(0<pi<=1e5)，精確到分。最后一行由一個0結(jié)束。對于每組數(shù)據(jù)只輸出一行，為最小交易額度，精確到分。輸入樣例：310.00