第二十三屆全國(guó)信息學(xué)奧林匹克競(jìng)賽試題(NOI2006第二試)VIP

第二十三屆全國(guó)信息學(xué)奧林匹克競(jìng)賽 NOI 2006 第二試 競(jìng)賽時(shí)間：2006 年 7 月 26 日上午 8:00-13:00 題目名稱 最大獲利 聰明的導(dǎo)游 神奇口袋 目錄 profit guide bag 可執(zhí)行文件名 profit N/A bag 輸入文件名 profit.in guide1.inguide10.in bag.in 輸出文件名 profit.out guide1.outguide10.out bag.out 每個(gè)測(cè)試點(diǎn)時(shí)限 2秒 N/A 1 秒 測(cè)試點(diǎn)數(shù)目 10 10 10 每個(gè)測(cè)試點(diǎn)分值 10 10 10 是否有部分分 無(wú) 有 無(wú) 題目類型 傳統(tǒng) 提交答案 傳統(tǒng) 提交源程序須加后綴 對(duì)于 Pascal 語(yǔ)言 profit.pas N/A bag.pas 對(duì)于 C 語(yǔ)言 profit.c N/A bag.c 對(duì)于 C+ 語(yǔ)言 profit.cpp N/A bag.cpp 注意：最終測(cè)試時(shí)，所有編譯 命令均不打開(kāi)任何優(yōu)化開(kāi)關(guān) 除了提交答案題以外，其余兩題只需要向輸出文件輸出一行，行內(nèi)不得有多余空白字符，行末須有一個(gè)換行/回車符，格式不對(duì)不能得分。 清北學(xué)堂 四川 綿陽(yáng) 2006-7-26 第 23 屆全國(guó)信息學(xué)奧林匹克競(jìng)賽 第二試 profit 第 2 頁(yè) 共 7 頁(yè) 最大獲利 【問(wèn)題描述】 新的技術(shù)正沖擊著手機(jī)通訊市場(chǎng)，對(duì)于各大運(yùn)營(yíng)商來(lái)說(shuō)，這既是機(jī)遇，更是挑戰(zhàn)。 THU 集團(tuán)旗下的 CS&T 通訊公司在新一代通訊技術(shù)血戰(zhàn)的前夜，需要做太多的準(zhǔn)備工作，僅就站址選擇一項(xiàng)，就需要完成前期市場(chǎng)研究、站址勘測(cè)、最優(yōu)化等項(xiàng)目。 在前期市場(chǎng)調(diào)查和站址勘測(cè)之后， 公司得到了一共 N 個(gè)可以作為通訊信號(hào)中轉(zhuǎn)站的地址，而由于這些地址的地理位置差異，在不同的地方建造通訊中轉(zhuǎn)站需要投入的成本也是不一樣的，所幸在前期調(diào)查之后這些都是已知數(shù)據(jù)：建立第 i個(gè)通訊中轉(zhuǎn)站需要的成本為 Pi（ 1 i N） 。 另外公司調(diào)查得出了所有期望中的用戶群，一共 M 個(gè)。關(guān)于第 i 個(gè)用戶群的信息概括為 Ai, Bi和 Ci：這些用戶會(huì)使用中轉(zhuǎn)站 Ai和中轉(zhuǎn)站 Bi進(jìn)行通訊，公司可以獲益 Ci。 （ 1 i M, 1 Ai, Bi N） THU 集團(tuán)的 CS&T 公司可以有選擇的建立一些中轉(zhuǎn)站（投入成本） ，為一些用戶提供服務(wù)并獲得收益（獲益之和） 。那么如何選擇最終建立的中轉(zhuǎn)站才能讓公司的凈獲利最大呢？（凈獲利 = 獲益之和 投入成本之和） 【輸入格式】 輸入文件中第一行有兩個(gè)正整數(shù) N 和 M 。 第二行中有 N 個(gè)整數(shù)描述每一個(gè)通訊中轉(zhuǎn)站的建立成本，依次為 P1, P2, , PN 。 以下 M 行，第 (i + 2)行的三個(gè)數(shù) Ai, Bi和 Ci描述第 i 個(gè)用戶群的信息。 所有變量的含義可以參見(jiàn)題目描述。 【輸出格式】 你的程序只要向輸出文件輸出一個(gè)整數(shù)，表示公司可以得到的最大凈獲利。 【輸入樣例】 5 5 1 2 3 4 5 1 2 3 2 3 4 1 3 3 1 4 2 4 5 3 清北學(xué)堂 四川 綿陽(yáng) 2006-7-26 第 23 屆全國(guó)信息學(xué)奧林匹克競(jìng)賽 第二試 profit 第 3 頁(yè) 共 7 頁(yè) 【輸出樣例】 4 【樣例說(shuō)明】 選擇建立 1、 2、 3 號(hào)中轉(zhuǎn)站，則需要投入成本 6，獲利為 10，因此得到最大收益 4。 【評(píng)分方法】 本題沒(méi)有部分分，你的程序的輸出只有和我們的答案完全一致才能獲得滿分，否則不得分。 【數(shù)據(jù)規(guī)模和約定】 80%的數(shù)據(jù)中： N 200， M 1 000。 100%的數(shù)據(jù)中： N 5 000， M 50 000， 0 Ci 100， 0 Pi 100。 清北學(xué)堂 四川 綿陽(yáng) 2006-7-26第 23 屆全國(guó)信息學(xué)奧林匹克競(jìng)賽 第二試 guide 第 4 頁(yè) 共 7 頁(yè) 聰明的導(dǎo)游 【問(wèn)題描述】 小佳最近迷上了導(dǎo)游這個(gè)工作，一天到晚想著帶游客參觀各處的景點(diǎn)。正好M 市在舉行 NOI，來(lái)參觀的人特別的多。不少朋友給小佳介紹了需要導(dǎo)游的人。 M 市有 n 個(gè)著名的景點(diǎn)，小佳將這些景點(diǎn)從 1 至 n 編號(hào)。有一些景點(diǎn)之間存在雙向的路。小佳可以讓游客們?cè)谌魏我粋€(gè)景點(diǎn)集合，然后帶著他們參觀，最后也可以在任何一個(gè)景點(diǎn)結(jié)束參觀。不過(guò)，來(lái)參觀的游客們都不愿去已經(jīng)參觀過(guò)的地方。所以，小佳不能帶游客們經(jīng)過(guò)同一個(gè)景點(diǎn)兩次或兩次以上。 小佳希望你幫助他設(shè)計(jì)一個(gè)方案 , 走可行的路線 , 帶游客們參觀盡可能多的地方。 【輸入格式】 輸入文件為 guide1.inguide10.in，第一行為兩個(gè)整數(shù) n,m，分別表示景點(diǎn)數(shù)和路的條數(shù)。接下來(lái) m 行，每行兩個(gè)整數(shù) a,b，表示景點(diǎn) a 和景點(diǎn) b 之間有一條雙向路。 【輸出格式】 你需要將答案輸出到 guide1.outguide10.out 中， guide?.out 為對(duì)應(yīng) guide?.in的答案。輸出的第一行為 p，表示你能找到的路徑所經(jīng)過(guò)的景點(diǎn)個(gè)數(shù)。接下來(lái) p行，每行一個(gè)整數(shù)，按順序表示你所找到的路徑上的每一個(gè)景點(diǎn)。 【說(shuō)明】 這是一道提交答案式的題目，你不需要提供任何源代碼，只需要將自己的輸出文件放在與 *.in 同一個(gè)目錄即可。 【樣例】 樣例輸入 樣例輸出 5 5 1 2 3 2 2 4 2 5 4 5 4 1 2 4 5 清北學(xué)堂 四川 綿陽(yáng) 2006-7-26第 23 屆全國(guó)信息學(xué)奧林匹克競(jìng)賽 第二試 guide 第 5 頁(yè) 共 7 頁(yè) 【樣例說(shuō)明】 題目可能有多解，該樣例有 4 個(gè)解，你只需輸出其中任何一個(gè)解。 解 1 解 2 解 3 解 4 4 1 2 4 5 4 1 2 5 4 4 3 2 4 5 4 3 2 5 4 【評(píng)分方法】 你的評(píng)分將由你的答案與標(biāo)準(zhǔn)答案之間的差異來(lái)給定。設(shè)你的答案正確且參觀的景點(diǎn)數(shù)為 x，我們所給出的結(jié)果為 ans，則按下表計(jì)算你的得分： 得分 條件 得分 條件 12 x ans 5 x ans * 0.93 10 x = ans 4 x ans * 0.9 9 x ans 1 3 x ans * 0.8 8 x ans 2 2 x ans * 0.7 7 x ans 3 1 x ans * 0.5 6 x ans * 0.95 0 x ans * 0.5 如果有多項(xiàng)滿足，則取滿足條件中的最高得分。 清北學(xué)堂 四川 綿陽(yáng) 2006-7-26第 23 屆全國(guó)信息學(xué)奧林匹克競(jìng)賽 第二試 bag 第 6 頁(yè) 共 7 頁(yè) 神奇口袋 【問(wèn)題描述】 Plya 獲得了一個(gè)奇妙的口袋，上面寫著人類難以理解的符號(hào)。 Plya 看得入了迷，冥思苦想，發(fā)現(xiàn)了一個(gè)神奇的模型（被后人稱為 Plya 模型 )。為了生動(dòng)地講授這個(gè)神奇的模型，他帶著學(xué)生們做了一個(gè)虛擬游戲： 游戲開(kāi)始時(shí)，袋中裝入 a1個(gè)顏色為 1 的球， a2個(gè)顏色為 2 的球， ， at個(gè)顏色為 t 的球，其中 )1( tiZai+。 游戲開(kāi)始后，每次嚴(yán)格進(jìn)行如下的操作： 從袋中隨機(jī)的抽出一個(gè)小球（袋中所有小球被抽中的概率相等） ，Plya 獨(dú)自觀察這個(gè)小球的顏色后將其放回 ， 然后再把 d 個(gè)與其顏色相同的小球放到口袋中。 設(shè) ci表示第 i 次抽出的小球的顏色 )1( tci ， 一個(gè)游戲過(guò)程將會(huì)產(chǎn)生一個(gè) 顏色序列 (c1,c2,cn,)。 Plya 把游戲開(kāi)始時(shí) t 種顏色的小球每一種的個(gè)數(shù) a1,a2,at告訴了所有學(xué)生。然后他問(wèn)學(xué)生：一次游戲過(guò)程產(chǎn)生的顏色序列滿足下列條件的概率有多大？ 1212,inx xxixncycy cy cy= = =LL 其中 0x1x2xn， 1yit 。換句話說(shuō)，已知 (t , n , d , a1,a2,at , x1,y1,x2,y2,.,xn,yn)，你要回答有多大的可能性會(huì)發(fā)生下面的事件： “對(duì)所有k,1kn，第 xk次抽出的球的顏色為 yk”。 【輸入格式】 第一行有三個(gè)正整數(shù) t， n， d； 第二行有 t 個(gè)正整數(shù) a1,a2,at，表示游戲開(kāi)始時(shí)口袋里 t 種顏色的球，每種球的個(gè)數(shù)。 以下 n 行，每行有兩個(gè)正整數(shù) xi,yi，表示第 xi次抽出顏色為的 yi球。 【輸出格式】 要求用分?jǐn)?shù)形式輸出（顯然此概率為有理數(shù)） 。輸出文件包含一行，格式為：分子 /分母。同時(shí)要求輸出最簡(jiǎn)形式（分子分母互質(zhì)） 。特別的，概率為 0 應(yīng)輸出清北學(xué)堂 四川 綿陽(yáng) 2006-7-26第 23 屆全國(guó)信息學(xué)奧林匹克競(jìng)賽 第二試 bag 第 7 頁(yè) 共 7 頁(yè) 0/1，概率為 1 應(yīng)輸出 1/1。 【樣例】 樣例 1 的輸入 樣例 1 的輸出 2 3 1 1 1 1 1 2 2 3 1 1/12 樣例 2 的輸入 樣例 2 輸出 3 1 2 1 1 1 5 1 1/3 【樣例 1 說(shuō)明】 初始時(shí)，兩種顏色球數(shù)分別為 (1, 1)，取出色號(hào)為 1 的球的概率為 1/2；第二次取球之前，兩種顏色球數(shù)分別為 (2, 1)，取出