【正文】 x1,y1,x2,y2 (分別表示 n,m,起點(diǎn)坐標(biāo)，終點(diǎn)坐標(biāo)) 輸出格式：路徑數(shù)目（若不存在從起點(diǎn)到終點(diǎn)的路徑，輸出 0）第四屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組 競(jìng)賽用時(shí)：3 小時(shí)）1．火車(chē)從始發(fā)站（稱(chēng)為第 1 站）開(kāi)出，在始發(fā)站上車(chē)的人數(shù)為 a，然后到達(dá)第 2 站，在第2 站有人上、下車(chē)，但上、下車(chē)的人數(shù)相同，因此在第 2 站開(kāi)出時(shí)（即在到達(dá)第 3 站之前）車(chē)上的人數(shù)保持為 a 人。 程序要求： 輸入：輸入一個(gè)字符串，以“；”結(jié)束， “；”本身不是代數(shù)表達(dá)式中字符，僅作為結(jié)束） ； 輸出：若表達(dá)式正確，則輸出“OK” ；若表達(dá)式不正確，則輸出 “ERROR”，及錯(cuò)誤類(lèi)型。設(shè)計(jì)一個(gè)挖地雷的方案，使某人能挖到最多的地雷。② 計(jì)算時(shí)可允許出現(xiàn)以下情況： A=B （即可理解為運(yùn)算符的個(gè)數(shù)為零） A=B B+B （即全部由 B 產(chǎn)生）?第二屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組 競(jìng)賽用時(shí)：3 小時(shí)）1．比賽安排（20 分） 設(shè)有有 2 n（n=6）個(gè)球隊(duì)進(jìn)行單循環(huán)比賽，計(jì)劃在 2 n – 1 天內(nèi)完成，每個(gè)隊(duì)每天進(jìn)行一場(chǎng)比賽。2 燈的排列問(wèn)題： 設(shè)在一排上有 N 個(gè)格子（ N≤20） ，若在格子中放置有不同顏色的燈，每種燈的個(gè)數(shù)記為 N1，N 2，……N k（k 表示不同顏色燈的個(gè)數(shù)） 。 放燈時(shí)要遵守下列規(guī)則：①同一種顏色的燈不能分開(kāi)；②不同顏色的燈之間至少要有一個(gè)空位置。設(shè)計(jì)一個(gè)比賽的安排，使在 2 n – 1 天內(nèi)每個(gè)隊(duì)都與不同的對(duì)手比賽。V1 V 2 V3 V4 V5 4 / 56 輸入格式： N： （表示地窖的個(gè)數(shù)） 　　?。?1，W 2，W 3，……W N （表示每個(gè)地窖中埋藏的地雷數(shù)量） A12…………… . A1N A23…………..A2N …….. AN1 N 輸出格式： K1K2……….KV （挖地雷的順序 ） MAX （挖地雷的數(shù)量）例如：　　　 ?、猗? ④ ⑦ ⑥其輸入格式為： 輸出： 5 1 –3 4 510，8，4，7，6 max=27 1 1 1 0 0 0 0 1 1 14．砝碼稱(chēng)重（30 分）設(shè)有 1g、2g、3g、5g、10g、20g 的砝碼各若干枚（其總重=1000） ，要求： 輸入方式：a1 a2 a3 a4 a5 a6 （表示 1g 砝碼有 a1 個(gè)，2g 砝碼有 a2 個(gè)，…，20g 砝碼有 a6 個(gè)） 輸出方式：Total=N （N 表示用這些砝碼能稱(chēng)出的不同重量的個(gè)數(shù)，但不包括一個(gè)砝碼也不用的情況）如輸入：1_1_0_0_0_0 （注：下劃線(xiàn)表示空格） 輸出：TOTAL=3 表示可以稱(chēng)出 1g，2g，3g 三種不同的重量。錯(cuò)誤類(lèi)型約定：1．式了中出現(xiàn)不允許的字符；2．括號(hào)不配對(duì)；acb字母 6 / 563．其它錯(cuò)誤。從第 3 站起（包括第 3 站）上、下車(chē)的人數(shù)有一定規(guī)律：上車(chē)的人數(shù)都是前兩站上車(chē)人數(shù)之和，而下車(chē)人數(shù)等于上一站上車(chē)人數(shù)，一直到終點(diǎn)站的前一站（第 n1 站） ，都滿(mǎn)足此規(guī)律。③ 若不可能組成加法表，則應(yīng)輸出“ERROR！”第五屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （提 高 組 競(jìng)賽用時(shí)：3 小時(shí)）第一題 攔截導(dǎo)彈(28 分) 某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 寫(xiě)一個(gè)程序，給定一個(gè) N（2=N=10 或 N=16）進(jìn)制數(shù) M，求最少經(jīng)過(guò)幾步可以得到回 9 / 56文數(shù)。 樣例： INPUT OUTPUT N=3 K=2 1 3 MAX=7 10 / 562022 年 題一 進(jìn)制轉(zhuǎn)換 （18 分） 問(wèn)題描述 我們可以用這樣的方式來(lái)表示一個(gè)十進(jìn)制數(shù)： 將每個(gè)阿拉伯?dāng)?shù)字乘以一個(gè)以該數(shù)字所處位置的（值減１）為指數(shù)，以１０為底數(shù)的冪之和的形式。在負(fù)進(jìn)制數(shù)中是用－Ｒ 作為基數(shù)，例如－１５（十進(jìn)制）相當(dāng)于１１０００１（－２進(jìn)制），并且它可以被表示為２的冪級(jí)數(shù)的和數(shù)： １１０００１＝１＊（－２） ５ ＋１＊（－２） ４ ＋０＊（－２） ３ ＋０＊（－２） ２ ＋ ０＊（－２） １ ＋１＊（－２） ０ 問(wèn)題求解 設(shè)計(jì)一個(gè)程序，讀入一個(gè)十進(jìn)制數(shù)和一個(gè)負(fù)進(jìn)制數(shù)的基數(shù), 并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下的數(shù)： －Ｒ∈｛－２，－３，－４， ． ． ． ，－２０｝　 輸 入 輸入的每行有兩個(gè)輸入數(shù)據(jù)。 輸 出 結(jié)果顯示在屏幕上，相對(duì)于輸入，應(yīng)輸出所求得的最大乘積（一個(gè)自然數(shù)） 。一行單獨(dú)的 0 表示輸入結(jié)束。1，1，5。2 ，2， 3。輸入格式去部輸入數(shù)據(jù)放在文本文件 中，其格式如下：第一行為一個(gè)正整數(shù)(0n=5)表示有 n 組測(cè)試數(shù)據(jù)每組的第一行有二個(gè)正整數(shù)(p，k)p 表示字串的行數(shù)。圖例 17 / 56機(jī)場(chǎng) 高速鐵路飛機(jī)航線(xiàn)　 注意：圖中并沒(méi)有標(biāo)出所有的鐵路與航線(xiàn)。輸出格式共有 n 行，每行一個(gè)數(shù)據(jù)對(duì)應(yīng)測(cè)試數(shù)據(jù)。文件格式：　　N（N 堆紙牌，1 = N = 100）　　A1 A2 … An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）[輸 出]：　　輸出至屏幕。[輸入]:　　鍵盤(pán)輸人文件名?！　≌?qǐng)你計(jì)算出小車(chē)能接受到多少個(gè)小球。各個(gè)矩形必須完全分開(kāi)（邊線(xiàn)與頂點(diǎn)也都不能重合）。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)分為幾層；稱(chēng)為輸入層、輸出層，和若干個(gè)中間層。【輸入格式】輸入文件第一行是兩個(gè)整數(shù) n（1≤n≤20）和 p。明明所知道的是，他的同學(xué)中有 N 個(gè)人始終說(shuō)假話(huà)，其余的人始終說(shuō)真。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)） ，記第 j 個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為 di，tree 及它的每個(gè)子樹(shù)都有一個(gè)加分，任一棵子樹(shù) subtree（也包含 tree 本身）的加分計(jì)算方法如下： subtree 的左子樹(shù)的加分 subtree 的右子樹(shù)的加分＋subtree 的根的分?jǐn)?shù) 若某個(gè)子樹(shù)為主，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。蓬萊國(guó)也發(fā)現(xiàn)了零星感染者，為防止該病在蓬萊國(guó)大范圍流行，該國(guó)政府決定不惜一切代價(jià)控制傳染病的蔓延。由于蓬萊國(guó)疾控中心人手不夠，同時(shí)也缺乏強(qiáng)大的技術(shù)，以致他們?cè)谝粋€(gè)疾病傳播周期內(nèi)，只能設(shè)法切斷一條傳播途徑，而沒(méi)有被控制的傳播途徑就會(huì)引起更多的易感人群被感染（也就是與當(dāng)前已經(jīng)被感染的人有傳播途徑相連，且連接途徑?jīng)]有被切斷的人群） ?！据斎霕永?7 6 1 2 1 3 2 4 2 5 3 6 3 7【輸出樣例】 32022 年第十屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題 (提高組 3 小時(shí)完成) 27 / 56一、津津的儲(chǔ)蓄計(jì)劃 (／dpr／c／cpp)． 【問(wèn)題描述】 津津的零花錢(qián)一直都是自己管理。有可能在某個(gè)月的月初，津津手中的錢(qián)加上這個(gè)月媽媽給的錢(qián)，不夠這個(gè)月的原定預(yù)算。多多決定把所有的果子合成一堆。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為 12，耗費(fèi)體力為 12。 三、合唱隊(duì)形(／dpr／c／cpp) 30 / 56【問(wèn)題描述】 N 位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(NK)位同學(xué)出列，使得剩下的 K位同學(xué)排成合唱隊(duì)形。來(lái)看一個(gè)簡(jiǎn)單的例子： 439865045 + 84686633 44445506978 其中號(hào)代表被蟲(chóng)子啃掉的數(shù)字。很顯然，我們只要讓 ABCD 分別代表0123，便可以讓這個(gè)式子成立了。 32 / 56【樣例輸入】5ABCEDBDACEEBBAA【樣例輸出】1 0 3 4 2【數(shù)據(jù)規(guī)?！繉?duì)于 30％的數(shù)據(jù)，保證有 N＝10；對(duì)于 50％的數(shù)據(jù)，保證有 N＝15；對(duì)于全部的數(shù)據(jù)，保證有 N＝26?！据斎胛募枯斎胛募? 有 2 行，第 1 行為 1 個(gè)正整數(shù)，表示所生成的隨機(jī)數(shù)的個(gè)數(shù)：N第 2 行有 N 個(gè)用空格隔開(kāi)的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)。他希望在不超過(guò) N元（可以等于 N 元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。我們把這樣的“數(shù)字”稱(chēng)為 Jam數(shù)字。所給的數(shù)據(jù)都是正確的，不必驗(yàn)證?！据斎霕永? 3 100【輸出樣例】9812022 年 全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2022）復(fù)賽 39 / 56提高組題目一覽題目名稱(chēng) 統(tǒng)計(jì)數(shù)字 字符串的展開(kāi) 矩陣取數(shù)游戲 樹(shù)網(wǎng)的核代號(hào) count expand game core輸入文件 輸出文件 時(shí)限 1 秒 1 秒 1 秒 1 秒(2022 年 11 月 17 日 3 小時(shí)完成)說(shuō)明：1. 文件名（程序名和輸入輸出文件名）必須使用小寫(xiě)2. C/C++中函數(shù) main()的返回值類(lèi)型必須是 int，程序正常結(jié)束時(shí)的返回值必須是 0?！据斎胼敵鰳永?82424510021002 34 25 1100 2【限制】 40%的數(shù)據(jù)滿(mǎn)足：1= n=1000 80%的數(shù)據(jù)滿(mǎn)足：1= n=50000 100%的數(shù)據(jù)滿(mǎn)足：1= n=202200，每個(gè)數(shù)均不超過(guò) 1 500 000 000（*10 9）2．字符串的展開(kāi)()【問(wèn)題描述】在初賽普及組的“閱讀程序?qū)懡Y(jié)果”的問(wèn)題中，我們?cè)o出一個(gè)字符串展開(kāi)的例子：如果在輸入的字符串中，含有類(lèi)似于“dh”或“48 ”的子串，我們就把它當(dāng)作一種簡(jiǎn)寫(xiě)，輸出時(shí)，用連續(xù)遞增的字母或數(shù)字串替代其中的減號(hào)，即，將上面兩個(gè)子串分別輸出為“defgh”和“ 45678”。p2=k 表示同一個(gè)字符要連續(xù)填充 k 個(gè)。第 2 行為一行字符串，僅由數(shù)字、小寫(xiě)字母和減號(hào)“”組成?！据斎搿? 輸入文件 包括 n+1 行： 第 1 行為兩個(gè)用空格隔開(kāi)的整數(shù) n 和 m。樹(shù)網(wǎng)的直徑：樹(shù)網(wǎng)中最長(zhǎng)的路徑稱(chēng)為樹(shù)網(wǎng)的直徑。圖中，AB 與 AC 是兩條直徑，長(zhǎng)度均為 20。例如， “2 4 7”表示連接結(jié)點(diǎn) 2 與 4 的邊的長(zhǎng)度為 7?！据敵觥? 輸出文件 只有一個(gè)非負(fù)整數(shù)，為指定意義下的最小偏心距。如果指定 s=11，則樹(shù)網(wǎng)的核為路徑 DEFG（也可以取為路徑 DEF） ，偏心距為 8。偏心距 ECC(F)：樹(shù)網(wǎng) T 中距路徑 F 最遠(yuǎn)的結(jié)點(diǎn)到路徑 F 的距離，即。【輸出】 輸出文件 僅包含 1 行，為一個(gè)整數(shù)，即輸入矩陣取數(shù)后的最大得分。【輸出】輸出文件 只有一行，為展開(kāi)后的字符串。減號(hào)兩側(cè)的字符不變。具體約定如下：（1）遇到下面的情況需要做字符串的展開(kāi)：在輸入的字符串中，出現(xiàn)了減號(hào)“” ，減 41 / 56號(hào)兩側(cè)同為小寫(xiě)字母或同為數(shù)字，且按照 ASCII 碼的順序，減號(hào)右邊的字符嚴(yán)格大于左邊的字符。 40 / 561．統(tǒng)計(jì)數(shù)字()【問(wèn)題描述】某次科研調(diào)查時(shí)得到了 n 個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò) 1500000000（*10 9） 。每行只輸出一個(gè) Jam 數(shù)字，是由 w 個(gè)小寫(xiě)字母組成的字符串，不要有多余的空格。每次，Jam 還指定使用字母的范圍，例如，從 2 到 10，表示只能使用{b,c,d,e,f,g,h,i,j}這些字母。（其中*為乘號(hào)）請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿(mǎn)足要求的購(gòu)物單。第 2 行為 M 個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大排好序的不相同的隨機(jī)數(shù)。2．允許使用數(shù)學(xué)庫(kù)(uses math 子句)，以及 ansistring。輸入數(shù)據(jù)保證有且僅有一組解，【輸入文件】 輸入文件 包含 4 行。 現(xiàn)在，我們對(duì)問(wèn)題做兩個(gè)限制： 首先，我們只考慮加法的蟲(chóng)食算。 你的任務(wù)是，已知所有 N 位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。可以證明 15 為最小的體力耗費(fèi)值。可以看出，所有的果子經(jīng)過(guò) n1 次合并之后，就只剩下一堆了。 現(xiàn)在請(qǐng)你根據(jù) 2022 年 1 月到 12 月每個(gè)月津津的預(yù)算，判斷會(huì)不會(huì)出現(xiàn)