本文正體字版由OpenCC轉換

完成了NOIP2000-2008的全部題解，發上來供大家參考吧，如有謬誤還請多多指教。

==2009.3.26== 格式重新整理，另外附上 NOIP2008 雙棧排序 twostack 題解

==2009.6.30== 添加 NOIP2008 傳紙條費用流建模

NOIP2000

進制轉換

和正基底進制數轉化方法類似，使用短除法進制轉換。

例如題中寫的-15的-2進制

-2|-15
+—–…1
-2|8
+—–…0
-2|-4
+—–…0
-2|2
+—–…0
-2|-1
+—–…1
-2|1
+—–…1
0

倒序把每次餘數寫下，就是110001。所以結果是-15=110001(base-2)。

但要注意的是在編程中，使用整除的問題。無論是C++還是Pascal，-15 整除 -2結果爲7，-15 與 -2 求模結果爲-1。但我們顯然不能用負數作爲餘數，所以要滿足，商 * 除數 <= 被除數。

即結論如下：

當 a / b * b <=a 時，a 整除 b 結果爲 a / b。
當 a / b * b >a 時，a 整除 b 結果爲 a / b + 1。

乘積最大

題中所述的是長度爲N的數字串中添加K個乘號，即把前N個數字分爲W份乘積的最大值，W=K+1。

動態規劃

狀態

sum[i,j] 表示從第i位到第j位組成的數字
F[i,j] 表示把前i個數字分爲j份乘積的最大值

狀態轉移方程

F[i,j]=max{F[k,j-1]*sum[k+1,i]} (1<=k<=i-1)

邊界條件

F[x,1]=sum[1,x]

目標結果

F[N,W]

時間複雜度

O(K*N^2)

單詞接龍

這是一道搜索題，可以轉化爲圖論，求有向圖無環最長路徑。由於每個單詞最多可以用兩次，爲方便起見，先把每個單詞複製一遍，看做兩個相同的單詞。

把能接龍的單詞a與b之間建立一條邊(a,b)，邊權爲單詞b的長度-a,b重合部分的長度。把起始字母看做一個節點，建立起始字母能接到的單詞a的邊，邊權爲a的長度。最後從起始點開始搜索最長路徑即可。

由於有向圖無環最長路徑是NP的，最壞情況下時間複雜度爲O(N^N)。這具體取決與圖的疏密程度，如果使用鄰接表存儲，在圖不是十分密集的時候效果很好。該題測試數據中沒有很強大的，所以這樣就可以過了。

有兩點要注意，題上說的很不明確，容易造成誤解。這兩點是我在看過數據後發現的。

所謂“兩部分不能存在包含關係”，是指兩部分接龍後不能長度不增加。例如ababab和ababab，可以接成ababababab，但不能爲ababab。
接龍時，如果兩個單詞接龍後的單詞有多種情況，要儘可能保證接龍後的單詞最長。例如cabab和ababc，一定要接成cabababc，爲而不是cababc。

方格取數

數據不大，搜索兩條路徑即可。

把每個有數字的方格看做一個頂點，該頂點與其右下的所有頂點連接一條有向邊。然後從左上角的點搜索到右下角頂點的點權最長路徑。搜索到一條路徑以後要再搜索一遍其餘節點，找出另一條最長路徑。每次保留兩個階段的和的最大值。

最後的結果就是兩次路徑和最長的路徑的長度。

最壞情況下時間複雜度爲O(2^(N^2))，不過數據中沒有能構造到這樣時間複雜度的。

NOIP2001

一元三次方程求解

窮舉就行了，精度只有0.01，範圍-100至100。

要注意精度問題，不要直接判斷式子等於0，而要判斷式子的絕對值在(-0.01,0.01)之間，避免漏解。

數的劃分

動態規劃

狀態

F[i,j] 表示數i分爲j部分的方案個數

狀態轉移方程

F[i,j]=F[i-1,j-1]+F[i-j,j]

邊界條件

F[x,1]=1
F[i,j]=0 (j>i)

目標結果

F[N,K]

狀態轉移方程可以理解爲：

每種拆分方案中，最小的數爲w，按照w的不同，我們可以把拆分方案分成2類：

w=1，我們把1除去，則剩餘部分正好是i-1拆分成j-1部分，一共有F[i-1,j-1])個；
w>1，所有的數都>1，我們把所有的數-1，則正好是i-j拆分成j部分，一共有F[i-j,j]個。

根據加法原理，得出以上方程。

統計單詞個數

動態規劃

以0爲第一個字符存儲字符串。

狀態

F[i,j]爲前i個字符，分爲j份的最大單詞個數
cnt[i,j]爲從第i到第j的字母中單詞最大個數

狀態轉移方程

F[i,j]=max{ F[k,j-1] + cnt[k+1,i] } (0<=k<=i-1)

邊界條件

F[x,1]=cnt[0,x]

目標結果

F[L,K] L爲主串長度-1，即最後一位

時間複雜度

O(K*P^2)

Car的旅行路線

明顯的最短路徑問題，頂點數最多隻有400個。Floyed，Dijkstra，SPFA，用什麼最短路算法都行。但這道題麻煩的地方不在最短路，而在構圖上。

首先是已知矩形三個頂點求第四個，利用對稱性可以求出。首先要找出已知三個頂點組成的三角形的直角頂點，可以用向量的數量積爲0，可以以用勾股定理的逆定理。如果(x3,y3)爲已知三個頂點組成的三角形的直角頂點，根據中心對稱性，要求的點(x4,y4)可以表示爲(x1+x2- x3,y1+y2-y3)，依此類推。

找出每個矩形的所有定點後，下面就是連接邊，只要細心就不會漏。最後再算一下最短路就行了。

由於這是一個完全圖，所以時間複雜度爲

Floyed O(N^3)
Dijkstra O(N^2)
SPFA O(N^2)

其中算法常數最小的是SPFA，我用SPFA做了這道題，儘管Floyed就可以了。

NOIP2002

均分紙牌

貪心法，一次掃描即可。

首先算出紙牌的平均數，我們希望通過儘可能少的移動，來使所有紙牌達到平均值。

從第一張紙牌開始掃描，把它[多出平均值的數量]向右移，[多出平均值的數量]有可能是負數。然後掃描第二張，一直到N 1張爲止。掃描的過程中如果發現這張紙牌數值正好是平均值，那麼直接跳過即可。

例如樣例，平均值爲10。

9 8 17 6

第1次移動，第1張牌移 1

10 7 17 6

第2次移動，第2張牌移 3

10 10 14 6

第3次移動，第3張牌移4

10 10 10 10

結果爲移動了3次。

字串變換

廣度優先搜索即可，沒有必要雙向搜索。

關鍵是狀態的判重，我用的是ELFash，配合Treap平衡樹，每次判斷時間都是O(logK^N)，根據數據規模最大也就是25次。

平衡樹中存儲字符串的Hash碼，由ELFHash算法生成。如果沒有重複的就加入搜索隊列，否則直接淘汰。

無解有兩種情況，一個是根本無法變換出目標串，另一個是在10步變換以內沒有求出目標串。

自由落體

這是一道十分基礎的題，不需要什麼算法，只是需要細心。

顯然小車接到的球一定是相鄰幾個，只需考慮兩端即可。注意小車接球時還在移動，可以接了一個球以後移動一下再接到一個。

誤差小於等於0.00001就行了。

矩形覆蓋

離散化加搜索，在NOIP的確是一道難題。

首先把所有點分別以橫座標和縱座標排序，生成兩組序列。

首先從[0,500]整個區域中，分別按橫向和縱向掃描若干個點，以一個矩形覆蓋。然後在剩餘的區域內再次分別按橫向和縱向掃描若干個點，以一個矩形覆蓋……直到把K個矩形覆蓋完爲止。

找到面積最小的方案。

NOIP2003

神經網絡

這道題描述上很冗長，容易使人混淆，多次讀題才能發現其意義。

根據題意，我們要在這個網絡上遞推。題目上給了一個遞歸公式，但我們可以把它改爲正向的遞推。

即 C[j]=Sum{W[i,j]*C[i]}-U[j] 以i的變化爲階段遞推即可。

爲了儘可能高效，我使用了鄰接表+鏈隊列。

題上有些地方描述的不清晰，需要來澄清。

“神經元 i 最初狀態”即爲C[i]的初始值。
公式只對非輸入層點有效。換句話說就是輸入層的閾值根本沒用，不用讓C[i]減去U[i]。
“僅輸出最後狀態非零的輸出層神經元狀態”，實際上是要求輸出C[i]>0的i和C[i]。

偵探推理

看似簡單的一道題，但很一次難拿到滿分。

顯然需要枚舉所有解，輸出唯一解，無解則輸出Impossible，多解則輸出Cannot Determine。

枚舉誰說的是真話，是個愚蠢的策略。這樣最多會有C(M,N)種可能，運行要超時不說，程序寫起來還十分麻煩。由於只存在兩個事實，即誰是兇手和今天是星期幾。我們枚舉這兩個事實即可，僅有M*7種可能。

輸入格式是個陷阱，很容易出錯。爲避免錯誤發生，原則就是字符串完全匹配，區分大小寫。在讀入的過程中，我們可以直接去掉“廢話”，即與事實無關的話。

在判斷誰說的是真話，誰說的是假話的時候，會出現一個人說的話前後矛盾，可能有悖論的產生，這時要直接跳過這種情況。

有人可能會不說一句話！對於這種情況，這些人是算成說真話的人呢？還是算成說假話的人？很顯然，有多種可能。所以對於輸入中給出的“始終說謊的人數N”，只要滿足(說假話的人<=N<=說假話的人+不說話的人)，即可認定爲一個解。

加分二叉樹

動態規劃

狀態

F[i,j] 爲中序遍歷中第i到第j個節點所組成的子樹的最大加分
root[i,j] 爲中序遍歷中第i到第j個節點所組成的子樹的根

狀態轉移方程

F[a,b]=max{ F[a,k-1]*F[k+1,b]+F[k,k] }
root[a,b]=使F[a,b]最大的k的值 (a<=k<=b)

邊界條件

F[i,i]=P[i] 第i個節點的分數
F[i,j]=1 (i>j)

目標結果

最大加分爲 F[1,N]

前序遍歷要在root狀態中遞歸得出。從a=1,b=N開始遞歸，a,b子樹中根爲root[a,b]。輸出root[a,b]並遞歸進入(a,root[a,b]-1)和(root[a,b]+1,b)

傳染病控制

搜索一棵樹，從根節點開始，枚舉剪掉每一條邊，把剩餘的節點合併爲一個節點，繼續回溯搜索它。返回時要把合併了的節點再拆開來。繼續枚舉另一條邊。

這樣的話，可能會超時的。所以要加上兩個顯而易見的優化。

優化一：當搜索過程中發現當前的感染人數已經大於已知最小感染人數，繼續搜索是無意義的，要回溯。

優化二：如果遍歷到一顆樹的節點全部都是葉節點，不用枚舉剪哪個，這時新感染人數一定爲葉節點數-1。否則在枚舉剪斷的時候，無需剪葉節點。

優化三：啓發式搜索。很明顯，一棵子樹的節點數越多，這棵樹就越“危險”，所以優先枚舉剪掉這棵子樹，會減少很多搜索量。

NOIP2004

津津的儲蓄計劃

再簡單不過的題了。邊讀邊算就行了，相信學過編程的都能做這道題。

有個要注意的地方，就是年末取得存款的時候，最好不要乘以1.2，而是先除以5再乘以6。這樣可以避免由於兩次隱式轉換產生的誤差。這個誤差對於C++尤爲顯著。

合併果子

由題意可知，顯然是每次合併兩堆數目最小的果子，合併N-1次以後消耗體力最少。

因爲越早合併的果子堆，合併的次數就越多。我們把數目大的果子堆留到儘量靠後合併，才能保證儘量合併少，這樣消耗體力才能最少。

我們每次合併時，都要從所有的果子中找到數目最少的兩堆。由於N<=10000，顯然每次O(N^2)的排序是不行的。要用到最小堆或者平衡樹了。

我用的是Treap樹，時間複雜度爲O(N*logN)。

注意這道題不是石子歸併！

合唱隊形

動態規劃。這道題實際上是求最長谷狀序列，可以轉化爲最長上升、下降序列問題。方法爲枚舉中間長的最高的人，在其左邊求最長上升序列，在其右邊求最長下降序列。注意這兩個序列要以中間這個人爲公共點。

所以設置的兩個狀態分別爲以第i個數爲結尾的最長上升序列和以第i個數爲開頭的最長下降序列，這樣可以保證兩個序列可以連接。

狀態

F[i] 以第i個數爲結尾的最長上升序列
G[i] 以第i個數爲開頭的最長下降序列
H[i] 第i個數的值

狀態轉移方程

F[i]=max{ F[j] + 1 } (1<=j<=i-1 and H[j]<H[i])
G[i]=max{ G[j] + 1 } (i+1<=j<=N and H[j]<H[i])

邊界條件

F[i]=1 (H[j]均大於等於H[i] 1<=j<=i-1 )
G[i]=1 (H[j]均大於等於H[i] i+1<=j<=N )

目標結果

N-最長谷狀序列長度。
max { N-(F[k]+G[k]+1) } (1<=k<=N)

蟲食算

這是NOIP2004的唯一一道難題，而且是很難的題。單純暴力搜索，超時是無疑的，加上許多強剪枝也很難通過。於是我用瞭解方程組的方法。

從算式中可以發現，有N位，每位都是兩個未知數相加得到第三個未知數。正好是N元一次線性方程組。由於存在進位問題，枚舉除最後一位以外的每位的是否進位，可以列出2^(N-1)個不同的方程組，解每個方程組即可得出解。解方程組使用高斯消元算法，時間複雜度爲O(N^3)。但枚舉多達2^(N-1)個，這樣還是會超時。

深入分析發現，枚舉每位是否進位，僅僅影響方程的常數項。於是可以在枚舉進位之前，設每個方程的常數項爲d1,d2,d3,…,dn。解方程組，把未知數x1,x2,x3,…,xn用d1,d2,d3,…,dn表示，高斯消元的時候要把常數項以多項式的方式計算。

這是我們在還是枚舉每位是否進位，算出每個方程的常數項，即d1,d2,d3,…,dn，代入x1,x2,x3,…,xn再判斷即可。

這種方式只用計算一次方程組，雖然時間複雜度不變，但算法常數小了許多，對付N=26沒有問題了。

NOIP2005

誰拿了最多獎學金

讀入每行數據，進行多條件判斷，算出每個人的獎學金，保留總和與最大值。

很簡單的題，只要細心就不會錯。

用C或C++語言讀入數據十分方便，一條語句即可。但是Pascal就麻煩了。

過河

動態規劃，需要狀態壓縮。

狀態

F[i] 跳到距離i處碰到的最少的石子數。

狀態轉移方程

F[i]=min{ F[i-k] } + F[i] (S<=k<=T i-k>=0)

邊界條件

F[i]=1 i處有石子

目標結果

min{ F[k] } (L+1<=k<=L+T-1)

狀態壓縮

由於L最大爲10^9，直接線性遞推會超時。發現石子數很少，這意味着路徑上有許多很長的空白段。我們可以把長度大於ST的空白段都縮小到ST，這樣最長只有10090了。

篝火晚會

首先把這個圈看做一個圖，每個同學看做一個頂點。因爲要形成環，所以每個頂點的度必須爲2。如果存在度數不爲2的頂點，那麼整個圖無法構成一個環，即“無論怎麼調整都不能符合每個同學的願望”輸出-1。如果是一個環，那麼就遍歷圖，生成以第1個頂點爲開頭的序列。現在就要求出最小移動的代價。

在理解題意所述的調整方式中，要注意實際上就是把M個在錯誤位置上的人移動到正確的位置上，代價爲M。一次下令移動即可。

假如生成的目標序列爲1,5,3,2,4。我們現在就需要比較它和初始狀態1,2,3,4,5，看有幾個人離開了原來的位置。但這個序列實際代表的是一個環，而且方向正反有兩種，就需要把初始序列正反分別轉N次，和得到的序列比較，看其中最少有幾個位置上的人編號不相同，就得到了我們要求的最小代價。

上述方法有大量冗餘。但可以發現轉來轉去不管怎麼轉，任意兩個人之間的相對位置關係在這過程中都不會變。於是想到做差，如果差小於0則加上N。

1 5 3 2 4
- 1 2 3 4 5
————
0 3 0 3 4

這表示序列1,5,3,2,4不轉動時1,3兩個人在原來的位置上，轉動3個位置後5和2兩個人在原來的位置上，轉動4個位置後只有4一個人會在原來的位置上。這就是說，1,5,3,2,4與1,2,3,4,5在旋轉後最多有2個位置上的人編號相同，即最少有3個位置上的人編號不相同。同理要反轉再求一次。

記錄每個不同的差值的個數，取其最大值P，即不調換次數最大的。結果N-P就是調換次數最小的。

等價表達式

這道題很顯然不是讓寫多項式展開的程序的。只需要代入幾次，判斷與題幹中表達式等價的表達式即可。

注意，只有加法、減法、乘法、乘冪四種運算，沒有除法！這意味着計算表達式的時候不用考慮出現小數的問題，數據類型要用8字節整型(即Pascal中的int64，C++中的long long)。因爲數據中有2004^9之類的大數，幸好還不用高精度。

對於表達式計算，我們可以現將題目中的表達式轉化爲後綴表達式，代入數值，並且對後綴表達式求值。當然也可以雙堆棧計算表達式。多帶入幾次不同的數值，以避免表達式恰好相等而並不等價的情況。

NOIP2006

能量項鍊

動態規劃，屬於石子歸併、合併沙堆等一類的題目。

首先把每顆珠子用一個結構存儲，.L爲頭標記的值，.R爲尾標記的值。由於項鍊是一個環，把環拆成兩條首尾相接的鏈。

例如每顆珠子表示爲

B[1] (2,3)
B[2] (3,5)
B[3] (5,10)
B[4] (10,2)
B[5] (2,3)
B[6] (3,5)
B[7] (5,10)

狀態設定

F[i,j]表示從第i顆珠子到第j顆珠子，合併一共所得的能量的最小值。
B[i]結構爲每顆珠子的頭尾標記值。

狀態轉移方程

F[i,j]=Max{ F[i,k] + F[k+1,j] + B[i].L * B[k].R * B[j].R } (i<=k<=j-1)

邊界條件

F[i,i]=0 (1<=i<=2*N-1)

目標結果

Max{ F[k,k+N-1] } (1<=k<=N)

金明的預算方案

揹包問題的衍生問題，動態規劃。

首先把附件物品分離出來，歸爲主件所有。於是每次決策成了5種

不購買
購買主件
購買主件 + 附件 1
購買主件 + 附件 2
購買主件 + 附件 1 + 附件 2

由於題中所述每件物品都是整10元，可以加一個小小的優化，就是每個物品的價格除以10。最後結果在乘以10輸出。

狀態設定

F[i,j] 前i個主件，花費爲j元的時候，重要程度與價格乘積的總和的最大值
V[i] 第i個主件的價格
W[i] 第i個主件的重要程度

狀態轉移方程

F[i,j] =
Max
{
F[ i - 1 , j ], (不購買)
F[ i - 1 , j - V[i] ] + V[i] * W[i], (只購買主件)
F[ i - 1 , j - V[i] - V[i的附件1] ] + V[i] * W[i] + V[i的附件1] * W[i的附件1], (購買主件+附件1)
F[ i - 1 , j - V[i] - V[i的附件2] ] + V[i] * W[i] + V[i的附件2] * W[i的附件2], (購買主件+附件2)
F[ i - 1 , j - V[i] - V[i的附件1] - V[i的附件2] ] + V[i] * W[i] + V[i的附件1] * W[i的附件1] + V[i的附件2] * W[i的附件2], (購買主件+附件1+附件2)
}

邊界條件

F[0,k]=0 (0<=k<=N)

目標結果

F[M,N]

作業調度方案

做這道題關鍵在於理解題意。這道題讓我想起了流水作業調度的Johnson算法，雖然與這道題無關。

提示幾點

每個工件的每個工序對應着不同的機器。
一個工件必須按照加工順序加工。
把每個機器看成一個時間軸，每個時間對應着加工一個工件，或者爲空閒狀態。
題中的算法是給定的貪心策略，不需要構造，只要模擬。

由於數據很小，把每個機器的時間軸用布爾數組表示，true爲該時間有工件在加工，false爲空閒。

按照給定的順序，一件一件得往時間軸上插入，每個工件插入的位置必須在前面的工序都完成以後的時間斷插入。每次插入掃描一遍時間軸數組，找到最前面一個。

其實題中所給的圖已經一目瞭然了。理解題意以後，會發現這是NOIP2006最簡單的題。

2^k進制數

較難的遞推問題，需要不錯的數學知識基礎才能順利的解決問題。

2^k進制實質上就是2進制數，分爲長度爲k的段。

每位的最大值 M = 2^k-1
最大的位數 N = w/k +1
最高位的最大值 H = (2^(W Mod K))-1

題中的“另一角度解釋”其實已經給了我們解題的思路。設F[i,j]爲位數爲i，最高位爲j的滿足條件的2^k進制數的個數。

如題中解釋

2 位數：高位爲 1 F[2,1]=6 (即 12,13,14,15,16,17)。高位爲2，F[2,2]=5 ， … ，F[2,6]=1(即 67)。
3 位數：高位是 1，F[3,1]，第 2 位爲2，有F[2,2]的5 個(即123,124,125,126,127)，第 2 位爲 3 ,F[2,3]4 個， … ，第 2 位爲 6,F[2,6] 個(即 167)。F[3,1]=5+4+ … +1=15個。

我們可以發現，F[i,j]總是由F[i-1,k]推出，確切來說遞推方程是Sum{ F[i-1,k] } (j+1<=k<=M)。

最終結果要分爲兩種情況的總和。

最高位大於等於1

對於這種情況，總數爲位數爲N，最高位爲i(1<=i<=H)的滿足條件的2^k進制數的個數的和。即Sum{ F[N,i] }(1<=i<=H)

最高位爲0

這種情況並不是簡單的F[N,0]，因爲r至少是個2位的2^k進制數，所以要求每位開頭不爲0的個數和。即Sum{ F[i,k] } (2<=i<=N-1,1<=k<=W)。根據遞推方程又可知Sum{ F[i,k] } (1<=k<=W)等於Sum{ F[i+1,N] }，所以這種情況的總個數爲Sum{ F[k,0] } (3<=j<=N)。

由於狀態很多，使用滾動數組可以大幅度節約空間。計算時要用要用高精度。

狀態設定

每位的最大值 M = 2^k-1
最大的位數 N = w/k +1
最高位的最大值 H = (2^(W Mod K))-1
F[i,j]爲位數爲i，最高位爲j的滿足條件的2^k進制數的個數

遞推方程

F[i,j]=Sum{ F[i-1,k] } (j+1<=k<=M)

邊界條件

F[1,k]=1 (0<=k<=M)

目標結果

Ans = Sum{ F[N,i] } + Sum{ F[j,0] } (1<=i<=H 3<=j<=N)

NOIP2007

統計數字

基本上可以說是送分題了吧。解決這道題的方法太多了，基本思想就是排序。快排，堆排，只要O(nlogn)都可以，沒有可以卡快排的數據。也可以掛鏈哈希。當然平衡樹也行。我寫了Treap。

字符串的展開

這是個簡單的題，但不是完全的送分題，要膽大心細。多讀幾遍題，掌握每一個細節。

題中陷阱很多，例如字符串長度可能很長，最好一邊讀一遍輸出，對於Pascal尤其不要用string存起來。注意減號的問題，注意有可能有些減號不是起上述作用的，例如字符串開頭就是一個減號，或者好幾個減號在一起。

矩陣取數遊戲

動態規劃。由於每行是互不影響的，可以把每行孤立開看，對每行分別進行一次動態規劃計算。結果可能很大，需要高精度計算。爲避免計算高精度乘法，可以在初始化時把每個數的2^k遞推算出。

狀態設定

F[i,j] 爲當前行取前i個數和後j個數的最大得分。
V[i,j] 爲當前行第i個數乘以2^j的值。

狀態轉移方程

F[i,j]=max{ F[i-1,j] + V[i,p] , F[i,j-1] + V[M-j+1,p] } p=i+j(表示當前是第幾次取數)
V[i,j]=V[i,j-1]+V[i,j-1]

邊界條件

V[i,1]=當前行第i個數的值
F[0,0]=0

每行結果

Max{ F[i,M-i] } (0<=i<=M)

最終結果

每行結果的總和

高精度計算時要縮位優化，否則是很容易超時的。任何可以常數優化的地方都不要放過，因爲數據是比較強的。

樹網的核

圖論題，其實並不難，但可能理解起來有障礙。

首先，一個圖可能有多個直徑，但只用研究其中任意一個即可。所以要先找一條直徑。

根據直徑的定義，可以這樣找直徑。

在圖中任意找一個頂點A。
以A爲源點，搜索距離A最遠的點B。O(N)
以B爲源點，搜索距離B最遠的點C。O(N)

則BC就是一條直徑。找直徑的時間複雜度爲O(N)。

下面就是在直徑上枚舉核。不難發現，核的長度越大，期望的最小偏心距就越小。方法如下

在直徑上枚舉頂點A。O(N)
找到直徑上距離A不超過S的最遠頂點B。O(1)
求AB的偏心距。O(N)

最後保留最小偏心距即可。時間複雜度爲O(N^2)。

按照定義找核的偏心距，即枚舉核上每個頂點A距離最遠點B，且B不在覈上的距離|AB|。搜索即可。要把核上的頂點從圖中暫時刪掉，避免找到的B在覈上。時間複雜度爲O(N)。

最終時間複雜度爲O(N^2)。

上次修改時間 2017-02-03

目錄

NOIP2000

進制轉換

乘積最大

單詞接龍

方格取數

NOIP2001

一元三次方程求解

數的劃分

統計單詞個數

Car的旅行路線

NOIP2002

均分紙牌

字串變換

自由落體

矩形覆蓋

NOIP2003

神經網絡

偵探推理

加分二叉樹

傳染病控制

NOIP2004

津津的儲蓄計劃

合併果子

合唱隊形

蟲食算

NOIP2005

誰拿了最多獎學金

過河

篝火晚會

等價表達式

NOIP2006

能量項鍊

金明的預算方案

作業調度方案

2^k進制數

NOIP2007

統計數字

字符串的展開

矩陣取數遊戲

樹網的核

相關日誌