NOIP2000-2007 全部題解

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

BYVoid原創程序及題解打包下載(37 KB)

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

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

目錄

  • 2 NOIP2001

  • 3 NOIP2002

  • 4 NOIP2003

  • 5 NOIP2004

  • 6 NOIP2005

  • 7 NOIP2006

  • 8 NOIP2007

  • 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)。這具體取決與圖的疏密程度,如果使用鄰接表存儲,在圖不是十分密集的時候效果很好。該題測試數據中沒有很強大的,所以這樣就可以過了。

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

    1. 所謂“兩部分不能存在包含關係”,是指兩部分接龍後不能長度不增加。例如ababab和ababab,可以接成ababababab,但不能爲ababab。
    2. 接龍時,如果兩個單詞接龍後的單詞有多種情況,要儘可能保證接龍後的單詞最長。例如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的變化爲階段遞推即可。

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

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

    1. “神經元 i 最初狀態”即爲C[i]的初始值。
    2. 公式只對非輸入層點有效。換句話說就是輸入層的閾值根本沒用,不用讓C[i]減去U[i]。
    3. “僅輸出最後狀態非零的輸出層神經元狀態”,實際上是要求輸出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. 購買主件
    3. 購買主件 + 附件 1
    4. 購買主件 + 附件 2
    5. 購買主件 + 附件 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算法,雖然與這道題無關。

    提示幾點

    1. 每個工件的每個工序對應着不同的機器。
    2. 一個工件必須按照加工順序加工。
    3. 把每個機器看成一個時間軸,每個時間對應着加工一個工件,或者爲空閒狀態。
    4. 題中的算法是給定的貪心策略,不需要構造,只要模擬。
    由於數據很小,把每個機器的時間軸用布爾數組表示,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. 最高位大於等於1
    對於這種情況,總數爲位數爲N,最高位爲i(1<=i<=H)的滿足條件的2^k進制數的個數的和。即Sum{ F[N,i] }(1<=i<=H)

    1. 最高位爲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)

    最終結果

    • 每行結果的總和

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

    樹網的核

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

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

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

    1. 在圖中任意找一個頂點A。
    2. 以A爲源點,搜索距離A最遠的點B。O(N)
    3. 以B爲源點,搜索距離B最遠的點C。O(N)
    則BC就是一條直徑。找直徑的時間複雜度爲O(N)。

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

    1. 在直徑上枚舉頂點A。O(N)
    2. 找到直徑上距離A不超過S的最遠頂點B。O(1)
    3. 求AB的偏心距。O(N)
    最後保留最小偏心距即可。時間複雜度爲O(N^2)。

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

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

    相關日誌