歷屆noip提高組復(fù)賽試題.doc

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