【正文】 【問題描述】Jam 是個喜歡標(biāo)新立異的科學(xué)怪人。他不使用阿拉伯?dāng)?shù)字計數(shù)，而是使用小寫英文字母計數(shù)，他覺得這樣做，會使世界更加豐富多彩。在他的計數(shù)法中，每個數(shù)字的位數(shù)都是相同的（使用相同個數(shù)的字母），英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱為 Jam數(shù)字。在 Jam 數(shù)字中，每個字母互不相同，而且從左到右是嚴(yán)格遞增的。每次，Jam 還指定使用字母的范圍，例如，從 2 到 10，表示只能使用{b,c,d,e,f,g,h,i,j}這些字母。如果再規(guī)定位數(shù)為 5，那么，緊接在 Jam 數(shù)字“bdfij ”之后的數(shù)字應(yīng)該是“bdghi”。（如果我們用 U、V 依次表示 Jam 數(shù)字“bdfij”與“bdghi”，則 UV span，且不存在 Jam 數(shù)字 P，使 UPV span）。你的任務(wù)是：對于從文件讀入的一個 Jam 數(shù)字，按順序輸出緊接在后面的 5 個 Jam 數(shù)字，如果后面沒有那么多 Jam 數(shù)字，那么有幾個就輸出幾個?！据斎胛募?37 / 56輸入文件 有 2 行，第 1 行為 3 個正整數(shù)，用一個空格隔開：s t w（其中 s 為所使用的最小的字母的序號，t 為所使用的最大的字母的序號。w 為數(shù)字的位數(shù)，這 3 個數(shù)滿足： 1≤sT span≤26, 2≤w ≤ts ） 第 2 行為具有 w 個小寫字母的字符串，為一個符合要求的 Jam 數(shù)字。所給的數(shù)據(jù)都是正確的，不必驗證?！据敵鑫募枯敵鑫募? 最多為 5 行，為緊接在輸入的 Jam 數(shù)字后面的5 個 Jam 數(shù)字，如果后面沒有那么多 Jam 數(shù)字，那么有幾個就輸出幾個。每行只輸出一個 Jam 數(shù)字，是由 w 個小寫字母組成的字符串，不要有多余的空格?！据斎霕永? 2 10 5 bdfij【輸出樣例】bdghibdghjbdgijbdhijbefgh （）【問題描述】 38 / 56給定一個正整數(shù) k(3≤k ≤15), 把所有 k 的方冪及所有有限個互不相等的k 的方冪之和構(gòu)成一個遞增的序列，例如，當(dāng) k=3 時，這個序列是：1，3，4，9，10，12，13 ，…（該序列實際上就是：3 0，3 1，3 0+31，3 2，3 0+32，3 1+32，3 0+31+32，…）請你求出這個序列的第 N 項的值（用 10 進(jìn)制數(shù)表示）。例如，對于 k=3，N=100，正確答案應(yīng)該是 981?！据斎胛募枯斎胛募? 只有 1 行，為 2 個正整數(shù)，用一個空格隔開：k N（k、N 的含義與上述的問題描述一致，且 3≤k≤ 15，10≤N≤1000 ）?！据敵鑫募枯敵鑫募? 為計算結(jié)果，是一個正整數(shù)（在所有的測試數(shù)據(jù)中，結(jié)果均不超過 *109）。（整數(shù)前不要有空格和其他符號）?！据斎霕永? 3 100【輸出樣例】9812022 年 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2022）復(fù)賽 39 / 56提高組題目一覽題目名稱 統(tǒng)計數(shù)字 字符串的展開 矩陣取數(shù)游戲 樹網(wǎng)的核代號 count expand game core輸入文件 輸出文件 時限 1 秒 1 秒 1 秒 1 秒(2022 年 11 月 17 日 3 小時完成)說明：1. 文件名（程序名和輸入輸出文件名）必須使用小寫2. C/C++中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時的返回值必須是 0。3. 全國統(tǒng)一評測時采用的機器參考配置為：CPU ，內(nèi)存 256M。 40 / 561．統(tǒng)計數(shù)字()【問題描述】某次科研調(diào)查時得到了 n 個自然數(shù)，每個數(shù)均不超過 1500000000（*10 9） 。已知不相同的數(shù)不超過 10000 個，現(xiàn)在需要統(tǒng)計這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計結(jié)果。【輸入】 輸入文件 包含 n+1 行： 第 1 行是整數(shù) n，表示自然數(shù)的個數(shù)。 第 2~n+1 行每行一個自然數(shù)。【輸出】 輸出文件 包含 m 行（m 為 n 個自然數(shù)中不相同數(shù)的個數(shù)） ，按照自然數(shù)從小到大的順序輸出。每行輸出兩個整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個空格隔開?！据斎胼敵鰳永?82424510021002 34 25 1100 2【限制】 40%的數(shù)據(jù)滿足：1= n=1000 80%的數(shù)據(jù)滿足：1= n=50000 100%的數(shù)據(jù)滿足：1= n=202200，每個數(shù)均不超過 1 500 000 000（*10 9）2．字符串的展開()【問題描述】在初賽普及組的“閱讀程序?qū)懡Y(jié)果”的問題中，我們曾給出一個字符串展開的例子：如果在輸入的字符串中，含有類似于“dh”或“48 ”的子串，我們就把它當(dāng)作一種簡寫，輸出時，用連續(xù)遞增的字母或數(shù)字串替代其中的減號，即，將上面兩個子串分別輸出為“defgh”和“ 45678”。在本題中，我們通過增加一些參數(shù)的設(shè)置，使字符串的展開更為靈活。具體約定如下：（1）遇到下面的情況需要做字符串的展開：在輸入的字符串中，出現(xiàn)了減號“” ，減 41 / 56號兩側(cè)同為小寫字母或同為數(shù)字，且按照 ASCII 碼的順序，減號右邊的字符嚴(yán)格大于左邊的字符。（2）參數(shù) p1：展開方式。p1=1 時，對于字母子串，填充小寫字母；p1=2 時，對于字母子串，填充大寫字母。這兩種情況下數(shù)字子串的填充方式相同。p1=3 時，不論是字母子串還是數(shù)字子串，都用與要填充的字母個數(shù)相同的星號“*”來填充。（3）參數(shù) p2：填充字符的重復(fù)個數(shù)。p2=k 表示同一個字符要連續(xù)填充 k 個。例如，當(dāng) p2=3 時，子串 “dh”應(yīng)擴展為“deeefffgggh ”。減號兩側(cè)的字符不變。（4）參數(shù) p3：是否改為逆序：p3=1 表示維持原有順序，p3=2 表示采用逆序輸出，注意這時仍然不包括減號兩端的字符。例如當(dāng) p1=p2=p3=2 時，子串“dh”應(yīng)擴展為“dggffeeh”。（5）如果減號右邊的字符恰好是左邊字符的后繼，只刪除中間的減號，例如：“de”應(yīng)輸出為“ de”， “34”應(yīng)輸出為“34” 。如果減號右邊的字符按照 ASCII 碼的順序小于或等于左邊字符，輸出時，要保留中間的減號，例如：“dd ”應(yīng)輸出為“dd ”， “31”應(yīng)輸出為“31” ?！据斎搿枯斎胛募? 包括兩行：第 1 行為用空格隔開的 3 個正整數(shù)，依次表示參數(shù) p1，p2，p3。第 2 行為一行字符串，僅由數(shù)字、小寫字母和減號“”組成。行首和行末均無空格?！据敵觥枯敵鑫募? 只有一行，為展開后的字符串?！据斎胼敵鰳永?1】 1 2 1abcsw12349s4zzabcsttuuvvw1234556677889s4zz【輸入輸出樣例 2】 2 3 2addaCCCBBBdd【輸入輸出樣例 3】 3 4 2dijkstra26dijkstra2************6【限制】 40%的數(shù)據(jù)滿足：字符串長度不超過 5 100%的數(shù)據(jù)滿足：1=p1=3, 1=p2=8, 1=p3=2。字符串長度不超過 100 42 / 563. 矩陣取數(shù)游戲()【問題描述】 帥帥經(jīng)常跟同學(xué)玩一個矩陣取數(shù)游戲：對于一個給定的 n*m 的矩陣，矩陣中的每個元素 aij均為非負(fù)整數(shù)。游戲規(guī)則如下：1. 每次取數(shù)時須從每行各取走一個元素，共 n 個。m 次后取完矩陣所有元素；2. 每次取走的各個元素只能是該元素所在行的行首或行尾；3. 每次取數(shù)都有一個得分值，為每行取數(shù)的得分之和，每行取數(shù)的得分 = 被取走的元素值*2 i，其中 i 表示第 i 次取數(shù)（從 1 開始編號） ；4. 游戲結(jié)束總得分為 m 次取數(shù)得分之和。帥帥想請你幫忙寫一個程序，對于任意矩陣，可以求出取數(shù)后的最大得分?！据斎搿? 輸入文件 包括 n+1 行： 第 1 行為兩個用空格隔開的整數(shù) n 和 m。 第 2~n+1 行為 n*m 矩陣，其中每行有 m 個用單個空格隔開的非負(fù)整數(shù)?！据敵觥? 輸出文件 僅包含 1 行，為一個整數(shù)，即輸入矩陣取數(shù)后的最大得分。【輸入輸出樣例 1】 2 31 2 33 4 282【輸入輸出樣例 1 解釋】第 1 次：第 1 行取行首元素，第 2 行取行尾元素，本次得分為 1*21+2*21=6第 2 次：兩行均取行首元素，本次得分為 2*22+3*22=20第 3 次：得分為 3*23+4*23=56?？偟梅譃?6+20+56=82【輸入輸出樣例 2】 1 44 5 0 5122【輸入輸出樣例 3】 2 1096 56 54 46 86 12 23 88 80 4316 95 18 29 30 53 88 83 64 67316994【限制】 60%的數(shù)據(jù)滿足：1= n, m=30, 答案不超過 1016 100%的數(shù)據(jù)滿足：1= n, m=80, 0=aij=1000 43 / 564. 樹網(wǎng)的核()【問題描述】設(shè) T=(V, E, W) 是一個無圈且連通的無向圖（也稱為無根樹） ，每條邊帶有正整數(shù)的權(quán)，我們稱 T 為樹網(wǎng)（treework） ，其中 V, E 分別表示結(jié)點與邊的集合，W 表示各邊長度的集合，并設(shè) T 有 n 個結(jié)點。路徑：樹網(wǎng)中任何兩結(jié)點 a,b 都存在唯一的一條簡單路徑，用 d(a,b)表示以 a,b 為端點的路徑的長度，它是該路徑上各邊長度之和。我們稱 d(a,b)為 a,b 兩結(jié)點間的距離。一點 v 到一條路徑 P 的距離為該點與 P 上的最近的結(jié)點的距離：d(v， P)=min{d(v， u)， u 為路徑 P 上的結(jié)點}。樹網(wǎng)的直徑：樹網(wǎng)中最長的路徑稱為樹網(wǎng)的直徑。對于給定的樹網(wǎng) T，直徑不一定是唯一的，但可以證明：各直徑的中點（不一定恰好是某個結(jié)點，可能在某條邊的內(nèi)部）是唯一的，我們稱該點為樹網(wǎng)的中心。偏心距 ECC(F)：樹網(wǎng) T 中距路徑 F 最遠(yuǎn)的結(jié)點到路徑 F 的距離，即。} ),(max{)(VvdEC??任務(wù)：對于給定的樹網(wǎng) T=(V, E,W)和非負(fù)整數(shù) s，求一個路徑 F，它是某直徑上的一段路徑（該路徑兩端均為樹網(wǎng)中的結(jié)點） ，其長度不超過 s（可以等于 s） ，使偏心距ECC(F)最小。我們稱這個路徑為樹網(wǎng) T=(V,E,W)的核（ Core） 。必要時，F(xiàn) 可以退化為某個結(jié)點。一般來說，在上述定義下，核不一定只有一個，但最小偏心距是唯一的。下面的圖給出了樹網(wǎng)的一個實例。圖中，AB 與 AC 是兩條直徑，長度均為 20。點W 是樹網(wǎng)的中心， EF 邊的長度為 5。如果指定 s=11，則樹網(wǎng)的核為路徑 DEFG（也可以取為路徑 DEF） ，偏心距為 8。如果指定 s=0（或 s=s=2） ，則樹網(wǎng)的核為結(jié)點 F，偏心距為 12?！据斎搿? 輸入文件 包含 n 行：第 1 行，兩個正整數(shù) n 和 s，中間用一個空格隔開。其中 n 為樹網(wǎng)結(jié)點的個數(shù)，s 為 44 / 56樹網(wǎng)的核的長度的上界。設(shè)結(jié)點編號依次為 1, 2, ..., n。從第 2 行到第 n 行，每行給出 3 個用空格隔開的正整數(shù)，依次表示每一條邊的兩個端點編號和長度。例如， “2 4 7”表示連接結(jié)點 2 與 4 的邊的長度為 7。所給的數(shù)據(jù)都是正確的，不必檢驗。【輸出】 輸出文件 只有一個非負(fù)整數(shù)，為指定意義下的最小偏心距?！据斎胼敵鰳永?1】 5 21 2 52 3 22 4 42 5 35【輸入輸出樣例 2】 8 61 3 22 3 23 4 64 5 34 6 44 7 27 8 35【限制】 40%的數(shù)據(jù)滿足：5= n=15 70%的數(shù)據(jù)滿足：5= n=80100%的數(shù)據(jù)滿足：5= n=300, 0=s=1000。邊長度為不超過 10002022 年 45 / 56全國信息學(xué)奧林匹克聯(lián)賽（NOIP2022）復(fù)賽提高組一、題目概覽中文題目名稱 笨小猴 火柴棒等式 傳紙條 雙棧排序英文題目名稱 word matches message twostack可執(zhí)行文件名 word matches message twostack輸入文件名 word,in 輸出文件名 每個測試點時限 1 秒 1 秒 1 秒 1 秒測試點數(shù)目 10 10 10 10每個測試點分值 10 10 10 10比較方式 全文比較 全文比較 全文比較 全文比較題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng)二、提交源程序文件名對于 Pascal 語言 對于 C 語言 對于 C++語言 三、編譯命令（不包含任何優(yōu)化開關(guān)）對于 Pascal 語言 fpc fpc fpc fpc 對于 C 語言 gcc –o word gcc –o matches gcc –o message gcc –o twostack 對于 C++語言 g++ o word g++o matches g++ o message g++ o twostack