【文章內(nèi)容簡介】 寶石 / 1996年提高組第3題挖地雷【問題描述】在一處原始森林中，發(fā)現(xiàn)了N個藏有寶石的山洞，這N個山洞以1至N編號。某些山洞間可能會有通道相連，山洞間的通道是單向的，編號較小的山洞可以通過通道走至編號較大的山洞，編號較大的山洞不可以通過通道走至編號較小的山洞。你可以選擇任意一個山洞進入，選擇一條通道，進入下一個較大編號的山洞，…，最后從某個山洞出來，并獲得所有經(jīng)過的山洞中的寶石。從外面只能進入一次，然后從一個山洞至另一個山洞，直至走出山洞?，F(xiàn)在告訴你每個山洞中的寶石數(shù)，以及山洞之間的通道情況，求最多能取得多少寶石？【輸入】。 第一行有兩個整數(shù)n和m，分別表示山洞數(shù)和通道數(shù)，兩數(shù)間以一個空格分隔。 第二行有n個整數(shù)，第一個數(shù)表示第一個山洞的寶石數(shù),第二個數(shù)表示第二個山洞的寶石數(shù),…，第n個數(shù)表示第n個山洞的寶石數(shù)。這n個數(shù)間互相以一個空格分隔。 以下m行，每行描述兩個山洞間有一條從編號較小山洞通向編號較大山洞的單向通道。每一行的兩個整數(shù)a和b,可能表示山洞a至山洞b間的單向通道，也可能表示山洞b至山洞a間的單向通道。a和b間有一個空格分隔。【輸出】 ，該行只有一個整數(shù)，表示最多能獲得的寶石數(shù)?！緮?shù)據(jù)限制】本題共有10組測試數(shù)據(jù)，每組10分，共100分，對于所有的數(shù)據(jù)，獲得的寶石總數(shù)不會超過210930%的數(shù)據(jù), 1≤n≤1000，0≤m≤10000100%的數(shù)據(jù), 1≤n≤20000，0≤m≤100000【輸入樣例】 【輸出樣例】5 6 2710 8 4 7 61 31 21 43 43 54 5題30。1999提高組第1題攔截導彈【問題描述】某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)）：1）計算這套系統(tǒng)最多能攔截多少導彈；2）如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)?！据斎敫袷健?包括若干以空格分隔的正整數(shù),表示來襲的導彈的高度.【輸出格式】。第一行只有一個正整數(shù),表示最多能攔截的導彈數(shù)。第二行也只有一個正整數(shù),表示要攔截所有導彈最少要配備的系統(tǒng)數(shù)?！据斎霕永? 389 207 155 300 299 170 158 65【輸出樣例】62題31。2004年提高組第3題合唱隊形【問題描述】N位同學站成一排，音樂老師要請其中的(NK)位同學出列，使得剩下的K位同學排成合唱隊形。合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1...TiTi+1…TK(1=i=K)。你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。【輸入格式】。第一行是一個整數(shù)n(2=n=100)，表示同學的總數(shù)。第二行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti(130=Ti=230)是第i位同學的身高(厘米)?！据敵龈袷健浚@一行只包含一個整數(shù)，就是最少需要幾位同學出列。 【輸入樣例】8186 186 150 200 160 130 197 220 【輸出樣例】4【數(shù)據(jù)規(guī)模】對于50％的數(shù)據(jù)，保證有n=20；對于全部的數(shù)據(jù)，保證有n=100。題32。渡河Problem iRabbit的國家被一條河流(河流是直的)分成南北兩岸，南北兩岸各有N個城市。北岸的每一個城市有一個唯一的友好城市在南岸，且他們的友好城市彼此不同。為了城市關系的發(fā)展，每對城市之間都想要開通輪渡。由于河面上常常有霧。iRabbit決定禁止船只航線相交。以避免發(fā)生安全事故。iRabbit希望能在保證安全的情況下，盡可能多地開通航線。由于N非常大（1=N=2004），所以必須用程序解決。iRabbit因為備戰(zhàn)競賽，所以十分繁忙，沒有時間來編寫程序，所以交給手下的TCR和sceoy解決?？墒撬麄儍蓚€想了很久都沒有想出答案，所以想請你來幫助解決。Input ：N（1≤N≤2004）。接下來N行,每行兩個數(shù)A,B。表示這一對友好城市與河源頭的距離(不過100000)，其中A代表北岸城市、B代表南岸城市。Output 。表示可以開通輪渡的最大線路數(shù)。Sample Input Sample Output7 422 4 2 610 3 15 129 817 174 2a[I]b[I]題33。最長公共子序列：勇闖黃金十二宮……射手宮同濟ACM第1108題Problem “已知艾爾里斯和弟弟艾爾里亞的基因基本相同，由于基因表達起來不方便，所以就用n個數(shù)字來表示。(因為至今共發(fā)現(xiàn)100000種基因，所以每個數(shù)字都=100000)兄弟之間的基因個數(shù)是相同的，就是說他們都有n個數(shù)字。且對于每個人，這n個數(shù)字互不相同?，F(xiàn)在要求兄弟之間基因的最長公共部分?？梢圆贿B續(xù)。” Input ，為n(1=n=100000) 下面2行，每行n個數(shù)字，表示了一個人的所有基因。，為他們兩人基因的最長公共部分的長度。Sample Input Sample Output7 31 2 3 4 5 6 77 6 5 4 1 2 3題38?！締栴}背景】A公司在南極大陸發(fā)現(xiàn)了一個稀有金屬礦，該礦沿直線分布，共有n個點，每個點有一定量的礦藏。由于覆蓋著冰塊，不能從中間開采，只能從兩頭開采。由于該稀有金屬的在地球上存量非常稀少，市場上價格越來越高，已知開采第一天的價格為1，第二天的價格為2，依次類推。A公司決定每天從兩頭選擇一頭開采出所有該點的礦藏?！据斎敫袷健浚旱谝恍?一個整數(shù)n，代表有n個礦點。第二行:n個整數(shù)，代表每個礦點的礦藏量。【輸出格式】，該行只有一個整數(shù)，代表開采出所有礦藏最多能得到的錢數(shù)。【樣例輸入】 【樣例輸出】4 211 2 3 1【數(shù)據(jù)規(guī)?！? n=1000，每點礦藏數(shù)不超過109，最多能得到的錢數(shù)1012。區(qū)域動規(guī)：題13. 2003年提高組第3題加分二叉樹【問題描述】 設一個n個節(jié)點的二叉樹tree的中序遍歷為(l,2,3,…,n),其中數(shù)字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第j個節(jié)點的分數(shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：subtree的左子樹的加分 subtree的右子樹的加分＋subtree的根的分數(shù) 若某個子樹為空,規(guī)定其加分為1,葉子的加分就是葉節(jié)點本身的分數(shù)。不考慮它的空子樹。試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；（1）tree的最高加分（2）tree的前序遍歷 【輸入格式】 第1行：一個整數(shù)n(n＜30)為節(jié)點個數(shù)。第2行：n個用空格隔開的整數(shù),為每個節(jié)點的分數(shù)(分數(shù)＜100）?！据敵龈袷健康?行：一個整數(shù)，為最高加分（結果不會超過4,000,000,000）。第2行：n個用空格隔開的整數(shù)，為該樹的前序遍歷。 【輸入樣例】55 7 1 2 10【輸出樣例】145 3 1 2 4 5題14。2000年普及組第3題乘積最大問題描述： 今年是國際數(shù)學聯(lián)盟確定的“2000——世界數(shù)學年”,又恰逢我國著名數(shù)學家華羅庚先生 誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇,組織了一場別開生面的數(shù)學智力競賽的活動,你的一個好朋友XZ也有幸得以參加?；顒又?主持人給所有參加活動的選手出了這樣一道題目：設有一個長度為N的數(shù)字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：有一個數(shù)字串：312， 當N=3，K=1時會有以下兩種分法： 1) 3*12=36 2) 31*2=62 這時，符合題目要求的結果是：31*2=62 現(xiàn)在，請你幫助你的好朋友XZ設計一個程序，求得正確的答案。輸入共有兩行：第一行共有2個自然數(shù)N，K（6≤N≤40，1≤K≤6）第二行是一個長度為N的數(shù)字串。輸出所求得的最大乘積（一個自然數(shù)）。樣例輸入4 21231樣例輸出62題15。NOIP2003年普及組第2題數(shù)字游戲（) 【問題描述】24131 丁丁最近沉迷于一個數(shù)字游戲之中。這個游戲看似簡單,但丁丁在研究了許多天之后卻發(fā)覺原來在簡單的規(guī)則下想要贏得這個游戲并不那么容易。游戲是這樣的,在你面前有一圈整數(shù)(一共n個),你要按順序?qū)⑵浞譃閙個部分,各部分內(nèi)的數(shù)字相加, 相加所得的m個結果對10取模后再相乘,最終得到一個數(shù)k。游戲的要求是使你所得的k最大或者最小。例如,對于下面這圈數(shù)字（n=4，m=2）：當要求最小值時,((21) mod 10)((4+3) mod 10)=17=7,要求最大值時,為((2+4+3) mod 10)(1 mod 10)=99=81。特別值得注意的是,無論是負數(shù)還是正數(shù),對10取模的結果均為非負值。丁丁請你編寫程序幫他贏得這個游戲。 【輸入】 ，n（1≤n≤50）和m（1≤m≤9）。 以下n行每行有個整數(shù),其絕對值不大于104,按順序給出圈中的數(shù)字,首尾相接?！据敵觥?各包含一個非負整數(shù)。第一行是你程序得到的最小值，第二行是最大值?！据斎霕永? 24312【輸出樣例】781題16。NOIP2001年提高組第3題統(tǒng)計單詞個數(shù)() 問題描述 給出一個長度不超過200的由小寫英文字母組成的字母串(約定。該字串以每行20個字母的方式輸入,且保證每行一定為20個)。要求將此字母串分成k份(1k=40),且每份中包含的單詞個數(shù)加起來總數(shù)最大(每份中包含的單詞可以部分重疊。當選用一個單詞之后,其第一個字母不能再用。例如字符串this中可包含this和is,選用this之后就不能包含th)。單詞在給出的一個不超過6個單詞的字典中。要求輸出最大的個數(shù)。輸入：，其格式如下：第一行有二個正整數(shù)(p，k),表示輸入字串有p行。分為k個部分。接下來的p行，每行均有20個字符。再接下來有一個正整數(shù)s，表示字典中單詞個數(shù)。(1=s=6)接下來的s行，每行均有一個單詞。輸出：,該行只有一個整數(shù),表示得到的最多單詞個數(shù)。 樣例輸入： 1 3thisisabookyouar