【強連通分量】四面楚歌 virus 解題報告

【題目描述】

公元2008年10月31日星期五，篤志者所在的整個機房由於猖獗的病毒一片恐慌。經查證，病毒是由A1機器散播開來的。。這要追溯到29日，篤志者由於病毒被迫從A1機器撤離。

一想到病毒是從自己的機器傳開的，篤志者就心神不寧。他決定搞清楚病毒是怎麼散播開來的。事實上，機房內的機器並不是全部都能夠互相感染的。篤志者（ceeji）好不容易經過測試得到了機房中各機器間是否連通的圖表，就在他馬上就要得出結果的時候，大腦突然亂了！問題的嚴重性在於：如果他不在1s內搞清楚這個問題，機房就會整體癱瘓。現在篤志者求助於你，他需要知道病毒從未感染機房開始，最少入侵幾臺機器之後，機房就會整體感染。

【輸入格式】

文件的第一行為一個整數n，第二行至第n+1行為n*n的矩陣（若第i行第j列為1，則機器i能對機器j進行ARP攻擊（即感染機器j），若第i行第j列為0，則機器i不能感染機器j）。

文件名為“2.in”。

【輸出格式】

輸出文件只有一行，為篤志者想知道的最少感染機器數。

文件名為“2.out”。

NOIP1995 普及組 編碼問題 code

【問題描述】

設有一個數組 A ： ARRAY[0..N-1] OF INTEGER ；數組中存儲的元素為 0-N-1 之間的整數，且 A[I] ≠ A[J] ( 當 I ≠ J) 時。

例如： N=6 時，有：（ 4 ， 3 ， 0 ， 5 ， 1 ， 2 ）

此時，數組 A 的編碼定義如下：

A[0] 的編碼為 0 ：

A[I] 的編碼為：在 A[0] ， A[1] ，…… A[I-1] 中比 A[I] 的值小的元素的個數（ I=1 ， 2 ，…… N-1 ）

所以上面數組 A 的編碼為 :B=(0,0,0,3,1,2)

程序要求解決以下問題

① 給出數組 A 後，求出其編碼；

② 給出數組 A 的編碼後，求出 A 的原資料。

[動態規劃]Ural 1031 rail 火車票 解題報告

【題目描述】
現在有一條“葉卡特琳堡－斯維爾德洛夫斯克”鐵路線。它有若干個火車站。這個鐵路線可以用一條線段來表示，而火車站就是線段上的點。鐵路起始於葉卡特琳堡(Eakterinburg)，終止於斯維爾德洛夫斯克(Sverlovsk)，且各站從葉卡特琳堡(它的編號是1)至斯維爾德洛夫斯克(終點)編號。

兩個站之間的票價僅跟兩站間的距離有關係。票價規定如下表。

兩站間距離 - X	票價
0<X<=L1	C1
L1<X<=L2	C2
L2<X<=L3	C3

當且僅當兩站間距離不大於L3時才能購買這兩站之間的直達車票。所以有時須要購買若干張票來完成整個旅行。


例如，在上圖，整條鐵路有七個站。從第2站不能直達第6站(因為距離大於L3)，但有另外幾種方法購票。其中一種是買兩張票：一張是從第2站至第3 站(票價為C2)，另一張是從第3站至第6站(票價為C3)，注意，雖然從第2站至第6站的距離為2×L2，但不可以買兩張價值C2的票，因為一張票只可以用一次且起點和終點必須在車站上。

你的任務時計算給出的兩站之間的最小花費。

[動態規劃]OI練習題 週年紀念聚會 aniv 解題報告

週年紀念聚會

Background

校長正在籌備學校的80週年紀念聚會。由於學校的職員有不同的職務級別，可以構成一棵以校長為根的人事關係樹。每個職員都有一個唯一的整數編號（範圍在1到N之間），並且對應一個參加聚會所獲得的歡樂度。為了使每個參加聚會者都感到歡樂，校長想設法使每個職員和他（她）的直接上司不會同時參加聚會。

Problem

你的任務是設計一份參加聚會者的名單，使總的歡樂度最高。

Input

輸入的第一行是一個整數N，1<= N <= 6000

以下的N行是對應的N個職員的歡樂度（歡樂度是一個從-128到127之間的整數）

接著是學校的人事關係樹，樹的每一行格式如下：

<L> <K>

表示第K個職員是第L個職員的直接上司。

輸入以0 0表示結束

輸出：參加聚會者獲得的最大總歡樂度

[動態規劃]OI練習題 最後的利益 9cwy 解題報告

【問題描述】
最近9C馬上就要和WY交收WOW的運營權了，9C為了最後的利益決定讓GM控制玩家上線時間。因為9C的小霸王伺服器總是容易爆滿，所以某伺服器中只剩一個玩家的位子，GM為了讓玩家在線時間總和最長。他將選擇一些上線時間不重複的玩家讓他們上線。我們假設某玩家下線以後，另一個玩家可以立即登入。但是GM又笨又懶，他希望你能幫他幫他寫一個程序來完成這個任務。

【輸入文件】

輸入文件第一行是一個正整數n，n<=10000，為玩家數量

一下n行每行含有兩個數t1、t2表示某玩家上線時段

【輸出文件】

輸出最長遊戲總時間

[動態規劃]POI 1998 ple 潛水員問題 解題報告

【問題描述】
     一個潛水員在潛水時使用一種特殊的裝置：一個有兩個容器的氣筒。一個容器中裝的是氧氣，另一個容器中裝氮氣。潛水員需要攜帶的氧氣和氮氣量依賴於潛水的時間和深度。潛水員有一系列的氣筒，用來在不同的情況下攜帶。每個氣筒可以用這樣幾個量來描述：氣筒的質量，氣筒中所能容納的氧氣量，以及可以容納的氮氣量。為了能完成最近的一個任務，潛水員需要一定量的氧氣和氮氣。潛水員有一系列準備好的氣筒。他希望能攜帶總質量儘可能小的氣筒下水。現在請你幫他計算一下至少要攜帶多少質量的氣筒下水才能完成這個任務。

【示例說明】
潛水員有以下 5 個氣筒。每個氣筒用三個整數來描述：氣筒所能容納的氧氣的量，氮氣的量和氣筒的質量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果這次任務中潛水員需要攜帶 5 升 氧氣， 60 升 氮氣。那麼他至少要攜帶總質量為 249 的氣筒下水（樣例中的第一個和第二個氣筒或者第四個和第五個氣筒）。