1 56 NOI 95 同創(chuàng)杯同創(chuàng)杯 全國青少年信息學(xué) 計算機(jī) 奧林匹克競賽全國青少年信息學(xué) 計算機(jī) 奧林匹克競賽 分區(qū)聯(lián)賽復(fù)賽試題 高中組 分區(qū)聯(lián)賽復(fù)賽試題 高中組 上機(jī)編程 完成時間 上機(jī)編程 完成時間 210 分鐘 分鐘 編碼問題 編碼問題 設(shè)有一個數(shù)組 A ARRAY 0 N 1 OF INTEGER 數(shù)組中存放的元素為 0 N 1 之間的整數(shù) 且 A i A j 當(dāng) i j 時 例如 N 6 時 有 A 4 3 0 5 1 2 此時 數(shù)組 A 的編碼定義如下 A 0 的編碼為 0 A i 的編碼為 在 A 0 A 1 A i 1 中比 A i 的值小的個數(shù) i 1 2 N 1 上面數(shù)組 A 的編碼為 B 0 0 0 3 1 2 程序要求解決以下問題 程序要求解決以下問題 給出數(shù)組 A 后 求出其編碼 給出數(shù)組 A 的編碼后 求出 A 中的原數(shù)據(jù) 燈的排列問題 燈的排列問題 設(shè)在一排上有 N 個格子 N 20 若在格子中放置有不同顏色的燈 每種燈的個數(shù)記 為 N1 N2 Nk k 表示不同顏色燈的個數(shù) 放燈時要遵守下列規(guī)則 放燈時要遵守下列規(guī)則 同一種顏色的燈不能分開 不同顏色的燈之間至少要有一個空位置 例如 N 8 格子數(shù) R 2 紅燈數(shù) B 3 藍(lán)燈數(shù) 放置的方法有 R B 順序 RRBBB RRBBB RRBBB RRBBB RRBBB RRBBB 2 56 B R 順序 BBBRR BBBRR BBBRR BBBRR BBBRR BBBRR 放置的總數(shù)為 12 種 數(shù)據(jù)輸入的方式為 N P1 顏色 為一個字母 N1 燈的數(shù)量 P2 N2 Q 結(jié)束標(biāo)記 Q 本身不是燈的顏色 程序要求 求出一種順序的排列方案及排列總數(shù) 程序要求 求出一種順序的排列方案及排列總數(shù) 設(shè)有一個四層的積木塊 1 4 層積木塊的數(shù)量依次為 5 6 7 8 如下圖所示放置 8158516914 23414326 其中 給出第三層與第四層所標(biāo)示的數(shù)字 并已知第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)計 算出來的 計算的方法是 第三層的某個數(shù)據(jù) A 是由第四層相鄰的兩個數(shù)據(jù) B C 經(jīng)過某種計算 后產(chǎn)生的 A BC 計算所用到的計算符為 且無優(yōu)先級之分 自左向右計算 運算符最多為 2 個 如 3 45 35 54 3 23 可以看出 上圖中的第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)用以下計算公式計算出來的 A BC B 也就是 8 23 2 15 34 3 14 26 2 程序要求 程序要求 給出第四層與第三層的數(shù)據(jù)后 將第一 二層的每塊積木標(biāo)上相應(yīng)的數(shù)據(jù) 并輸出整 3 56 個完整的積木圖及計算公式 輸入數(shù)據(jù)不存在出錯的情況 同時也不會超過整數(shù)的范圍 計算時可允許出現(xiàn)以下情況 A B 即可理解為運算符的個數(shù)為零 A BB B 即全部由 B 產(chǎn)生 第二屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第二屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 高中組 高中組 競賽用時 競賽用時 3 小時 小時 1 比賽安排 20 分 設(shè)有有 2 n n 6 個球隊進(jìn)行單循環(huán)比賽 計劃在 2 n 1 天內(nèi)完成 每個隊每天進(jìn)行 一場比賽 設(shè)計一個比賽的安排 使在 2 n 1 天內(nèi)每個隊都與不同的對手比賽 例如 n 2 時的比賽安排 隊 1 23 4 比賽 1 23 4 一天 1 32 4 二天 1 4 2 3 三天 2 數(shù)制轉(zhuǎn)換 20 分 設(shè)有一個字符串 A 的結(jié)構(gòu)為 A mp 其中 m 為數(shù)字串 長度 20 而 n p 均為 1 或 2 位的數(shù)字串 其中所表達(dá)的內(nèi)容在 2 10 之間 程序要求 從鍵盤上讀入 A 后 不用正確性檢查 將 A 中的數(shù)字串 m n 進(jìn)制 以 p 進(jìn)制的形式輸出 例如 A 488 其意義為 將 10 進(jìn)制數(shù) 48 轉(zhuǎn)換成 8 進(jìn)制數(shù)輸出 輸出結(jié)果為 48 60 4 挖地雷 30 分 在一個地圖上有 N 個地窖 N 20 每個地窖中埋有一定數(shù)量的地雷 同時 給出 地窖之間的連接路徑 例如 題目要求 當(dāng)?shù)亟鸭捌溥B接的數(shù)據(jù)給出之后 某人可以從任一處開始挖地雷 然后可以沿著指出 的連接往下挖 僅能選擇一條路徑 當(dāng)無連接時挖地雷工作結(jié)束 設(shè)計一個挖地雷的方案 使某人能挖到最多的地雷 V1 V 2 V3 V4 V5 4 56 輸入格式 N 表示地窖的個數(shù) 1 W2 W3 WN 表示每個地窖中埋藏的地雷數(shù)量 A12 A1N A23 A2N AN 1 N 輸出格式 K1 K2 KV 挖地雷的順序 MAX 挖地雷的數(shù)量 例如 其輸入格式為 輸出 51 3 4 5 10 8 4 7 6max 27 1 1 1 0 0 0 0 1 1 1 4 砝碼稱重 30 分 設(shè)有 1g 2g 3g 5g 10g 20g 的砝碼各若干枚 其總重 1000 要求 輸入方式 a1 a2 a3 a4 a5 a6 表示 1g 砝碼有 a1 個 2g 砝碼有 a2 個 20g 砝碼有 a6 個 輸出方式 Total N N 表示用這些砝碼能稱出的不同重量的個數(shù) 但不包括一個砝碼也不 用的情況 如輸入 1 1 0 0 0 0 注 下劃線表示空格 輸出 TOTAL 3 表示可以稱出 1g 2g 3g 三種不同的重量 第三屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第三屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 高中組 高中組 競賽用時 競賽用時 3 小時 小時 1 在 N N 的棋盤上 1 N 10 填入 1 2 N N 共 N N 個數(shù) 使得任意兩個相 鄰的數(shù)之和為素數(shù) 30 例如 當(dāng) N 2 時 有 12 地窖之間連接路徑 其中 ij 1 表示地窖 i j 之間是否有通路 通 Aij 1 不通 Aij 0 其相鄰數(shù)的和為素數(shù)的有 1 2 1 4 4 3 2 3 5 56 43 當(dāng) N 4 時 一種可以填寫的方案如下 121112 161585 134914 67103 在這里我們約定 左上角的格子里必須填數(shù)字 1 程序要求 輸入 N 輸出 如有多種解 則輸出第一行 第一列之和為最小的排列方案 若無解 則 輸出 NO 2 代數(shù)表達(dá)式的定義如下 例如 下面的式子是合法的代數(shù)表達(dá)式 a a b a c a a b c 下面的式子是不合法的代數(shù)表達(dá)式 ab a a b c 程序要求 輸入 輸入一個字符串 以 結(jié)束 本身不是代數(shù)表達(dá)式中字符 僅作 為結(jié)束 輸出 若表達(dá)式正確 則輸出 OK 若表達(dá)式不正確 則輸出 ERROR 及 錯誤類型 錯誤類型約定 1 式了中出現(xiàn)不允許的字符 2 括號不配對 a c b 字母 6 56 3 其它錯誤 例如 輸入 a b 輸出 OK 例如 輸入 a b c a 輸出 ERROR 2 3 騎士游歷 設(shè)有一個 n m 的棋盤 2 n 50 2 m 50 如下圖 在棋盤上左下角有一個中國 象棋馬 n m 1 1 馬走的規(guī)則為 1 馬走日字 2 馬只能向右走 即如下圖如示 任務(wù) 1 當(dāng) n m 輸入之后 找出一條從左下角到右上角的路徑 例如 輸入 n 4 m 4 輸出 路徑的格式 1 1 2 3 4 4 若不存在路徑 則輸出 NO 任務(wù) 2 當(dāng) n m 給出之后 同時給出馬起點的位置和終點的位置 試找出從起點到終 點的所有路徑的數(shù)目 例如 n 10 m 10 1 5 起點 3 5 終點 輸 出 2 即由 1 5 到 3 5 共有 2 條路徑 馬 4 4 1 1 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 7 56 輸入格式 n m x1 y1 x2 y2 分別表示 n m 起點坐標(biāo) 終點坐標(biāo) 輸出格式 路徑數(shù)目 若不存在從起點到終點的路徑 輸出 0 第四屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第四屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 高中組 高中組 競賽用時 競賽用時 3 小時 小時 1 火車從始發(fā)站 稱為第 1 站 開出 在始發(fā)站上車的人數(shù)為 a 然后到達(dá)第 2 站 在第 2 站有人上 下車 但上 下車的人數(shù)相同 因此在第 2 站開出時 即在到達(dá)第 3 站之 前 車上的人數(shù)保持為 a 人 從第 3 站起 包括第 3 站 上 下車的人數(shù)有一定規(guī)律 上車的人數(shù)都是前兩站上車人數(shù)之和 而下車人數(shù)等于上一站上車人數(shù) 一直到終點站 的前一站 第 n 1 站 都滿足此規(guī)律 現(xiàn)給出的條件是 共有 N 個車站 始發(fā)站上車 的人數(shù)為 a 最后一站下車的人數(shù)是 m 全部下車 試問 x 站開出時車上的人數(shù)是多 少 輸入 a n m 和 x 輸出 從 x 站開出時車上的人數(shù) 20 2 設(shè)有 n 個正整數(shù) n 20 將它們聯(lián)接成一排 組成一個最大的多位整數(shù) 例如 n 3 時 3 個整數(shù) 13 312 343 聯(lián)接成的最大整數(shù)為 34331213 又如 n 4 時 4 個整數(shù) 7 13 4 246 聯(lián)接成的最大整數(shù)為 7424613 程序輸入 n n 個數(shù) 程序輸出 聯(lián)接成的多位數(shù) 40 3 著名科學(xué)家盧斯為了檢查學(xué)生對進(jìn)位制的理解 他給出了如下的一張加法表 表中的字 母代表數(shù)字 例如 40 其含義為 L L L L K K L V V L E E K L K K K V K V E K E KL E E KV 根據(jù)這些規(guī)則可推導(dǎo)出 L 0 K 1 V 2 E 3 同時可以確定該表表示的是 4 進(jìn)制加法 程序輸入 n n 9 表示行數(shù) LKVE LLKVE KKVEKL VVEKLKK EEKLKK KV 8 56 以下 n 行 每行包括 n 個字符串 每個字串間用空格隔開 字串僅有一個為 號 其它都由大寫字母組成 程序輸出 各個字母表示什么數(shù) 格式如 L 0 K 1 加法運算是幾進(jìn)制的 若不可能組成加法表 則應(yīng)輸出 ERROR 第五屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第五屆全國青少年信息學(xué) 計算機(jī) 奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 提 提 高高 組組 競賽用時 競賽用時 3 小時 小時 第一題第一題 攔截導(dǎo)彈攔截導(dǎo)彈 28 28 分分 某國為了防御敵國的導(dǎo)彈襲擊 發(fā)展出一種導(dǎo)彈攔截系統(tǒng) 但是這種導(dǎo)彈攔截系統(tǒng)有 一個缺陷 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度 但是以后每一發(fā)炮彈都不能高于前 一發(fā)的高度 某天 雷達(dá)捕捉到敵國的導(dǎo)彈來襲 由于該系統(tǒng)還在試用階段 所以只有一 套系統(tǒng) 因此有可能不能攔截所有的導(dǎo)彈 輸入導(dǎo)彈依次飛來的高度 雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù) 計算這套 系統(tǒng)最多能攔截多少導(dǎo)彈 如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng) 樣例 INPUT OUTPUT 389 207 155 300 299 170 158 65 6 最多能攔截的導(dǎo)彈數(shù) 2 要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù) 第二題第二題 回文數(shù)回文數(shù) 25 25 分分 若一個數(shù) 首位不為零 從左向右讀與從右向左讀都一樣 我們就將其稱之為回文數(shù) 例如 給定一個 10 進(jìn)制數(shù) 56 將 56 加 65 即把 56 從右向左讀 得到 121 是一個回 文數(shù) 又如 對于 10 進(jìn)制數(shù) 87 STEP1 87 78 165 STEP2 165 561 726 STEP3 726 627 1353 STEP4 1353 3531 4884 在這里的一步是指進(jìn)行了一次 N 進(jìn)制的加法 上例最少用了 4 步得到回文數(shù) 4884 寫一個程序 給定一個 N 2 N 10 或 N 16 進(jìn)制數(shù) M 求最少經(jīng)過幾步可以得到回 9 56 文數(shù) 如果在 30 步以內(nèi) 包含 30 步 不可能得到回文數(shù) 則輸出 Impossible 樣例 INPUT OUTPUT N 9 M 87 STEP 6 第三題第三題 旅行家的預(yù)算旅行家的預(yù)算 27 27 分分 一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市 假設(shè)出發(fā)時油箱是空 的 給定兩個城市之間的距離 D1 汽車油箱的容量 C 以升為單位 每升汽油能行駛的 距離 D2 出發(fā)點每升汽油價格 P 和沿途油站數(shù) N N 可以為零 油站 i 離出發(fā)點的距離 Di 每升汽油價格 Pi i 1 2 N 計算結(jié)果四舍五入至小數(shù)點后兩位 如果無法到 達(dá)目的地 則輸出 No Solution 樣例 INPUT D1 275 6 C 11 9 D2 27 4 P 2 8 N 2 油站號 I離出發(fā)點的距離 Di每升汽油價格 Pi 1102 02 9 2220 02 2 OUTPUT 26 95 該數(shù)據(jù)表示最小費用 第四題第四題 郵票面值設(shè)計郵票面值設(shè)計 40 40 分分 給定一個信封 最多只允許粘貼 N 張郵票 計算在給定 K N K 40 種郵票的情況下 假定所有的郵票數(shù)量都足夠 如何設(shè)計郵票的面值 能得到最大值 MAX 使在 1 MAX 之間的每一個郵資值都能得到 例如 N 3 K 2 如果面值分別為 1 分 4 分 則在 1 分 6 分之間的每一個郵資值都 能得到 當(dāng)然還有 8 分 9 分和 12 分 如果面值分別為 1 分 3 分 則在 1 分 7 分之間 的每一個郵資值都能得到 可以驗證當(dāng) N 3 K 2 時 7 分就是可以得到的連續(xù)的郵資最大 值 所以 MAX 7 面值分別為 1 分 3 分 樣例 INPUT OUTPUT N 3 K 2 1 3 MAX 7 10 56 2000 年 題一題一 進(jìn)制轉(zhuǎn)換進(jìn)制轉(zhuǎn)換 18 分 分 問題描述問題描述 我們可以用這樣的方式來表示一個十進(jìn)制數(shù) 將每個阿拉伯?dāng)?shù)字乘以一個以該數(shù)字所 處位置的 值減 為指數(shù) 以 為底數(shù)的冪之和的形式 例如 可表示為 這樣的形式 與之相似的 對二進(jìn)制數(shù)來說 也可表示成每個二進(jìn)制數(shù)碼乘以一個以該數(shù)字所處位 置的 值 為指數(shù) 以 為底數(shù)的冪之和的形式 一般說來 任何一個正整數(shù) 或一 個負(fù)整數(shù) 都可以被選來作為一個數(shù)制系統(tǒng)的基數(shù) 如果是以 或 為基數(shù) 則需要 用到的數(shù)碼為 例如 當(dāng) 時 所需用到的數(shù)碼是 和 這與其是 或 無關(guān) 如果作為基數(shù)的數(shù)絕對值超過 則為了表示這些數(shù)碼 通常使用英文字母來表示那些大于 的數(shù)碼 例如對 進(jìn) 制數(shù)來說 用 表示 用 表示 用 表示 用 表示 用 表示 用 表示 在負(fù)進(jìn)制數(shù)中是用 作為基數(shù) 例如 十進(jìn)制 相當(dāng)于 進(jìn)制 并且它可以被表示為 的冪級數(shù)的和數(shù) 問題求解問題求解 設(shè)計一個程序 讀入一個十進(jìn)制數(shù)和一個負(fù)進(jìn)制數(shù)的基數(shù) 并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù) 進(jìn)制下的數(shù) 輸輸 入入 輸入的每行有兩個輸入數(shù)據(jù) 第一個是十進(jìn)制數(shù) 32768 32767 第二個是負(fù)進(jìn)制數(shù)的基數(shù) 輸輸 出出 結(jié)果顯示在屏幕上 相對于輸入 應(yīng)輸出此負(fù)進(jìn)制數(shù)及其基數(shù) 若此基數(shù)超過 則參照 進(jìn)制的方式處理 樣樣 例例 輸入 11 56 輸出 提高組 題二題二 乘積最大乘積最大 22 分 分 問題描述問題描述 今年是國際數(shù)學(xué)聯(lián)盟確定的 2000 世界數(shù)學(xué)年 又恰逢我國著名數(shù)學(xué)家華羅庚 先生誕辰 90 周年 在華羅庚先生的家鄉(xiāng)江蘇金壇 組織了一場別開生面的數(shù)學(xué)智力競賽的 活動 你的一個好朋友 XZ 也有幸得以參加 活動中 主持人給所有參加活動的選手出了 這樣一道題目 設(shè)有一個長度為 N 的數(shù)字串 要求選手使用 K 個乘號將它分成 K 1 個部分 找出一 種分法 使得這 K 1 個部分的乘積能夠為最大 同時 為了幫助選手能夠正確理解題意 主持人還舉了如下的一個例子 有一個數(shù)字串 312 當(dāng) N 3 K 1 時會有以下兩種分法 1 3 12 36 2 31 2 62 這時 符合題目要求的結(jié)果是 31 2 62 現(xiàn)在 請你幫助你的好朋友 XZ 設(shè)計一個程序 求得正確的答案 輸輸 入入 程序的輸入共有兩行 第一行共有 2 個自然數(shù) N K 6 N 40 1 K 6 第二行是一個長度為 N 的數(shù)字串 輸輸 出出 結(jié)果顯示在屏幕上 相對于輸入 應(yīng)輸出所求得的最大乘積 一個自然數(shù) 樣樣 例例 12 56 輸入 4 2 1231 輸出 62 提高組 題三 題三 單詞接龍單詞接龍 27 分 分 問題描述問題描述 單詞接龍是一個與我們經(jīng)常玩的成語接龍相類似的游戲 現(xiàn)在我們已知一組單詞 且 給定一個開頭的字母 要求出以這個字母開頭的最長的 龍 每個單詞都最多在 龍 中 出現(xiàn)兩次 在兩個單詞相連時 其重合部分合為一部分 例如 beast 和 astonish 如果接 成一條龍則變?yōu)?beastonish 另外相鄰的兩部分不能存在包含關(guān)系 例如 at 和 atide 間不 能相連 輸輸 入入 輸入的第一行為一個單獨的整數(shù) n n 20 表示單詞數(shù) 以下 n 行每行有一個單詞 輸 入的最后一行為一個單個字符 表示 龍 開頭的字母 你可以假定以此字母開頭的 龍 一定存在 輸輸 出出 只需輸出以此字母開頭的最長的 龍 的長度 樣樣 例例 輸入 5 at touch cheat choose tact a 輸出 13 56 23 連成的 龍 為 atoucheatactactouchoose 14 56 提高組 題四 題四 方格取數(shù)方格取數(shù) 33 分 分 問題描述問題描述 設(shè)有 N N 的方格圖 N 1 要求由小到大依次在同一行輸出這三個實根 根與根之間留有 空格 并精確到小數(shù)點后 2 位 提示 記方程 f x 0 若存在 2 個數(shù) x1 和 x2 且 x1 x2 f x1 f x2 0 則在 x1 x2 之 間一定有一個 根 樣例樣例 輸入 1 5 4 20 輸出 2 00 2 00 5 00 題二 數(shù)的劃分 20 分 問題描述問題描述 將整數(shù) n 分成 k 份 且每份不能為空 任意兩份不能相同 不考慮順序 例如 n 7 k 3 下面三種分法被認(rèn)為是相同的 1 1 5 1 5 1 5 1 1 問有多少種不同的分法 輸入 n k 6 n 200 2 k 6 輸出 一個整數(shù) 即不同的分法 樣例樣例 輸入 7 3 輸出 4 四種分法為 1 1 5 1 2 4 1 3 3 2 2 3 題三 統(tǒng)計單詞個數(shù) 30 分 問題描述問題描述 給出一個長度不超過 200 的由小寫英文字母組成的字母串 約定 該字串以每行 20 個字母的方式 輸入 且保證每行一定為 20 個 要求將此字母串分成 k 份 1 k 40 且每份中包含的單詞個 數(shù)加起來總數(shù)最大 每份中包含的單詞可以部分重疊 當(dāng)選用一個單詞之后 其第一個字母不能 16 56 再用 例如字符串 this 中可包含 this 和 is 選用 this 之后就不能包含 th 單詞在給出的一個不超過 6 個單詞的字典中 要求輸出最大的個數(shù) 輸入格式輸入格式 去部輸入數(shù)據(jù)放在文本文件 input3 dat 中 其格式如下 第一行為一個正整數(shù) 0 n 5 表示有 n 組測試數(shù)據(jù) 每組的第一行有二個正整數(shù) p k p 表示字串的行數(shù) k 表示分為 k 個部分 接下來的 p 行 每行均有 20 個字符 再接下來有一個正整數(shù) s 表示字典中單詞個數(shù) 1 s 6 接下來的 s 行 每行均有一個單詞 輸出格式輸出格式 結(jié)果輸出至屏幕 每行一個整數(shù) 分別對應(yīng)每組測試數(shù)據(jù)的相應(yīng)結(jié)果 樣例樣例 輸入 1 1 3 thisisabookyouareaoh 4 is a ok sab 輸出 說明 不必輸出 7 this isabookyoua reaoh 題四 Car 的旅行路線 30 分 問題描述問題描述 又到暑假了 住在城市 A 的 Car 想和朋友一起去城市 B 旅游 她知道每個城市都有四個飛機(jī)場 分別位于一個矩形的四個頂點上 同一個城市中兩個機(jī)場之間有一條筆直的高速鐵路 第 I 個 城市中高速鐵路了的單位里程價格為 Ti 任意兩個不同城市的機(jī)場之間均有航線 所有航線單 位里程的價格均為 t 圖例 17 56 機(jī)場 高速鐵路 飛機(jī)航線 注意 圖中并沒有 標(biāo)出所有的鐵路與航線 那么 Car 應(yīng)如何安排到城市 B 的路線才能盡可能的節(jié)省花費呢 她發(fā)現(xiàn)這并不是一個簡單的問題 于是她來向你請教 任務(wù)任務(wù) 找出一條從城市 A 到 B 的旅游路線 出發(fā)和到達(dá)城市中的機(jī)場可以任意選取 要求總的花費最 少 輸入文件 鍵盤輸入文件名 輸 出 到屏幕 輸出最小費用 小數(shù)點后保留 1 位 輸入格式輸入格式 第一行為一個正整數(shù) n 0 n 10 表示有 n 組測試數(shù)據(jù) 每組的第一行有四個正整數(shù) s t A B S 0 S 100 表示城市的個數(shù) t 表示飛機(jī)單位里程的價格 A B 分別為城市 A B 的序號 1 A B 從 取 3 張牌放到 9 11 10 10 從 取 1 張牌放到 10 10 10 10 輸輸 入入 鍵盤輸入文件名 文件格式 N N 堆紙牌 1 N 100 A1 A2 An N 堆紙牌 每堆紙牌初始數(shù) l Ai B1 A2 B2 規(guī)則的含義為 在 A 中的子串 A1 可以變換為 B1 A2 可以變換為 B2 例如 A abcd B xyz 變換規(guī)則為 abc xu ud y y yz 則此時 A 可以經(jīng)過一系列的變換變?yōu)?B 其變換的過程為 abcd xud xy xyz 共進(jìn)行了三次變換 使得 A 變換為 B 輸入輸入 鍵盤輸人文件名 文件格式如下 A B A1 B1 A2 B2 變換規(guī)則 所有字符串長度的上限為 20 輸出輸出 輸出至屏幕 格式如下 若在 10 步 包含 10 步 以內(nèi)能將 A 變換為 B 則輸出最少的變換步數(shù) 否則輸出 NO ANSWER 輸入輸出樣例輸入輸出樣例 b in abcd wyz abc xu ud y y yz 屏幕顯示 3 題三 自由落體 存盤名 NOIPG3 問題描述問題描述 在高為 H 的天花板上有 n 個小球 體積不計 位置分別為 0 1 2 n 1 在地面上 20 56 有一個小車 長為 L 高為 K 距原點距離為 S1 已知小球下落距離計算公式為 d 1 2 g t 2 其中 g 10 t 為下落時間 地面上的小車以速度 V 前進(jìn) 如下圖 小車與所有小球同時開始運動 當(dāng)小球距小車的距離 0 00001 時 即認(rèn)為小球被小車 接受 小球落到地面后不能被接受 請你計算出小車能接受到多少個小球 輸入輸入 鍵盤輸人 H S1 V L K n l H S1 V L K n 100000 輸出輸出 屏幕輸出 小車能接受到的小球個數(shù) 輸入輸出樣例輸入輸出樣例 輸入 5 0 9 0 5 0 2 5 1 8 5 輸出 1 題四 矩形覆蓋 存盤名 NOIPG4 問題描述問題描述 在平面上有 n 個點 n 50 每個點用一對整數(shù)坐標(biāo)表示 例如 當(dāng) n 4 時 4 個 點的坐標(biāo)分另為 p1 1 1 p2 2 2 p3 3 6 P4 0 7 見圖一 21 56 這些點可以用 k 個矩形 1 k 4 全部覆蓋 矩形的邊平行于坐標(biāo)軸 當(dāng) k 2 時 可用 如圖二的兩個矩形 sl s2 覆蓋 s1 s2 面積和為 4 問題是當(dāng) n 個點坐標(biāo)和 k 給出后 怎 樣才能使得覆蓋所有點的 k 個矩形的面積之和為最小呢 約定 覆蓋一個點的矩形面積為 0 覆蓋平行于坐標(biāo)軸直線上點的矩形面積也為 0 各個矩形必須完全分開 邊線與頂點也都不能 重合 輸入輸入 鍵盤輸人文件名 文件格式為 n k xl y1 x2 y2 xn yn 0 xi yi 500 輸出輸出 輸出至屏幕 格式為 一個整數(shù) 即滿足條件的最小的矩形面積之和 輸入輸出樣例輸入輸出樣例 d in 4 2 1 1 2 2 3 6 0 7 屏幕顯示 4 2003 年 22 56 第九第九屆屆全全國青國青少年信息少年信息學(xué)奧學(xué)奧林匹克林匹克聯(lián)賽聯(lián)賽 N0IP2003N0IP2003 2003 年 11 月 29 日 提高組試題 三小時完成 試題輸入 蘇州高斌 大榕樹 題一題一 神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò) 問題背景 人工神經(jīng)網(wǎng)絡(luò) Artificial Neural Network 是一種新興的具有自我學(xué)習(xí)能力的計算系統(tǒng) 在模式識別 函數(shù)逼近及貸款風(fēng)險評估等諸多領(lǐng)域有廣泛的應(yīng)用 對神經(jīng)網(wǎng)絡(luò)的研究一直 是當(dāng)今的熱門方向 蘭蘭同學(xué)在自學(xué)了一本神經(jīng)網(wǎng)絡(luò)的入門書籍后 提出了一個簡化模型 他希望你能幫助他用程序檢驗這個神經(jīng)網(wǎng)絡(luò)模型的實用性 問題描述 在蘭蘭的模型中 神經(jīng)網(wǎng)絡(luò)就是一張有向圖 圖中的節(jié)點稱為神經(jīng)元 而且兩個神經(jīng) 元之間至多有一條邊相連 下圖是一個神經(jīng)元的例子 神經(jīng)元 編號為 1 圖中 X1 X3 是信息輸入渠道 Y1 Y2 是信息輸出渠道 C1 表示神經(jīng)元目前的狀 態(tài) Ui 是閾值 可視為神經(jīng)元的一個內(nèi)在參數(shù) 神經(jīng)元按一定的順序排列 構(gòu)成整個神經(jīng)網(wǎng)絡(luò) 在蘭蘭的模型之中 神經(jīng)網(wǎng)絡(luò)中的神 經(jīng)無分為幾層 稱為輸入層 輸出層 和若干個中間層 每層神經(jīng)元只向下一層的神經(jīng)元 輸出信息 只從上一層神經(jīng)元接受信息 下圖是一個簡單的三層神經(jīng)網(wǎng)絡(luò)的例子 蘭蘭規(guī)定 Ci服從公式 其中 n 是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目 23 56 公式中的 Wji 可能為負(fù)值 表示連接 j 號神經(jīng)元和 i 號神經(jīng)元的邊的權(quán)值 當(dāng) Ci 大 于 0 時 該神經(jīng)元處于興奮狀態(tài) 否則就處于平靜狀態(tài) 當(dāng)神經(jīng)元處于興奮狀態(tài)時 下一 秒 它會向其他神經(jīng)元傳送信號 信號的強(qiáng)度為 Ci 如此 在輸入層神經(jīng)元被激發(fā)之后 整個網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿酉逻M(jìn)行運作 現(xiàn)在 給定一個神經(jīng)網(wǎng)絡(luò) 及當(dāng)前輸入層神經(jīng)元的狀態(tài) Ci 要求你的程序運算出最后網(wǎng) 絡(luò)輸出層的狀態(tài) 輸入格式 輸入文件第一行是兩個整數(shù) n 1 n 20 和 p 接下來 n 行 每行兩個整數(shù) 第 i 1 行是神經(jīng)元 i 最初狀態(tài)和其閾值 Ui 非輸入層的神經(jīng)元開始時狀態(tài)必然為 0 再下面 P 行 每行由兩個整數(shù) i j 及一個整數(shù) Wij 表示連接神經(jīng)元 i j 的邊權(quán)值為 Wij 輸出格式 輸出文件包含若干行 每行有兩個整數(shù) 分別對應(yīng)一個神經(jīng)元的編號 及其最后的狀 態(tài) 兩個整數(shù)間以空格分隔 僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài) 并且按照編號由 小到大順序輸出 若輸出層的神經(jīng)元最后狀態(tài)均為 0 則輸出 NULL 輸入樣例 5 6 1 0 1 0 0 1 0 1 0 1 1 3 1 1 4 1 1 5 1 2 3 1 2 4 1 2 5 1 輸出樣例 3 1 4 1 5 1 題二題二 偵探推理偵探推理 問題描述 E i j ijjii UCWC 24 56 明明同學(xué)最近迷上了偵探漫畫 柯南 并沉醉于推理游戲之中 于是他召集了一群同 學(xué)玩推理游戲 游戲的內(nèi)容是這樣的 明明的同學(xué)們先商量好由其中的一個人充當(dāng)罪犯 在明明不知情的情況下 明明的任務(wù)就是找出這個罪犯 接著 明明逐個詢問每一個同 學(xué) 被詢問者可能會說 證詞中出現(xiàn)的其他話 都不列入邏輯推理的內(nèi)容 明明所知道的是 他的同學(xué)中有 N 個人始終說假話 其余的人始終說真 現(xiàn)在 明明需要你幫助他從他同學(xué)的話中推斷出誰是真正的兇手 請記住 兇手只有 一個 輸入格式 輸入由若干行組成 第一行有二個整數(shù) M 1 M 20 N 1 N M 和 P 1 P 100 M 是參加游戲的明明的同學(xué)數(shù) N 是其中始終說謊的人數(shù) P 是證言的總數(shù) 接下來 M 行 每行是明明的一個同學(xué)的名字 英文字母組成 沒有主格 全部大寫 往后有 P 行 每行開始是某個同學(xué)的名宇 緊跟著一個冒號和一個空格 后面是一句 證詞 符合前表中所列格式 證詞每行不會超過 250 個字符 輸入中不會出現(xiàn)連續(xù)的兩個空格 而且每行開頭和結(jié)尾也沒有空格 輸出格式 如果你的程序能確定誰是罪犯 則輸出他的名字 如果程序判斷出不止一個人可能是 罪犯 則輸出 Cannot Determine 如果程序判斷出沒有人可能成為罪犯 則輸出 Impossible 輸入樣例 3 1 5 MIKE CHARLES KATE MIKE I am guilty MIKE Today is Sunday CHARLES MIKE is guilty KATE I am guilty KATE How are you 輸出樣例 MIKE 25 56 題三題三 加分二叉樹加分二叉樹 問題描述 設(shè)一個 n 個節(jié)點的二叉樹 tree 的中序遍歷為 l 2 3 n 其中數(shù)字 1 2 3 n 為節(jié)點 編號 每個節(jié)點都有一個分?jǐn)?shù) 均為正整數(shù) 記第 j 個節(jié)點的分?jǐn)?shù)為 di tree 及它的每個 子樹都有一個加分 任一棵子樹 subtree 也包含 tree 本身 的加分計算方法如下 subtree 的左子樹的加分 subtree 的右子樹的加分 subtree 的根的分?jǐn)?shù) 若某個子樹為主 規(guī)定其加分為 1 葉子的加分就是葉節(jié)點本身的分?jǐn)?shù) 不考慮它的 空 子樹 試求一棵符合中序遍歷為 1 2 3 n 且加分最高的二叉樹 tree 要求輸出 1 tree 的最高加分 2 tree 的前序遍歷 輸入格式 第 1 行 一個整數(shù) n n 30 為節(jié)點個數(shù) 第 2 行 n 個用空格隔開的整數(shù) 為每個節(jié)點的分?jǐn)?shù) 分?jǐn)?shù) 100 輸出格式 第 1 行 一個整數(shù) 為最高加分 結(jié)果不會超過 4 000 000 000 第 2 行 n 個用空格隔開的整數(shù) 為該樹的前序遍歷 輸入樣例 5 5 7 1 2 10 輸出樣例 145 3 1 2 4 5 題四題四 傳染病控制傳染病控制 問題背景 近來 一種新的傳染病肆虐全球 蓬萊國也發(fā)現(xiàn)了零星感染者 為防止該病在蓬萊國 大范圍流行 該國政府決定不惜一切代價控制傳染病的蔓延 不幸的是 由于人們尚未完 全認(rèn)識這種傳染病 難以準(zhǔn)確判別病毒攜帶者 更沒有研制出疫苗以保護(hù)易感人群 于是 蓬萊國的疾病控制中心決定采取切斷傳播途徑的方法控制疾病傳播 經(jīng)過 WHO 世界衛(wèi) 生組織 以及全球各國科研部門的努力 這種新興傳染病的傳播途徑和控制方法已經(jīng)研究 消楚 剩下的任務(wù)就是由你協(xié)助蓬萊國疾控中心制定一個有效的控制辦法 26 56 問題描述 研究表明 這種傳染病的傳播具有兩種很特殊的性質(zhì) 第一是它的傳播途徑是樹型的 一個人 X 只可能被某個特定的人 Y 感染 只要 Y 不 得病 或者是 XY 之間的傳播途徑被切斷 則 X 就不會得病 第二是 這種疾病的傳播有周期性 在一個疾病傳播周期之內(nèi) 傳染病將只會感染一 代患者 而不會再傳播給下一代 這些性質(zhì)大大減輕了蓬萊國疾病防控的壓力 并且他們已經(jīng)得到了國內(nèi)部分易感人群 的潛在傳播途徑圖 一棵樹 但是 麻煩還沒有結(jié)束 由于蓬萊國疾控中心人手不夠 同 時也缺乏強(qiáng)大的技術(shù) 以致他們在一個疾病傳播周期內(nèi) 只能設(shè)法切斷一條傳播途徑 而 沒有被控制的傳播途徑就會引起更多的易感人群被感染 也就是與當(dāng)前已經(jīng)被感染的人有 傳播途徑相連 且連接途徑?jīng)]有被切斷的人群 當(dāng)不可能有健康人被感染時 疾病就中止 傳播 所以 蓬萊國疾控中心要制定出一個切斷傳播途徑的順序 以使盡量少的人被感染 你的程序要針對給定的樹 找出合適的切斷順序 輸入格式 輸入格式的第一行是兩個整數(shù) n 1 n 300 和 p 接下來 p 行 每一行有兩個整數(shù) i 和 j 表示節(jié)點 i 和 j 間有邊相連 意即 第 i 人和第 j 人之間有傳播途徑相連 其中節(jié)點 1 是已經(jīng)被感染的患者 輸出格式 只有一行 輸出總共被感染的人數(shù) 輸入樣例 7 6 1 2 1 3 2 4 2 5 3 6 3 7 輸出樣例 3 2004 年 第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題 提高組提高組 3 3 小時完成小時完成 27 56 一 津津的儲蓄計劃一 津津的儲蓄計劃 Save pas dpr c cpp 問題描述 津津的零花錢一直都是自己管理 每個月的月初媽媽給津津 300 元錢 津 津會預(yù)算這個月的花銷 并且總能做到實際花銷和預(yù)算的相同 為了讓津津?qū)W習(xí)如何儲蓄 媽媽提出 津津可以隨時把整百的錢存在她那 里 到了年末她會加上 20 還給津津 因此津津制定了一個儲蓄計劃 每個月 的月初 在得到媽媽給的零花錢后 如果她預(yù)計到這個月的月末手中還會有多 于 100 元或恰好 100 元 她就會把整百的錢存在媽媽那里 剩余的錢留在自己 手中 例如 11 月初津津手中還有 83 元 媽媽給了津津 300 元 津津預(yù)計 11 月的 花銷是 180 元 那么她就會在媽媽那里存 200 元 自己留下 183 元 到了 11 月 月末 津津手中會剩下 3 元錢 津津發(fā)現(xiàn)這個儲蓄計劃的主要風(fēng)險是 存在媽媽那里的錢在年末之前不能 取出 有可能在某個月的月初 津津手中的錢加上這個月媽媽給的錢 不夠這 個月的原定預(yù)算 如果出現(xiàn)這種情況 津津?qū)⒉坏貌辉谶@個月省吃儉用 壓縮 預(yù)算 現(xiàn)在請你根據(jù) 2004 年 1 月到 12 月每個月津津的預(yù)算 判斷會不會出現(xiàn)這 種情況 如果不會 計算到 2004 年年末 媽媽將津津平常存的錢加上 20 還 給津津之后 津津手中會有多少錢 輸入文件 輸入文件 save in 包括 12 行數(shù)據(jù) 每行包含一個小于 350 的非負(fù)整數(shù) 分 別表示 1 月到 12 月津津的預(yù)算 輸出文件 輸出文件 save out 包括一行 這一行只包含一個整數(shù) 如果儲蓄計劃實施 過程中出現(xiàn)某個月錢不夠用的情況 輸出 X X 表示出現(xiàn)這種情況的第一個月 否則輸出到 2004 年年末津津手中會有多少錢 樣例輸入 1 290 230 28 56 280 200 300 170 340 50 90 80 200 60 樣例輸出 1 7 樣例輸入 2 290 230 280 200 300 170 330 50 90 80 200 60 樣例輸出 2 1580 二 合并果子二 合并果子 fruit pas dpr c cpp 問題描述 在一個果園里 多多已經(jīng)將所有的果子打了下來 而且按果子的不同種類 分成了不同的堆 多多決定把所有的果子合成一堆 每一次合并 多多可以把兩堆果子合并到一起 消耗的體力等于兩堆果子 29 56 的重量之和 可以看出 所有的果子經(jīng)過 n 1 次合并之后 就只剩下一堆了 多多在合并果子時總共消耗的體力等于每次合并所耗體力之和 因為還要花大力氣把這些果子搬回家 所以多多在合并果子時要盡可能地 節(jié)省體力 假定每個果子重量都為 1 并且已知果子的種類數(shù)和每種果子的數(shù) 目 你的任務(wù)是設(shè)計出合并的次序方案 使多多耗費的體力最少 并輸出這個 最小的體力耗費值 例如有 3 種果子 數(shù)目依次為 1 2 9 可以先將 1 2 堆合并 新堆數(shù)目 為 3 耗費體力為 3 接著 將新堆與原先的第三堆合并 又得到新的堆 數(shù)目 為 12 耗費體力為 12 所以多多總共耗費體力 3 12 15 可以證明 15 為最小 的體力耗費值 輸入文件 輸入文件 fruit in 包括兩行 第一行是一個整數(shù) n 1 n 10000 表示 果子的種類數(shù) 第二行包含 n 個整數(shù) 用空格分隔 第 i 個整數(shù) ai 1 ai 20000 是第 i 種果子的數(shù)目 輸出文件 輸出文件 fruit out 包括一行 這一行只包含一個整數(shù) 也就是最小的體 力耗費值 輸入數(shù)據(jù)保證這個值小于 231 樣例輸入 3 1 2 9 樣例輸出 15 數(shù)據(jù)規(guī)模 對于 30 的數(shù)據(jù) 保證有 n 1000 對于 50 的數(shù)據(jù) 保證有 n 5000 對于全部的數(shù)據(jù) 保證有 n 10000 三 合唱隊形三 合唱隊形 chorus pas dpr c cpp 30 56 問題描述 N 位同學(xué)站成一排 音樂老師要請其中的 N K 位同學(xué)出列 使得剩下的 K 位同學(xué)排成合唱隊形 合唱隊形是指這樣的一種隊形 設(shè) K 位同學(xué)從左到右依次編號為 1 2 K 他們的身高分別為 T1 T2 TK 則他們的身高滿足 T1 Ti 1 TK 1 i K 你的任務(wù)是 已知所有 N 位同學(xué)的身高 計算最少需要幾位同學(xué)出列 可 以使得剩下的同學(xué)排成合唱隊形 輸入文件 輸入文件 chorus in 的第一行是一個整數(shù) N 2 N 100 表示同學(xué)的總數(shù) 第一行有 n 個整數(shù) 用空格分隔 第 i 個整數(shù) Ti 130 Ti 230 是第 i 位同學(xué) 的身高 厘米 輸出文件 輸出文件 chorus out 包括一行 這一行只包含一個整數(shù) 就是最少需要幾 位同學(xué)出列 樣例輸入 8 186 186 150 200 160 130 197 220 樣例輸出 4 數(shù)據(jù)規(guī)模 對于 50 的數(shù)據(jù) 保證有 n 20 對于全部的數(shù)據(jù) 保證有 n 100 四 蟲食算四 蟲食算 alpha pas dpr c cpp 問題描述 31 56 所謂蟲食算 就是原先的算式中有一部分被蟲子啃掉了 需要我們根據(jù)剩 下的數(shù)字來判定被啃掉的字母 來看一個簡單的例子 43 9865 045 8468 6633 44445506978 其中 號代表被蟲子啃掉的數(shù)字 根據(jù)算式 我們很容易判斷 第一行的兩 個數(shù)字分別是 5 和 3 第二行的數(shù)字是 5 現(xiàn)在 我們對問題做兩個限制 首先 我們只考慮加法的蟲食算 這里的加法是 N 進(jìn)制加法 算式中三個 數(shù)都有 N 位 允許有前導(dǎo)的 0 其次 蟲子把所有的數(shù)都啃光了 我們只知道哪些數(shù)字是相同的 我們將 相同的數(shù)字用相同的字母表示 不同的數(shù)字用不同的字母表示 如果這個算式 是 N 進(jìn)制的 我們就取英文字母表午的前 N 個大寫字母來表示這個算式中的 0 到 N 1 這 N 個不同的數(shù)字 但是這 N 個字母并不一定順序地代表 0 到 N 1 輸 入數(shù)據(jù)保證 N 個字母分別至少出現(xiàn)一次 BADC CRDA DCCC 上面的算式是一個 4 進(jìn)制的算式 很顯然 我們只要讓 ABCD 分別代表 0123 便可以讓這個式子成立了 你的任務(wù)是 對于給定的 N 進(jìn)制加法算式 求出 N 個不同的字母分別代表的數(shù)字 使得該加法算式成立 輸入數(shù)據(jù)保證有 且僅有一組解 輸入文件 輸入文件 alpha in 包含 4 行 第一行有一個正整數(shù) N N 26 后面的 3 行每行有一個由大寫字母組成的字符串 分別代表兩個加數(shù)以及和 這 3 個字 符串左右兩端都沒有空格 從高位到低位 并且恰好有 N 位 輸出文件 輸出文件 alpha out 包含一行 在這一行中 應(yīng)當(dāng)包含唯一的那組解 解 是這樣表示的 輸出 N 個數(shù)字 分別表示 A B C 所代表的數(shù)字 相鄰的 兩個數(shù)字用一個空格隔開 不能有多余的空格 32 56 樣例輸入 5 ABCED BDACE EBBAA 樣例輸出 1 0 3 4 2 數(shù)據(jù)規(guī)模 對于 30 的數(shù)據(jù) 保證有 N 10 對于 50 的數(shù)據(jù) 保證有 N 15 對于全部的數(shù)據(jù) 保證有 N 26 2005 年 第十二屆全國青少年信息學(xué)奧林匹克第十二屆全國青少年信息學(xué)奧林匹克 聯(lián)賽復(fù)賽試題聯(lián)賽復(fù)賽試題 NOIP2006NOIP2006 普及組 普及組 競賽時間 競賽時間 20062006 年年 1111 月月 1818 日日 下午下午 1 30 4 301 30 4 30 試題名稱試題名稱 randomrandomHappyHappycountcountsequencesequence 目錄目錄 randomrandomHappyHappycountcountsequencesequence 輸入文件名輸入文件名 random inrandom inhappy inhappy incount incount insequence insequence in 輸出文件名輸出文件名 random outrandom outhappy outhappy outcount outcount outsequence outsequence out 試題類型試題類型非交互式程序非交互式程序 題題 非交互式程序題非交互式程序題非交互式程序非交互式程序 題題 非交互式程序非交互式程序 題題 附加文件附加文件無無無無無無無無 時限時限1 1 秒秒1 1 秒秒1 1 秒秒1 1 秒秒 33 56 關(guān)于競賽中不同語言使用限制的說明關(guān)于競賽中不同語言使用限制的說明 一 關(guān)于使用一 關(guān)于使用 PascalPascal 語言與編譯結(jié)果的說明語言與編譯結(jié)果的說明 1 1 對于 對于 PascalPascal 語言的程序 當(dāng)使用語言的程序 當(dāng)使用 IDEIDE 和和 fpcfpc 編譯結(jié)果不一致時 以編譯結(jié)果不一致時 以 fpcfpc 的的 編譯結(jié)果為準(zhǔn) 編譯結(jié)果為準(zhǔn) 2 2 允許使用數(shù)學(xué)庫 允許使用數(shù)學(xué)庫 uses uses mathmath 子句子句 以及 以及 ansistringansistring 但不允許使用編譯開 但不允許使用編譯開 關(guān) 最后測試時關(guān) 最后測試時 pascalpascal 的范圍檢查開關(guān)默認(rèn)關(guān)閉 的范圍檢查開關(guān)默認(rèn)關(guān)閉 R Q S R Q S 也不支 也不支 持與優(yōu)化相關(guān)的選項 持與優(yōu)化相關(guān)的選項 二 關(guān)于二 關(guān)于 C C 語言中模板使用的限制說明語言中模板使用的限制說明 1 1 允許使用的部分 允許使用的部分 標(biāo)準(zhǔn)容器中的布爾集合 迭代器 串 流 相關(guān)的頭文件 2 2 禁止使用的部分 禁止使用的部分 序列 vector list deque 序列適配器 stack queue priority queue 關(guān)聯(lián)容器 map multimap set multiset 擬容器 valarray 散列容器 hash map hash set hash multimap hash multiset 所有的標(biāo)準(zhǔn)庫算法 相關(guān)頭文件 34 56 1 明明的隨機(jī)數(shù)明明的隨機(jī)數(shù) random pas c cpp 問題描述 明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查 為了實驗的客觀性 他 先用計算機(jī)生成了 N 個 1 到 1000 之間的隨機(jī)整數(shù) N 100 對于其中重復(fù) 的數(shù)字 只保留一個 把其余相同的數(shù)去掉 不同的數(shù)對應(yīng)著不同的學(xué)生的學(xué) 號 然后再把這些數(shù)從小到大排序 按照排好的順序去找同學(xué)做調(diào)查 請你協(xié) 助明明完成 去重 與 排序 的工作 輸入文件 輸入文件 random in 有 2 行 第 1 行為 1 個正整數(shù) 表示所生成的隨機(jī)數(shù) 的個數(shù) N 第 2 行有 N 個用空格隔開的正整數(shù) 為所產(chǎn)生的隨機(jī)數(shù) 輸出文件 輸出文件 random out 也是 2 行 第 1 行為 1 個正整數(shù) M 表示不相同的 隨機(jī)數(shù)的個數(shù) 第 2 行為 M 個用空格隔開的正整數(shù) 為從小到大排好序的不相 同的隨機(jī)數(shù) 輸入樣例 10 20 40 32 67 40 20 89 300 400 15 輸出樣例 8 15 20 32 40 67 89 300 400 35 56 2 開心的金明開心的金明 happy pas c cpp 問題描述 金明今天很開心 家里購置的新房就要領(lǐng)鑰匙了 新房里有一間他自己專 用的很寬敞的房間 更讓他高興的是 媽媽昨天對他說 你的房間需要購買 哪些物品 怎么布置 你說了算 只要不超過 N 元錢就行 今天一早金明就 開始做預(yù)算 但是他想買的東西太多了 肯定會超過媽媽限定的 N 元 于是 他把每件物品規(guī)定了一個重要度 分為 5 等 用整數(shù) 1 5 表示 第 5 等最重要 他還從因特網(wǎng)上查到了每件物品的價格 都是整數(shù)元 他希望在不超過 N 元 可以等于 N 元 的前提下 使每件物品的價格與重要度的乘積的總和最大 設(shè)第 j 件物品的價格為 v j 重要度為 w j 共選中了 k 件物品 編號 依次為 j1 j2 jk 則所求的總和為 v j1 w j1 v j2 w j2 v jk w jk 其中 為乘號 請你幫助金明設(shè)計一個滿足要求的購物單 輸入文件 輸入文件 happy in 的第 1 行 為兩個正整數(shù) 用一個空格隔開 N m 其中 N 30000 表示總錢數(shù) m 25 為希望購買物品的個數(shù) 從第 2 行到