課件案例全國賽day

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

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

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

4、行正確，獲得對應測試點 60%的分數(shù)；如果兩行均正確，獲得對應測試點 100%的分數(shù)。【樣例輸入】25【樣例輸出】3 4 1 2 1【樣例輸入 2】5 03 3 3 5 5【樣例輸出 2】3 2 1 5 41 1 1 4 4【樣例說明】在樣例 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)兩個限制，航班 1 只能安排在航班 5 和 3 之后，故最早起飛時間為 3，其他航班類似。在樣例 2 中：雖然航班 4、5 沒有相對起飛順序限制，但是由于航班

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

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

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

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

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

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

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