第二十三屆全國信息學奧林匹克競賽試題(NOI2006第二試)

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