課件案例全國(guó)賽day

1、45/ 航空【問(wèn)題描述】世博期間，的航空客運(yùn)量大大超過(guò)了平時(shí)，隨之而來(lái)的航空也頻頻發(fā)生。最近，小 X 就因?yàn)楹娇招?X 表示很不滿意。，連續(xù)兩次在機(jī)場(chǎng)被延誤超過(guò)了兩小時(shí)。對(duì)此，在這次來(lái)煙臺(tái)的關(guān)于航空，小 X 不幸又一次碰上了航空。于是小 X 開始思考。假設(shè)目前被延誤航班共有 n 個(gè)，為 1 至 n。機(jī)場(chǎng)只有一條起飛跑道，所有的航班需按某個(gè)順序依次起飛（稱這個(gè)順序?yàn)槠痫w序列）。定義一個(gè)航班的起飛序號(hào)為該航班在起飛序列中的位置，即是第幾個(gè)起飛的航班。起飛序列還存在兩類限制條件：第一類（最晚起飛時(shí)間限制）：為 i 的航班起飛序號(hào)不得超過(guò) ki;第二類（相對(duì)起飛順序限制）：存在一些相對(duì)起飛順序限制(a

2、, b)，表示航班 a 的起飛時(shí)間必須早于航班 b，即航班 a 的起飛序號(hào)必須小于航班 b的起飛序號(hào)。小 X 思考的第一個(gè)問(wèn)題是，若給定以上兩類限制條件，是否可以計(jì)算出一個(gè)可行的起飛序列。第二個(gè)問(wèn)題則是，在考慮兩類限制條件的情況下，如何求出每個(gè)航班在所有可行的起飛序列中的最小起飛序號(hào)?！据斎敫袷健枯斎胛募?plane.in 第一行包含兩個(gè)正整數(shù) n 和 m，n 表示航班數(shù)目，m 表示第二類限制條件（相對(duì)起飛順序限制）的數(shù)目。第二行包含 n 個(gè)正整數(shù) k1, k2, , kn。接下來(lái) m 行，每行兩個(gè)正整數(shù) a 和 b，表示一對(duì)相對(duì)起飛順序限制(a, b)，其中 1a,bn, 表示航班 a 必須

3、先于航班 b 起飛。【輸出格式】輸出文件 plane.out 由兩行組成。第一行包含 n 個(gè)整數(shù)，表示一個(gè)可行的起飛序列，相鄰兩個(gè)整數(shù)用空格分隔。輸入數(shù)據(jù)保證至少存在一個(gè)可行的起飛序列。如果存在多個(gè)可行的方案，輸出任意一個(gè)即可。第二行包含 n 個(gè)整數(shù) t1, t2, , tn，其中 ti 表示航班 i 可能的最小起飛序號(hào)，相鄰兩個(gè)整數(shù)用空格分隔?！救绾卧u(píng)分】如果你的輸出文件格式與題目要求不符，則得 0 分。即你的輸出文件必須滿足：第一行恰好包含 n 個(gè)整數(shù)，且第二行也恰好包含 n 個(gè)整數(shù)。當(dāng)你的輸出文件格式與題目要求相符時(shí)：1.2.3.如果僅第一行正確，獲得對(duì)應(yīng)測(cè)試點(diǎn) 40%的分?jǐn)?shù)；如果僅第二

4、行正確，獲得對(duì)應(yīng)測(cè)試點(diǎn) 60%的分?jǐn)?shù)；如果兩行均正確，獲得對(duì)應(yīng)測(cè)試點(diǎn) 100%的分?jǐn)?shù)。【樣例輸入】25【樣例輸出】3 4 1 2 1【樣例輸入 2】5 03 3 3 5 5【樣例輸出 2】3 2 1 5 41 1 1 4 4【樣例說(shuō)明】在樣例 1 中：起飛序列 33 4 5 1 22 45142 滿足了所有的限制條件，所有滿足條件的起飛序列有：3 5 1 2 45 3 1 4 23 55 3 4 1 2由于存在(5, 1)和(3, 1)兩個(gè)限制，航班 1 只能安排在航班 5 和 3 之后，故最早起飛時(shí)間為 3，其他航班類似。在樣例 2 中：雖然航班 4、5 沒(méi)有相對(duì)起飛順序限制，但是由于航班

5、1、2、3 都必須安排3 個(gè)起飛，所以 4、5 最早只能安排在第 4 個(gè)起飛。【數(shù)據(jù)范圍】對(duì)于 30%數(shù)據(jù)：n10；對(duì)于 60%數(shù)據(jù)：n500；對(duì)于 100%數(shù)據(jù)：n2,000，m10,000?！具\(yùn)行時(shí)限】1 秒。【運(yùn)行空限】512M。旅行路線【問(wèn)題描述】2010 年，世博會(huì) 暑假期間小 Z 也來(lái)到了舉辦，吸引了數(shù)以千萬(wàn)計(jì)的中外游客前來(lái)參觀。世， 她對(duì)世的擁擠早有所聞，對(duì)有的展館甚至要排上好幾個(gè)小時(shí)的隊(duì)才能進(jìn)入也做好了充分準(zhǔn)備，但為了使得自己的世博之旅更加順利舒暢，小 Z 決定在游玩之前先 制定一份詳細(xì)的旅行路線。小 Z 搜集到了世的地圖，她發(fā)現(xiàn)從整體上看世是一塊非常狹長(zhǎng)的區(qū)域，而每一個(gè)展館占

6、用了其中一個(gè)幾乎相同大小的方塊。因此可以將整個(gè)園區(qū)看成一個(gè) n m 的矩陣(n3)，其中每一個(gè)格子為一個(gè)展館。由于不同展館受到的關(guān)注度會(huì)有一些差別，因此排隊(duì)時(shí)間的長(zhǎng)短也不盡相同。小 Z 根據(jù)統(tǒng)計(jì)信息給每一個(gè)展館(x, y)標(biāo)記了 Tx,y = 0 或 1，如果 Tx,y = 1，表示這個(gè)展館非常熱門，需要排很長(zhǎng)時(shí)間的隊(duì)；如果 Tx,y = 0，表示這個(gè)展館相對(duì)比較普通，幾乎不需要排隊(duì)參觀。小 Z 希望能夠制定一份合理的路線，使得能交替參觀熱門館和普通館，既不會(huì)因?yàn)榭偸菂⒂^熱門館 而長(zhǎng)時(shí)間在排隊(duì)，也不會(huì)因?yàn)榭偸菂⒂^普通館而使得游覽過(guò)于平淡。同時(shí)，小 Z 辦事很講究效率，她希望在游遍所有展館的同時(shí)

7、，又不會(huì)走冤枉路浪費(fèi)體力。因此她希望旅行路線滿足以下幾個(gè)限制：在參觀完位于(x, y)的展館后，下一個(gè)參觀的是一個(gè)相鄰的且未被參觀過(guò)的展館(x, y)，即 |x-x|+|y-y|=1；路線的起點(diǎn)位于整個(gè)矩陣的邊界上，即 x = 1 或 x = n 或 y = 1 或 y = m；她制定了一個(gè)長(zhǎng)度為 n*m 的 01 序列 L，她希望第 i 個(gè)參觀的展館(x,y)滿足Tx,y=Li。小 Z 想知道有多少條不同的旅行路線能夠滿足要求。由于最終的結(jié)果可能很大，小 Z 只想知道可行的旅行路線總數(shù) mod 11192869 的值?！据斎胛募枯斎胛募?trip.in 第一行包含兩個(gè)正整數(shù) n, m。第

8、2 行至第 n+ 1 行，每行有 m 個(gè) 01 整數(shù)，其中第 i+ 1 行第 j 個(gè)數(shù)表示 Ti,j。第 n+ 2 行有 n*m 個(gè) 01 整數(shù)，其中第 i 個(gè)數(shù)表示 Li 的值?！据敵鑫募枯敵鑫募?trip.out 僅包含一個(gè)整數(shù)，表示可行的旅行路線總數(shù) mod 11192869的值?！据斎霕永? 210011010【輸出樣例】4【樣例說(shuō)明】這四條可行的旅行路線分別為：(1,1)(1,2)(2,2)(2,1)(1,1)(2,1)(2,2)(1,2)(2,2)(1,2)(1,1)(2,1)(2,2)(2,1)(1,1)(1,2)【數(shù)據(jù)規(guī)模和約定】對(duì)于 10%的數(shù)據(jù)：n=1；對(duì)于 30%的數(shù)

9、據(jù)：n=2；對(duì)于 60%的數(shù)據(jù)：n= 3，其中 20%的數(shù)據(jù) Ti,j 全為 0；對(duì)于 100%的數(shù)據(jù)：m50，Li,【運(yùn)行時(shí)限】10 秒。【運(yùn)行空限】512M。Ti,j= 0 或 1。成長(zhǎng)【問(wèn)題描述】Nemo 是一條無(wú)憂無(wú)慮的小魚，它的初始體重為 w0。可愛的 Nemo 希望自己能夠盡快地成長(zhǎng)，因此需要吃盡量多的食物。Nemo 最喜愛的食物是海里的小蝦。已知 Nemo 對(duì)食物的情況了解如下：大海里共有 n 只小蝦，從 1 到 n，其中為i 的小蝦的重量為 wi。將大?？醋饕粋€(gè) X-Y 坐標(biāo)系，在 0 時(shí)刻為 i 的小蝦所在的位置為(xi,yi)。小蝦在大海中作勻速直線運(yùn)動(dòng)，其中它的位置為為

10、i 的小蝦的速度向量為(pi, qi)，即在時(shí)刻 t，(xi+pi*t,yi+qi*t)Nemo 在 0 時(shí)刻的位置為(x0, y0)，它可以在海中隨意移動(dòng)，但速度不超過(guò) V。Nemo 希望通過(guò)自己的努力，在 T 個(gè)時(shí)間內(nèi)(含 T 時(shí)刻)吃到的小蝦重量總和盡量大。當(dāng) Nemo 與某只小蝦同時(shí)移動(dòng)到同一個(gè)位置上，且小蝦的重量小于 Nemo 當(dāng)時(shí)的重量，則 Nemo 可以將該小蝦。當(dāng) Nemo重量為wi 的小蝦之后，它的體重將增加 wi。注意，小蝦不會(huì)吃 Nemo，且小蝦之間也不會(huì)自相殘殺。Nemo 希望你來(lái)幫助它制定一個(gè)成長(zhǎng)計(jì)劃，使得它【輸入格式】的小蝦重量總和盡量大。該題為提交型試題，所有輸入

11、數(shù)據(jù) nemo1.innemo10.in 已在試題目錄下。對(duì)于每個(gè)數(shù)據(jù)，輸入文件中第一行為五個(gè)實(shí)數(shù) w0, V, T, x0, y0。分別表示 Nemo 的初始體重、最大移動(dòng)速度、時(shí)間限制以及 Nemo 在 0 時(shí)刻的位置。第二行為一個(gè)整數(shù) n，表示大海中小蝦的只數(shù)。接下來(lái) n 行，每行 5 個(gè)實(shí)數(shù)，包括 wi, xi, yi, pi, qi，分別表示 0 時(shí)刻的位置和速度向量。【輸出格式】為 i 的小蝦的重量、在針對(duì)給定的 10 個(gè)輸入文件 nemo1.innemo10.in ， 你需要分別提交你的輸出文件nemo1.outnemo10.out。輸出文件第一行包含一個(gè)整數(shù) k。表示在你的成長(zhǎng)計(jì)劃中，Nemo 將吃到 k 只小蝦。第二行包含一個(gè)實(shí)數(shù) w，表示在你的成長(zhǎng)計(jì)劃中，Nemo 吃到的小蝦的重量總和。接下來(lái) k 行，每行 4 個(gè)數(shù) t, x, y, s。表示在時(shí)刻 t，Nemo 在位置(x, y)處的小蝦。其中 t, x, y 為實(shí)數(shù)，s 為整數(shù)。了為 s為保證驗(yàn)證程序的精度，所有實(shí)數(shù)建議至少輸出到小數(shù)點(diǎn)后 6 位。在驗(yàn)證程序中，兩個(gè)實(shí)數(shù)絕對(duì)誤差不超過(guò) 10-4 時(shí)，即視為相等?！緲永斎搿?【樣例輸出】55 2 2 1【樣例說(shuō)明】在這個(gè)樣例