1、IOI2010 中國國家隊選拔賽CTSC 2010 Day1競賽時間：2010 年 5 月 4 日上午 8:00-13:00提交源程序須加后綴注意：最終測試時，所有編譯命令均不打開任何優(yōu)化開關(guān)第 1 頁 共 7 頁對于Pascal 語言galaxy.pasgo.pasoptimize.pas對于C語言galaxy.cgo.coptimize.c對于C+語言galaxy.cppgo.cppoptimize.cpp題目名稱星際旅行三國圍棋擂臺賽性能優(yōu)化目錄galaxygooptimize可執(zhí)行文件名galaxygooptimize輸入文件名galaxy.ingo.inoptimize.in輸出文件

2、名galaxy.outgo.outoptimize.out每個測試點時限1 秒3 秒15 秒內(nèi)存限制256M256M256M測試點數(shù)目102010每個測試點分值10510是否有部分分無無無題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)附加文件無無無星際旅行【問題描述】公元 3000 年，地球已經(jīng)攻占了系內(nèi)的 N 個星球，出于的考慮，僅僅在星球間建立了 N-1 條雙向時空隧道保證任意兩個星球之間互相可達(dá)。出于管理上的考慮，第 i 個星球的行政長官要求每個公民在一年內(nèi)不得從該星球利用時空隧道次數(shù)超過 Hi 次（這一統(tǒng)計是基于離開次數(shù)統(tǒng)計的，如果你已經(jīng)使 用從該星球離開過 Hi 次，那么這一年內(nèi)你就不能再使用時空隧道離開這個

3、星球了）。Louis Paosen 是一個星際旅行家，他希望能使用盡量多次的時空隧道，但又不希望最終被迫的星球條件太過惡劣。所以他希望能知道對于每個星球 i，若從 0 號星球出發(fā)，最終以 i 號星球為終點，這樣的星際旅行途中最多可以使用多少次時空隧道?！据斎胛募枯斎胛募?galaxy.in 的第一行包含一個整數(shù) N。接下來的一行包含 N 個整數(shù) Hi，分別表示每個星球的離開次數(shù)限制。接下來 N-1 行每行兩個整數(shù)，表示這兩個星球之間有時空隧道連接。星球的 從 0 開始，Louis Paosen 一開始在 0 號星球?！据敵鑫募枯敵鑫募?galaxy.out。文件包含 N 行，每行一個整數(shù)

4、，表示如果最終旅行結(jié)束在這個星球，最多可以使用時空隧道的次數(shù)。【樣例輸入】32016 212【樣例輸出】878【數(shù)據(jù)規(guī)模】40%的數(shù)據(jù)N500100%的數(shù)據(jù)中 N50000。所有星球的離開次數(shù)限制滿足 1Hi40000，且每個星球的 Hi 大于等于與該星球直接相連的星球數(shù)（即度數(shù)）。第 2 頁 共 7 頁三國圍棋擂臺賽【問題描述】一年一度的“農(nóng)心杯”三國圍棋擂臺賽是世界上最高水平的圍棋比賽，也是圍棋界最激動人心的較量。本題就是建立在這一比賽的規(guī)則之上。三國圍棋擂臺賽是三個國家的代表隊之間的比賽，下面簡要介紹一下比賽的規(guī)則：1.不妨設(shè)三個國家分別為 A、B 和 C，每個國家各有 n 名選手（在上

5、述的實際比賽中 n = 5），分別稱其為 A1，A2， An，B1，B2， Bn，C1， C2， Cn。每場比賽都能分出勝負(fù)。每場比賽的負(fù)者遭到淘汰。每隊第一位出場的選手都已經(jīng)確定為每隊的第 n 位選手，即 An、Bn 和 Cn。通過抽簽等概率地選出一支隊伍。該隊將在第一輪中輪空，而剩下的兩支隊伍的第 n 位選手將進(jìn)行第一場比賽。第一場比賽的勝者（這里的勝者是指贏得該局比賽的選手，下同）與輪空隊伍的第 n 位選手進(jìn)行第二場比賽。比如在第一場比賽中 Cn 戰(zhàn)勝了 An，則第二場則由 Cn 對陣 Bn。從第三場比賽開始，前一場比賽未參加的隊伍將選出一個未被淘汰的選手與上一場比賽的勝者進(jìn)行下一場比賽

6、。這個過程將一直進(jìn)行，直到某個隊伍的全部參賽選手都被淘汰為止。 當(dāng)只有兩支隊伍的時候，每場比賽后，由負(fù)方選擇一位未被淘汰的選手與勝者進(jìn)行下一場比賽。當(dāng)兩支隊伍中的任意一隊的全部選手均被淘汰后比賽結(jié)束，余下的那支隊伍將獲得農(nóng)心杯。2.3.4.5.6.7.8.9.新一屆的比賽就要開始了。你作為 A 隊的領(lǐng)隊，在比賽開始前已經(jīng)統(tǒng)計了這 3n 位選手之間的勝率即對于來自不同隊伍的兩個選手 Q 和 R， Q 戰(zhàn)勝 R 的概率為 p（0 ），且 R 戰(zhàn)勝 Q 的概率為 。已知由于你所在的國家實力超群，可以認(rèn)為剩下的兩只隊伍都將矛頭對準(zhǔn)了你。 B、C 隊的每個決策，即派出選手的順序的目的都是使你所在的國家（

7、A 隊）奪冠的概率盡可能小，而 A 隊的決策的目的必然是使最后奪冠的概率盡可能大。你要做的事情就是計算出在這種極為不利的情況下，在提下，A 隊奪冠的期望 EA。都做出最優(yōu)決策的前關(guān)于期望的計算：設(shè)現(xiàn)在在場上比賽的人是 Q 和 R，Q 勝 R 的概率為 p，則此時 A 隊勝率的期望 = 1 + ( ) 2其中1為 Q 勝 R 后 A 隊奪冠的期望，2為 R 勝 Q 后 A 隊奪冠的期望。1、2則同樣使用上式遞歸計算。A 隊的決策會盡可能使這個期望盡可能大，而 B、C 隊則會使這個期望盡可能小。當(dāng) B、C 隊的全部選手都被淘汰后奪冠期望為 1，A 隊所有隊員被淘汰后期望為 0。例如當(dāng)每隊有 3 位

8、參賽選手時，相互之間的勝率由如下的 3 個3 3的矩陣給出，其中矩陣中的每個數(shù)值 p 為所在行選手對于所在列選手的勝率，所在列選第 3 頁 共 7 頁手對于所在行選手的勝率為 。B11.00.50.5B20.01.00.5B30.51.00.5C10.50.50.5C20.50.00.5C31.00.50.5C10.50.50.5C20.00.50.5C31.00.50.5A1A2 A3A1A2 A3B1B2 B3三支隊的第三位選手的水平相同，在第兩局比賽后，三支隊的選手獲勝的概率是相同的。假設(shè)第二局獲勝的是 B3，第三局輪到 A 隊出場。這時出 A1 和 A2 兩種選擇?？梢耘湃绻沙?A2

9、，雖然第三局一定可以戰(zhàn)勝 B3（勝率為 100%），但是 C 隊會在第四場比賽中派出 C2，A2 對于 C2 必?。▌俾蕿?0），第五場中 B 隊會讓 B1 出場，第六場 A1 只能出場，這時對 A1 必勝的 B2 還未登場，因此 A1 遲早會遭到淘汰，A隊奪冠的概率就為 0。如果派出 A1，雖然本局對于 B3 比賽只有 50%的勝率，但是奪冠的概率為 6.25%；因此在第三場應(yīng)該派出 A1。根據(jù)第三場比賽的參賽選手的六種情況，最后奪冠的期望為：(6.25% + 3. 25% + 8.75% + 25% + 60.9375% + 50%)6= 27.34375%【輸入文件】輸入文件為go.in

10、。第一行包括一個整數(shù) n，表示每隊的選手?jǐn)?shù)。第二行到第 n + 1 行每行包含 n 個實數(shù)，整體為一個 的矩陣，表示 A 隊對 B 隊的勝率。其中第 i + 1 行的第 j 個數(shù)表示選手 Ai 對選手 Bj 時的勝率。第 n+2 行為空行。第 n + 3 行到第 2n + 2 行每行包含 n 個實數(shù)，同樣為一個 的矩陣，表示 A 隊對 C 隊的勝率。其中第 i + n + 2 行的第 j 個數(shù)表示選手 Ai 對選手 Cj 時的勝率。第 2n + 3 行為空行。第 2n + 4 行到第 3n + 3 行每行包含 n 個實數(shù)，整體為一個 的矩陣，表示 B 隊對 C 隊的勝率。其中第 i + 2n

11、+ 3 行的第 j 個數(shù)表示選手 Bi 對選手 Cj 時的勝率。【輸出文件】輸出文件 go.out 僅包含一個實數(shù)，保留 6 位小數(shù)，表示 A 隊獲得冠軍的概率?！緲永斎搿?1.00.50.50.01.00.50.51.00.5第 4 頁 共 7 頁0.50.50.50.50.00.51.00.50.50.50.50.50.00.50.51.00.50.5【樣例輸出】0.273438【數(shù)據(jù)規(guī)模】30%的數(shù)據(jù)中，n 4。40%的數(shù)據(jù)中，n 5。100%的數(shù)據(jù)中，n 7。對于 10%的數(shù)據(jù)有三個勝率矩陣中，每個矩陣的元素都相同，但不同矩陣的數(shù)字可能不同。第 5 頁 共 7 頁性能優(yōu)化【問題描述】

12、程序員正在開發(fā)一套大型軟件，軟件中有一段程序，用偽代碼描述如下(假設(shè)所有變量初值均為 0，并且假定其中的數(shù)據(jù)類型均不會出現(xiàn)溢出)：Input 0, , , , 0, , , , For 0 0, For 0 to For 0 to For 0 to + , ( + ) mod = + , ( + ) mod + , Output , 0mod ( + ), , mod ( + ), , , mod ( + )的效率非常低，它的時間復(fù)雜度高達(dá)(2)。他想讓你幫但是，這忙優(yōu)化一下這個程序，當(dāng)然要求輸出相同的結(jié)果。為了使問題更簡單，他保證輸入的能表示成若干個不超過 10 的正整數(shù)的乘積，并且 + 是質(zhì)數(shù)?！据斎胛募枯斎胛募ptimize.in 第一行包含兩個非負(fù)整數(shù), 。接下來一行包含個非負(fù)整數(shù)0, , , 。第三行包含個非負(fù)整數(shù) 0, , , ?！据敵鑫募枯敵鑫募ptimize.out 包含行，每行包含一個數(shù)。第行為, mod (