集訓(xùn)隊作業(yè)泛做表格藩

IOI2011中國國家集訓(xùn)隊第二次作業(yè)第一部分:TopCoder題目泛做湖南雅禮中學(xué)何樸藩教練：胡偉棟唐文斌[前言]TopCoderAlgorithm與OI和ACM的競賽方式區(qū)別很大。在這個平臺上只允許程序員使用面向?qū)ο蟮恼Z言JavaC++C#VB.net，而且必須按照面向?qū)ο蟮姆绞浇鉀Q問題。與NOI傳統(tǒng)的比賽題區(qū)別明顯，語言限制少，允許使用高級語言的各種強大的功能。題目的數(shù)據(jù)范圍一般都不大，時間限制為每個測試點2s，內(nèi)存限制64MB。SRM（SingleRoundMatch）是比賽的一種。TopCoderAlgo每次比賽有3道題（Level1-3），分值不同（一般為2005001000根據(jù)難度有小調(diào)整）。題目采用一次性測試，錯了得0分，對了按解題的時間得分。可以說TopCoder在考察的方向上是側(cè)重編寫代碼的能力。我會盡量向讀者介紹最優(yōu)化以及最易實現(xiàn)的算法。表格的內(nèi)容為SRM450-499的51道DivILevel3的題目(包括453.5)。表格對每道題的題意進行了簡明描述，對解法做了討論。希望這個表格對讀者能有一點點幫助。*附帶編者的C++參考程序。如果不理解表格里的題解，可以閱讀帶注釋的參考程序。[泛做表格]表格共包括99道有效試題。難度用★表示，星數(shù)越多表示題目難度相對越大。難度完全是編者主觀意見，難免與讀者意見有些不同，請讀者多多包涵。SRM近來的題目質(zhì)量都很不錯，基本都是推薦做的。標記AC(51/51)表示作者在練習(xí)房間中提交并通過所有SystemTest。編者handle：hpfdf難度導(dǎo)讀：LevelCountRatio★35.9%★★2039.2%★★★1223.5%★★★★1223.5%★★★★★47.8%SRM內(nèi)容450AC★★★[題意]RowGame有N個數(shù)的數(shù)列，初始時人在最左邊的元素上。人需要移動不超過K次，第奇數(shù)次移動必須向右走，第偶數(shù)次必須向左走。(可以走距離0)。一次移動經(jīng)過的數(shù)字將會被全部累計入人的得分。初始時得分是0.每次移動完成后不允許出現(xiàn)總分<0的情況。求移動完K次以后人可以得到的最大分數(shù)。[范圍]1≤N≤50|數(shù)字|≤400,000,0001≤K≤400,000,000[分析]動態(tài)規(guī)劃，貪心通過研究我們發(fā)現(xiàn)，如果沒有“不允許分數(shù)<0”的限制，人第一次一定會移動到一個點，然后在這個點為結(jié)尾的最大子段和中來回運動一直跳滿K次。我們枚舉這個點就可以求最大值了。加入了限制以后，人的最優(yōu)策略會產(chǎn)生變化：為了到達目標段，我們可能要在之前的某些段中積累分數(shù)，然后移動過來在達到目標段之前，人只會積累分數(shù)，一旦積累足夠了就會移動人總是會選擇一個較大的子段進行積累。我們可以算出以每個數(shù)為結(jié)尾的最大子段和是多少。然后進行動態(tài)規(guī)劃：e[i]表示最早移動到i的時間。f[i]表示最早移動到i時可以積累的最大分數(shù)。注意不會出現(xiàn)延遲一點時間可以增大分數(shù)的情況，因為人只可能從較低分的段移動到較高分，一旦積累足夠就會跳過來。轉(zhuǎn)移時e是第一關(guān)鍵字，f是第二關(guān)鍵字。[復(fù)雜度]時間O(N2)空間O(N)451AC★★[題意]BrickPuzzle用這4種積木任意多，覆蓋一個給定的地圖。地圖中有些格子必須被覆蓋，其他的也可以覆蓋。不允許翻轉(zhuǎn)旋轉(zhuǎn)，不允許出界和重疊。問是否有解。如果沒有輸出-1。如果有解，輸出最少使用的積木塊數(shù)。[范圍]地圖大小1≤N,M≤22[分析]狀態(tài)壓縮動態(tài)規(guī)劃四種拼圖都在2行之內(nèi)，由此我們可以按行來做狀態(tài)壓縮動態(tài)規(guī)劃。經(jīng)證實此題對時間常數(shù)要求極為殘酷。需要按單格來轉(zhuǎn)移。F[i][j][mask]表示到(i,j)之前的已經(jīng)全部填好，對緊接的M+2個格子造成的影響是mask(狀態(tài)壓縮)，此時的最少塊數(shù)。優(yōu)化：滾動數(shù)組hash狀態(tài)(由于不會出現(xiàn)單獨1個格子被覆蓋，左右都沒覆蓋的情況，所以實際上合法狀態(tài)總數(shù)不超過Fibonacci數(shù)列的第M+2項，約10萬)[復(fù)雜度]時間O(φMNM)φ≈1.618空間O(φMN+2M)452AC★★★[題意]IncreasingNumber求滿足一下要求的長度為N的數(shù)字序列的總數(shù)：十進制里是M的倍數(shù)，序列不下降。[范圍]1≤N≤10181≤M≤500[分析]動態(tài)規(guī)劃，組合數(shù)學(xué)我們可以把這樣的上升數(shù)，看做不多于9個的”全1數(shù)”的和。例如，1335=1111+111+111+1+1其中全1數(shù)的位數(shù)≤N這樣一來問題變成了在前N個全1數(shù)中選出不超過9個，使得和是M的倍數(shù)。注意到M不大。我們可以用動態(tài)規(guī)劃來解決：預(yù)處理D[i]表示模M為i的全1數(shù)有多少個。F[i][j][k]表示我們已經(jīng)取了k個模M小于i的全1數(shù)，目前的和模M為j的總方案數(shù)。F[i+1][(j+x*i)%M][k+x]+=f[i][j][k]*重組和(D[i],x)重組和(a,b)=C(a+b-1,b)細節(jié)上，可以利用余數(shù)的循環(huán)節(jié)求D[i]，利用階乘式求C(i,j)[復(fù)雜度]時間O(M2K2)//K=10空間O(M2K)453AC★★[題意]TheSoccerDivOne某足球大賽有N支隊伍。現(xiàn)在每支球隊都還剩恰好4場比賽沒比完、你知道目前所有隊伍的積分。每場勝+3分，平+1分，負不加分。求第0號隊伍的最好排名。[范圍]2≤N≤500≤Score[i]≤106[分析]動態(tài)規(guī)劃首先可以確定的是，0號隊伍的4場比賽是全勝的。如果不是這樣，答案不可能變得更優(yōu)。Score[0]一旦確定，我們的任務(wù)就是要分配比賽使得分數(shù)大于Score[0]的球隊盡量少。接下來我們先不看平局。如果全體球隊的(勝場-負場)之和為0，那么就一定可以把他們間的比賽匹配好。我們只需要考慮勝場-負場的個數(shù)就可以了。加入平局以后，每個球隊的4場比賽會有15種情況。我們需要考慮對未分配對手的勝負和平局進行匹配。F[i][j][k]表示1到i的隊伍，已經(jīng)確定的(勝-負)總和=j，還有k個未匹配的平局，比a[0]分高的最少個數(shù)。這里j的范圍是-4N到4N，k的范圍是0到4[復(fù)雜度]時間O(N2)//狀態(tài)為N2,最多有15*4種轉(zhuǎn)移，為常數(shù))空間O(N)//滾動數(shù)組453.5AC★★[題意]TheAlmostLuckyNumbers十進制里只包含4和7的數(shù)字叫做幸運數(shù)字求A到B中有多少個幸運數(shù)的倍數(shù)。[范圍]1≤A≤B≤1010[分析]枚舉，搜索，容斥原理1010以內(nèi)的幸運數(shù)字共有2000個左右。一個做法是我們求出，對于任意集合的幸運數(shù)字的最小公倍數(shù)，求出在A到B中有多少個倍數(shù)。然后用容斥原理得到不重復(fù)的答案。優(yōu)化1：使用dfs，一旦中途最小公倍數(shù)大于數(shù)字范圍，剪枝。優(yōu)化2：從大到小決定幸運數(shù)字的取放，這樣可以盡快篩去過大的狀態(tài)。優(yōu)化3(可選)：刪除幸運數(shù)里面是其它幸運數(shù)倍數(shù)的項。注意中途直接乘法求最小公倍數(shù)可能會超過longlong/int64，需要移項比較。[復(fù)雜度]時間O(2logB)空間O(2logB)454AC★★[題意]MegaSum如上圖，定義S[i]為以i數(shù)字為右下角的子矩形的數(shù)字和。現(xiàn)在輸入N，輸出所有在N為右下角子矩形內(nèi)的S[i]的和。答案對1,000,000,007取余數(shù)。[范圍]1≤N≤1010[分析]數(shù)學(xué)，數(shù)值可以根據(jù)規(guī)律求出N的位置，可以證明位置坐標的范圍是O(sqrt(N))的。假設(shè)N在x,y。接下來我們討論每個數(shù)字被算的次數(shù)。一個在xi,yi數(shù)字被算了(x-xi+1)*(y-yi+1)次。我們可以把整個矩陣拆成若干個橫豎條來計算，每個條內(nèi)的數(shù)字是等差數(shù)列，被計算次數(shù)也是等差數(shù)列?？梢杂脭?shù)學(xué)方法來求兩個等差數(shù)列對應(yīng)項相乘的和。提示：Sum(i2,[1,n])=n(n+1)(2n+1)/6注意及時取模防止超過數(shù)字范圍。[復(fù)雜度]時間O(sqrt(N))空間O(1)455AC★★★[題意]ActivateTree給一棵N個節(jié)點的有根樹，再給不超過M棵有根樹，每棵樹節(jié)點數(shù)不超過5個。每次可以用一棵樹去覆蓋大樹中一棵同構(gòu)的子樹（邊的方向也必須相同），要求大樹的每個點作為根節(jié)點不能被同一棵小樹覆蓋多次。用第i棵樹去覆蓋每次需要花費整數(shù)costs[i]權(quán)值，求最小費用的方案，使每條邊被奇數(shù)次覆蓋。[范圍]1≤N≤161≤M≤50≤costs≤65536[分析]狀態(tài)壓縮動態(tài)規(guī)劃范圍不大。我們可以設(shè)F[i][j][mask]表示用前i棵小樹，第i棵已經(jīng)處理完大樹中0到j(luò)的節(jié)點(為根)。大樹上所有邊的覆蓋情況為mask(記錄奇偶性)。此時的最小費用?？梢允褂盟阉鱽淼玫絠小樹在大樹的j節(jié)點的所有同構(gòu)覆蓋方案。建議使用拓撲排序處理輸入數(shù)據(jù)，這樣搜索會很簡單。注意大樹的根節(jié)點沒有父親邊，也就是說mask的范圍是[0,2N-1)[復(fù)雜度]時間O(N6M2N)空間O(N+M+2N)456AC★★★★★[題意]FunctionalEquation如上圖，f函數(shù)是一個定義在全體整數(shù)上的離散整數(shù)函數(shù)。請在所有滿足以上要求的函數(shù)中找到一個，使如下和式最?。浩渲衳[0..N-1]和y[0..N-1]都是通過輸入的隨機種子生成的109以內(nèi)的整數(shù)輸出最小值。[范圍]1≤C≤161≤N≤10000[分析]數(shù)學(xué)，二分圖，狀態(tài)壓縮動態(tài)規(guī)劃設(shè)g(x)=2f(x)-x+1,則f(g(x))=f(x)+C，進一步化簡得g(g(x))=x+2C由于g(x+2C)=g(g(g(x)))=g(x)+2C可以推出f(x+2kC)=f(x)+2kC我們只需要求出f(0..2C-1)的返回值，就可以求出f在所有整數(shù)上的值，也就是說，f函數(shù)返回值對2C的余數(shù)是一個周期為2C的函數(shù)。由于g(g(x))=x(mod2C)，所以g在2C的剩余系中是一個自反函數(shù)。每一個g(x)必然和一個x唯一匹配.問題轉(zhuǎn)化成二分圖。我們發(fā)現(xiàn)x和g(x)的奇偶性一定相反。(根據(jù)定義)所以我們把0到2C-1的偶數(shù)作為左圖，奇數(shù)作為右圖，根據(jù)求出的限制條件建邊，求一個最小費用完備匹配即可。注意可以以2C為單位調(diào)整模2C相同的點的全體匹配對象。建邊時需要用到一個類似求中位數(shù)的方法，來達到絕對值差的和最小。最后可以用經(jīng)典的KM算法。但由于圖中最多只有16個點，狀態(tài)壓縮動規(guī)也可以通過。[復(fù)雜度]時間O(CNlogN+C3)空間O(NC)457AC★★★★[題意]TheSquareDivOne輸入N*N的01矩陣。可以交換2個相鄰元素。記R[i]表示第i行有多少個1.現(xiàn)在要盡量少的交換使得把矩陣變成第i列有R[i]個1.輸出字典序最小的解。[范圍]1≤N≤18[分析]最小費用最大流棋盤移動問題是經(jīng)典的費用流模型。建立棋盤圖A[i][j]，對于每一列建立虛擬點col[i].A[i][j]-->A[i’][j’]容量為∞，費用為1(i,j)與(i’,j’)相鄰A[i][j]-->col[j]容量為1，費用為0源點-->所有初始是1的A[i][j]容量為1，費用為0col[j]-->匯點容量為R[j],費用為0這樣求最小費用最大流，可以求出最少移動次數(shù)的情況下滿足要求。然而如何保證字典序最優(yōu)呢我們可以把A[i][j]-->col[j]的邊加上一個修正費用設(shè)A[i][j]在字典序里面重要性排在第k位。12345678910111213141516A[i][j]-->col[j]容量為1，費用為2k這樣就可以求得最小字典序的方案。直接使用實數(shù)精度會不夠，建議使用壓縮的2進制高精度。另外也可以使用枚舉刪邊并多次嘗試求費用流的方法來做這道題。[復(fù)雜度]時間O(N8)空間O(N4)點數(shù)V=O(N2)邊數(shù)E=O(N2)高精度C=O(N2)單位增廣網(wǎng)絡(luò)增廣次數(shù)K=O(E)=O(N2)SPFA增廣算法O(VEKC)=O(N8)由于spfa算法時間上界寬松，再加上按位壓縮優(yōu)化，該算法可以通過此題。458AC★★★[題意]ModuloFourDivisor如果：存在正整數(shù)N，使得N1.正好a個約數(shù)模4為0，2.正好b個約數(shù)模4為1，3.正好c個約數(shù)模4為2，4.正好d個約數(shù)模4為3.那么(a,b,c,d)是一個可行的四元組。給4個自然數(shù)集合A,B,C,D。求有多少個(a∈A,b∈B,c∈C,d∈D)是可行四元組。[范圍]1≤集合大小≤500≤數(shù)字≤1018[分析]枚舉，數(shù)學(xué)首先想到枚舉數(shù)字組合再判斷。這樣我們只需要一個O(1)的判斷方法就能通過本題，即是否存在正整數(shù)滿足：1.正好a個約數(shù)模4為0，2.正好b個約數(shù)模4為1，3.正好c個約數(shù)模4為2，4.正好d個約數(shù)模4為3.我們可以把N的質(zhì)因子分成3類：第1類是模4為1的第2類只有2第3類是模4為3的那么，最后決定N對應(yīng)(a,b,c,d)，實際上只跟N的每類因數(shù)內(nèi)部的組合總數(shù)有關(guān)。也就是說，如果(a,b,c,d)可行，我們一定可以找到一個形為5x·2y·3z的N。這里x,y,z都是自然數(shù)。N的約數(shù)共有(x+1)(y+1)(z+1)=a+b+c+d個b≥1b和d的大小不受y的影響。經(jīng)過簡單推導(dǎo)我們發(fā)現(xiàn)：b+d=(x+1)(z+1)d=(x+1)((z+1)/2)那么如果z是偶數(shù)，則有(z+1)/2*2<z+1也就是說b>d，可以直接算出x+1=b–d。注意b和d都必須是x+1的倍數(shù)z是奇數(shù)時b=d.再看a和c的大小如果y=0那么a=c=0如果y>0那么c=b+d,a=(b+d)*(y–1)對于以上所有情況進行判斷即可。總結(jié)：b≠0(b=d)OR(b>d)AND(b-d|b)AND(b-d|d)//X|Y：X整除Y(a=c=0)OR(c=b+d)AND(c|a)[復(fù)雜度]時間O(N4)空間O(N)459AC★★★★[題意]TheContest在NxM的矩陣中填入盡量少種不同數(shù)字，要求每種數(shù)字出現(xiàn)次數(shù)相同，使得每行每列不存在重復(fù)的數(shù)。輸出字典序最小的解。[范圍]1≤N,M≤50[分析]枚舉，二分圖匹配首先可以確定：一定有Max(N,M)種不同數(shù)字，每個數(shù)字被選了Min(N,M)次。我們可以采用按字典序枚舉+判斷是否可行的思路來處理這道題。對于當前行，把要填的數(shù)字看成左圖中的點，矩陣中的元素看做右圖的點。我們只需要按已知條件建立二分圖，然后判斷是否存在完備匹配即可。注意每個數(shù)字必須出現(xiàn)Min(N,M)次。如果還剩p行未確定時，發(fā)現(xiàn)某個數(shù)字還需要填入p次，那么必須優(yōu)先匹配這個數(shù)字對應(yīng)的左圖中的點?？梢宰C明只要數(shù)字出現(xiàn)次數(shù)不存在矛盾，那么當前的匹配不會影響到之后的行是否有解。二分圖完備匹配可以使用匈牙利算法。[復(fù)雜度]時間O(N6)空間O(N2)460AC★★★★★[題意]TheCitiesAndRoadsDivOne一個N個點的無向圖，初始時有一些邊。保證無重邊和自環(huán)。現(xiàn)在要添加若干邊，使得任意兩個點之間都只有1或者2條簡單路徑。求加邊的方案總數(shù)。對1234567891取余。[范圍]1≤N≤20[分析]狀態(tài)壓縮動態(tài)規(guī)劃任意兩個點之間都只有1或者2條簡單路徑。也就是說圖在加邊以后必須是一棵樹，或者一棵樹+1條邊的形式。首先對原圖進行收縮連通分量，不妨設(shè)有M個連通分量。記下每個連通分量的電容量A[i]表示i分量內(nèi)有多少點。如果原圖中已經(jīng)有1個環(huán)，那么我們的問題變成了M個點的生成樹個數(shù)。如果原圖中已經(jīng)有多個環(huán)，那么答案為0。生成樹計數(shù)有一個經(jīng)典的狀態(tài)壓縮動態(tài)規(guī)劃方法：F[mask]表示把集合mask的點做生成樹有多少種方案。轉(zhuǎn)移時，我們不妨取mask中編號最小的點s1為這棵樹的根。如果mask只有1個點，直接F[mask]=1。否則再取次小的點s2.s2一定在樹中是s1的某棵子樹的根。枚舉mask2為s2為根的子樹的點集。易得mask2必然包含s2但不包含s1。對于每一個mask2,都有如下選擇：F[mask–mask2]*F[mask2]*把s2接在mask–mask2的任意一個節(jié)點上方案數(shù)。這樣累加答案是不會重復(fù)的。這個題需要處理環(huán)。那么加一維狀態(tài)。G[mask]表示把mask集合做成一棵樹+一個環(huán)的方案數(shù)。轉(zhuǎn)移時同樣求s1,s2,枚舉mask2注意只有一個點時G[mask]=(A[s1]-1)*(A[s1]-1)否則有三種情況：mask2內(nèi)部有環(huán)mask-mask2內(nèi)部有環(huán)從s2連2條不相同的邊到mask-mask2，使得形成一個新環(huán)并連通這樣的復(fù)雜度是Σ(C[N][i]*2i)=3N優(yōu)化：設(shè)計狀態(tài)時，我們可以不用單純的2進制：對于A值相同的連通分量，我們可以只記這類分量在mask中的個數(shù)，而不用分別01標記。這樣，總共最多只會有5個不同的A值。狀態(tài)會很可觀地減少。[復(fù)雜度]時間O(3N)空間O(2N)461AC★★[題意]FencingGarden你需要靠著一個無限長的直線墻壁修一個矩形圍欄。有N段可用的籬笆，已知它們的長度。籬笆可以連起來用。你有一把鋸子可以把一段籬笆從任意長處據(jù)成2段，但是只能鋸一次。要求圍成的面積最大，面積最大的情況下，平行于墻的那條邊要最長。返回平行于墻的那條邊的長度。[范圍]1≤N≤401≤長度≤108都是整數(shù)[分析]折半，枚舉做成題目要求的形狀，需要拼成3條線段，其中兩條必須長度相等。設(shè)籬笆總長度為m不妨設(shè)平行于墻的那條長度是x顯然兩條短的必須是(m-x)/2面積是x(m-x)/2如果鋸子可以據(jù)2次，那么可以直接求f(x)=x(m-x)/2在R+上的最大函數(shù)值。根據(jù)二次函數(shù)的知識，我們知道x=m/2時函數(shù)有最大值。因為我們只需要把所有籬笆擱在一條直線上，然后在m/4和3m/4處切開就可以了。只能據(jù)一次，說明x和(m-x)/2中至少有一個是必須從原始線段中組合得到的，也就是天然不用鋸的。當然，我們希望天然的x和m/2盡量靠近。(二次函數(shù)滿足凸單調(diào)性)或者天然的(m-x)/2和m/4盡量靠近。我們可以把原來的籬笆數(shù)組分成2組，分別求出所有的組合長度。(分成盡量平均的兩組，最大2^20*2種組合需要考慮)對每組的長度做排序。這樣我們可以枚舉第一組的組合長度，然后動態(tài)在第二組的組合中找到對應(yīng)的長度，使得兩個長度相加離給定的常數(shù)最近。由于2^20完全可以承受，這樣就可以統(tǒng)計答案了。[復(fù)雜度]時間O(2N/2N)空間O(2N/2)462AC★★[題意]WarTransportationN個點的正權(quán)有向圖。人需要從1號點走到2號點。圖中有一條邊被刪除了，但是人必須走到這條邊的起點才知道這條邊是否存在。求一個最壞情況下最好的走法使得路徑最短。輸出最壞情況的最短路。如果刪除一條邊可以使起點無法到終點，輸出-1[范圍]2≤N≤100表示邊的字符串長度≤2500[分析]最短路，動態(tài)規(guī)劃考慮動態(tài)規(guī)劃：F[i]表示到i之前還沒遇到被刪掉的邊，現(xiàn)在到了i，往終點走的最壞情況最小距離是多少。F[i]=max(max(i被刪了一條出邊后到終點的最短路best2[i]),max(F[j]+cost[edge])//edge表示i-->j的邊)best2可以預(yù)處理出來，枚舉邊再在逆圖上算從終點出法的單源最短路。注意F的轉(zhuǎn)移不滿足拓撲序，需要用Bellman-Ford或SPFA進行轉(zhuǎn)移。這類動態(tài)規(guī)劃叫做迭代型動態(tài)規(guī)劃。[復(fù)雜度]時間O(NM2)空間O(M)463AC★★★★[題意]RabbitPuzzle3只兔子在數(shù)軸上的3個不同整點。一個兔子可以繞過另一個兔子跳等長距離，但是不允許跳過多個兔子或跳到有兔子的點上。給出3只兔子的位置A[0..2]，和目標位置B[0..2]。求從A到B恰好K次跳動有多少種不同方案。輸出答案對1,000,000,007取模。[范圍]|坐標|≤10180≤K≤100[分析]二叉樹，動態(tài)規(guī)劃每個狀態(tài)要么有3個出邊(中間向左右，或外側(cè)的一個向內(nèi))，要么有2個出邊(中間向左右，外側(cè)2個到中間距離相等跳不動)容易想到二叉樹的模型。實際上所有的狀態(tài)組成了無限大的滿二叉森林。問題轉(zhuǎn)換成從點p到q走恰好k條邊的方案總數(shù)。設(shè)F[i][x][y]表示走了i步，目前在樹中深度是x，和目標節(jié)點的最近公共祖先的深度為y，有多少種方案。最后求F[k][H(q)][H(q)]即可[復(fù)雜度]時間O(K3)空間O(K2)//滾動數(shù)組464AC★★★★[題意]ColorfulMaze在一個NxM棋盤地圖上，有唯一的起點和終點。有些格子是障礙，不得進入。人可以在有相鄰的非障礙格子間移動?，F(xiàn)在有些非障礙格子被標上了顏色A..G(7種)同一種顏色的格子要么都是陷阱，要么都是正常陸地。已知每種顏色格子是陷阱的概率。人必須走入相應(yīng)的顏色才知道這個格子是否是陷阱?，F(xiàn)在規(guī)定人有2條命，不能掉進陷阱兩次。（可以走過一個陷阱格子）問人使用最優(yōu)策略時，在最壞情況下到達終點的概率是多少。[范圍]1≤N,M≤50概率都是百分數(shù)0..100的整數(shù)形式給出要求精確到10-9[分析]動態(tài)規(guī)劃假設(shè)一個人在地圖中走，他一定會記錄下：現(xiàn)在的位置，現(xiàn)在已經(jīng)碰見過的安全的顏色有哪些，還有已經(jīng)碰到過的陷阱顏色有哪個。注意人不可能同時知道2個陷阱顏色。那么自然的設(shè)計狀態(tài)：F[x][y][mask][k]表示表示目前到了x,y已經(jīng)有mask集合的顏色確認安全，k為不安全的顏色。此時到終點的最大概率。推薦使用記憶化搜索進行轉(zhuǎn)移。注意這題可能出現(xiàn)狀態(tài)之間互相依賴的關(guān)系，也就是說走一個環(huán)但是沒有遇到任何新的顏色。這需要進行特殊處理。我們知道這樣走出一個環(huán)是沒有意義的，最終返回值一定相等。我們可以把等價的狀態(tài)縮在一起然后記憶化搜索。具體實現(xiàn)時，可以動態(tài)生成等價狀態(tài)集合。每一個新集合的第一個被訪問的狀態(tài)為代表，進行最小值記錄。另外終點所在的狀態(tài)集合返回值強行改為1即可。[復(fù)雜度]時間O(2CCN2)//C=7表示顏色數(shù)空間O(2CCN2)465AC★★[題意]BouncingDiceGame直線上有從左到右編號為1..N的空位。初始時甲的棋子在x號，乙的棋子在y號。有一個骰子，上面有1..D的數(shù)字。使用一次骰子就會返回一個1..D的隨機數(shù)?，F(xiàn)在甲乙交替進行投骰子移動棋子。玩家投到了k，那么只能往右移動k格。如果正好到達N，那么該玩家獲勝。如果移過了N，棋子就會彈回來往左移動。已知N,x,y,D求甲先獲勝的概率。[范圍]2≤N≤50001≤x,y,D≤N-1[分析]數(shù)學(xué)，動態(tài)規(guī)劃初步想法：F[i][j]和G[i][j]表示甲/乙在第i次移動后到達j格子的概率這樣由于轉(zhuǎn)移時是計算連續(xù)的一段的和，可以用部分和優(yōu)化。實現(xiàn)均攤O(1)轉(zhuǎn)移。但是我們注意到棋子可能彈回很多次，也就是說，這個游戲可能雙方移動很多次都不會出勝負。這樣F[i][j]中i的取值會很大。幸運的是，我們發(fā)現(xiàn)棋子一旦跳進N-1到N-D的格子，情況就一樣了：棋子只可能在這些格子里移動，而且每一步都是1/D的概率到達終點。因為每次至少要跳動一步，所以在N次以內(nèi)棋子必然跳入這后D個格子之中。于是我們只要把F[i][j]中的i做到N，接下來的勝率可以通過數(shù)學(xué)方法直接計算，或者多次迭代計算近似值。[復(fù)雜度]時間O(N2)空間O(N)//滾動數(shù)組466AC★★★[題意]DrawingBlackCrosses一個NxM的01矩陣，每次可以選擇一個0，然后把同行同列的所有數(shù)變成1。問有多少種不同的操作順序可以把矩陣變成全1。輸出答案對1,000,000,007取余數(shù)。[范圍]1≤N,M≤20特殊：初始時最多只有8個元素是‘1’[分析]狀態(tài)壓縮動態(tài)規(guī)劃由于每行最多只能選1個，所以選的次數(shù)不超過20.我們可以求出選k個格子的方案總數(shù)，然后乘以k!再取模。這樣一來此題變成了經(jīng)典的狀態(tài)壓縮動態(tài)規(guī)劃。F[i][j][k]表示前i行中，沒有剩余0的列的集合為j，被選過的列的集合為k，有多少種方案數(shù)。轉(zhuǎn)移有M+1種：該行不選，或者選一個未被放過且不為”1”的格子。這樣復(fù)雜度還是有些大，注意到最多只有8列有1，我們可以把全0列放在一起考慮。這樣一來可以大大減少狀態(tài)個數(shù)。注意及時取模。[復(fù)雜度]時間O(N217M)空間O(217M)//滾動數(shù)組467AC★★★★[題意]NextHomogeneousStrings一個合法串的定義是：元素都是小寫字母所有長度為N的子串中，都不包含超過D個不同的字母。給出一個小寫字母串S，求字典序大于等于S的，長度和S相同的所有合法串中，第K+1個是多少。[范圍]1≤D≤N≤91≤|S|≤500≤K≤1018[分析]狀態(tài)壓縮動態(tài)規(guī)劃這題的想法是這樣的：用動態(tài)規(guī)劃把求第K小答案的問題轉(zhuǎn)換成求S為前綴有多少個答案的問題。這樣，我們從后往前枚舉原串的后綴，并把后綴改成一個≥原串的合法字符串。我們可以用F[i][S]來表示長度為i，之前N-1位字符的情況為S，有多少種方案。為了確保后綴比原來的串后綴要大，我們需要枚舉后綴的第一位。這樣一來，DP時不需要知道詳細的字符情況，只需要記錄之前N-1位的字符相同情況即可。我們可以用最小表示法：ayax寫成0102（arab,owoz都是0102）這樣可以大大減少狀態(tài)總量。接下來處理好dp輸出答案即可。需要注意的問題：原串可能本身是合法的，枚舉最后的后綴修改字符時應(yīng)該考慮改成相等。N=1時最小表示法只有一個狀態(tài):空數(shù)列。特別注意不能訪問出界DP時中途值可能會超過1018甚至超過64位整型，這時應(yīng)使用實數(shù)運算判斷，如果很大那么換成一個較大的數(shù)即可。（因為K≤1018）[復(fù)雜度]時間O(N2*State*|Σ|)|Σ|=26空間O(N*State)468AC★★★★[題意]MallSecurity大樓有1到N層，每層有若干個電梯站。只有相鄰2層的電梯站間會有直達電梯。第1層和第N層之間也有直達電梯?，F(xiàn)在要安置盡量多的保安到所有電梯站上。滿足同一條電梯道的兩端最多只能有1個保安。問最多可以放多少保安。[范圍]10≤N≤50總共最多有100個電梯站邊數(shù)限制400左右[分析]最大獨立集，二分圖匹配這一題實際上是求一個N層的這樣的圖的最大獨立集。如果層數(shù)為偶數(shù)，那么我們可以直接把奇數(shù)層都歸為左圖，偶數(shù)層歸右圖。問題就轉(zhuǎn)換成二分圖的最大獨立集了，可以用(總點數(shù)-最大匹配)來求。同樣的道理，如果層數(shù)為奇數(shù)，我們可以枚舉其中電梯站數(shù)最少的一層的取舍方案，再把剩下的圖化成二分圖來處理。最壞情況下，11層共100點，點最少的層至多也只有9個點。29M3可以通過測試數(shù)據(jù)。[復(fù)雜度]時間O(2CM3)//M為總點數(shù)空間O(M2)469AC★★★★[題意]TheMoviesLevelThreeDivOne甲乙兩個人決定看N部電影編號0到N-1。他們用這樣一個方法看：兩個人分別有一個等待隊列(先進先出)，最開始他們按照電影的編號順序把N部電影選擇放進2個隊列（2N種方案）然后每當一個人看完一部對方?jīng)]有看過的，就會把看完的電影加到對方的隊列中，并立即開始隊列中下一部電影。告訴你A[0..N-1]和B[0..N-1]分別表示甲和乙看每個電影需要的時間。問有多少種安排方法使得雙方不需要任何等待就能分別看完所有電影。[范圍]1≤N≤47,0≤A[i],B[i]≤20[分析]動態(tài)規(guī)劃本題很難直接統(tǒng)計合法方案，我們轉(zhuǎn)換思路為所有方案2N減去所有不合法的方案。一個不合法的方案一定只會有一個人等待，等待的人不同，方案就一定不同。我們可以分開來算。假設(shè)現(xiàn)在算甲讓乙等待的方案總數(shù)只看一開始被分配到甲的電影：甲[1][2]XXX乙XXXXXX[1][2]乙需要先完成一開始分配到自己隊列的電影才會開始看甲隊列中過來的電影。F[i][j][k]表示分配完編號前i個電影時，乙最少還要給自己分配j時間電影才能保證不等待，甲已安排的時間(圖中甲行的1+2)-乙安排的時間(圖中乙行的X+1+2)的值為k轉(zhuǎn)移有2個：第i個電影可以開始分配給甲，（兩行都加一個段,更新狀態(tài)）那么j要取max(j,k+A[i]),k要變成k+A[i]-B[i]第i個電影可以開始分配給乙（乙行開始的XX變長），那么j要取max(0,j-B[i])，k要變成k-B[i]注意負數(shù)狀態(tài)的存儲。當把所有電影分配完時統(tǒng)計j不為0的總數(shù)，答案減去之即可。[復(fù)雜度]時間O(N3K2)K=20空間O(N2K2)//滾動數(shù)組470AC★★★★[題意]BuildingRoads一個NxM的網(wǎng)格地圖上有各種巖石，有至多4對城市。摧毀不同的巖石需要的費用已知?，F(xiàn)在要摧毀盡量少的巖石，使得4對城市每一對都連通。連通的同一字母表示一塊大巖石：費用如下”a”..”z”:1..26”A”..”Z”:100..2600”1”..”9”:10000..90000”0”:100000[范圍]1≤N,M≤50每種巖石只有1塊。[分析]狀態(tài)壓縮動態(tài)規(guī)劃首先可以根據(jù)相鄰的相同路地塊來建點，相鄰的塊來建邊。最多有8個城市,DPF[i][mask]表示把mask集合的城市連通到i節(jié)點所需要的最少花費。這樣可以求出把一個特定的城市集合連通到一起需要的最少花費。注意到城市可能不會完全連通到一起，我們需要用第二次DP，求出匹配城市互相連通的最少花費。雖然N2為2500，但由于巖石種類有限，最壞情況下，收縮后的圖只有900個點左右，轉(zhuǎn)移需要枚舉28的子集，實際上沒有達到216。[復(fù)雜度]時間O(216N2)空間O(28N2)471AC★★[題意]ConstructPolyline給N個三維非零向量，可以選擇把一部分向量反向，使得向量和的模最大。[范圍]1≤N≤50|坐標|≤10000[分析]枚舉+貪心/隨機化本題的二維版本存在一個O(NlogN)的解法：如果答案向量已經(jīng)確定，那么和答案同側(cè)（點積>0）的向量必然都不取反，異側(cè)的必然都取反。也就是說最優(yōu)方案一定是一個半平面內(nèi)的向量不取反，其余的取反。這樣我們可以把平面向量按極坐標排序，然后動態(tài)維護半平面內(nèi)向量的和，就能保證求出最大的答案。推廣到三維以后，基本假設(shè)仍然成立：最優(yōu)方案一定是一個半球內(nèi)的向量不取反，其余的取反。這個半球要么只有1個向量，要么可以通過調(diào)整使得至少有2個向量在邊界上且不改變答案。我們可以枚舉這兩個邊界上的向量，然后用三維叉積求出法向量（即垂直于兩個邊界向量的新向量。）接著計算半球內(nèi)外的向量和注意這時邊界上的取舍問題，我們可以把問題化簡成上面說道的平面問題來做，這樣可以保證答案準確。不過由于向量個數(shù)較少，隨機調(diào)整也是一個不錯的選擇。事實證明后者實現(xiàn)簡單，而且可以通過所有系統(tǒng)測試。[復(fù)雜度]時間O(N3logN)//這里使用非隨機的方法，瓶頸是排序空間O(N)472AC★★★[題意]ColorfulTilesNxM的網(wǎng)格，每個格子可能是G/B/R/Y這4種顏色之一?，F(xiàn)在要求改變0到K個格子的顏色，使得沒有兩個相鄰格子同色(對角或公共邊相鄰)。求有多少種不同的改色方案。求答案對1,000,000,007取余數(shù)[范圍]1≤N,M≤50K≤N*M[分析]動態(tài)規(guī)劃一個點會有八格相鄰，這個限制十分嚴格。經(jīng)過實踐發(fā)現(xiàn)，如果N>1,M>1，那么只會有3種情況：矩陣變成N/2xM/2個顏色情況完全相同的2x2小矩陣，有4!種。奇數(shù)行是2種顏色相間出現(xiàn)，偶數(shù)行是另2種顏色相間。奇數(shù)列是2種顏色相間出現(xiàn)，偶數(shù)列是另2種顏色相間。如果N和M有一個為1需要另用DP處理否則枚舉第一個2x2的方案，接著分3種情況討論并DP。注意Case2和Case3都重復(fù)算了Case1[復(fù)雜度]時間O(4!N3)空間O(N2)473AC★★[題意]RooksParty一個NxM的棋盤上放入K種顏色的車A[0..K-1]個。不同顏色的車不能在同行或同列。問有多少種不同填法。對1,000,000,009取余數(shù)[范圍]1≤N,M≤301≤K≤10[分析]組合數(shù)學(xué)，動態(tài)規(guī)劃我們知道一個合法的方案把行列進行重新排列仍然是合法的，那么我們知道：G[i][x][y]表示前i種顏色的車填完以后總共占了x行和y列，再填下一種顏色轉(zhuǎn)移就是填當前顏色的車p行q列接著轉(zhuǎn)移到G[i+1][x+p][y+q]*C[x+p][p]*C[y+q][q].最后空余的行列也可以重新組合。所以我們預(yù)先求出F[i][x][y]表示i個車，填x*y的矩陣并沒有任何空行列的方案數(shù)。每次填一行：F[i+c][x+1][y+d]第x+1行總共填c個，其中有d個是另起的列。由插空的經(jīng)典方法，我們知道這樣共有F[i][x][y]*C[y][c-d]*C[y+d][d]種方法。預(yù)處理組合數(shù)，注意優(yōu)化取余運算，就可以通過該題了。[復(fù)雜度]時間O(N6)空間O(N4)474AC★[題意]GameWithGraphAndTree一個N個點的無向圖，一棵N個點的樹。求樹和圖有多少種點的匹配方法，使得當樹中兩點有邊時，圖中匹配對應(yīng)的點也有邊。[范圍]1≤N≤14[分析]狀態(tài)壓縮動態(tài)規(guī)劃，樹型動態(tài)規(guī)劃F[i][j][mask]表示樹中i為根的子樹，i對應(yīng)原圖中的j點，mask為原圖已經(jīng)被匹配的點集，這種情況的方案數(shù)。常數(shù)優(yōu)化。注意：轉(zhuǎn)移時，易被剪枝的變量應(yīng)該優(yōu)先枚舉。[復(fù)雜度]時間O(22NN2)空間O(2NN2)475AC★★[題意]RabbitProgramming在編程比賽中有M個選手，N道題目。不同的題目有得分Score[0~N-1]?，F(xiàn)在已經(jīng)完成了一些題目的評測。給出所有選手在所有題目上的測試情況(正確/錯誤)，以及還沒有評測的題目的提交情況(提交/未交)。最后要在分數(shù)最高的Qualified個選手中任選Selected個人出來作為最終的隊伍人選。問一共存在多少種不同的可能的方案。（分數(shù)相同時，優(yōu)先編號考前的）[范圍]1≤Selected≤Qualified≤M≤501≤N≤50|Score[i]|≤105[分析]數(shù)學(xué)/數(shù)論首先把已經(jīng)測完的分數(shù)直接算出來，對于沒測的分數(shù)，我們可以這樣想：假設(shè)某個方案是可以的，我們不妨設(shè)被選中的人交了的題目都得分了，沒被選中的人交的題目都錯掉了，這樣這個方案仍然是合法的。也就是說，我們只需要考慮每個人的最大可能得分和最小可能得分就可以了。關(guān)于統(tǒng)計與判重：之后我們枚舉最后被選中的人中分最低的選手編號i，并定他得到了最大可能分(如果有分數(shù)相等的也只能在i之前)再統(tǒng)計兩類人的個數(shù)：分數(shù)一定比i分數(shù)高的人數(shù)P分數(shù)可能比i分數(shù)高也可能低的人數(shù)Q這樣通過組合數(shù)就可以計算答案了。Answer+=C[P][x]*C[Q][Selected–1-x](0≤x＜Selected,Selected–1–x+P≤Qualified)[復(fù)雜度]時間O(M2)空間O(NM+M2)476AC★★★[題意]SpaceshipEvacuation一個無向，每個點最多屬于一個簡單環(huán)。0號點為出口。初始時有crewSize個人，可任意分布在圖中的任意點上。圖有N個點M條邊。每一條邊(A,B)都有從A到B和從B到A分別的經(jīng)過次數(shù)限制?，F(xiàn)在問，最少給圖中邊的次數(shù)限制一共加多少，才可保證所有人都能走到出口。不可解輸出-1.[范圍]1≤crewSize≤1051≤N,M≤50[分析]樹，動態(tài)規(guī)劃不連通輸出-1首先猜想最壞情況下一定是一開始所有人都在同一點。也就是我們只需要保證原點到任意點的最大流量都大于等于crewSize即可。這點可被證明。又注意到原圖的性質(zhì)，不難想到利用樹的性質(zhì)來推導(dǎo)，如此一來問題就是求出所有環(huán)，環(huán)上一定有離根最近的節(jié)點R。環(huán)上任意節(jié)點都必須滿足從左走到R路上容量的最小值，加上從右走到R路上的容量最小值，要大于等于crewSize.另外非環(huán)邊往回走的方向必須要加到大于等于crewSize。對于一個環(huán)，每一個可能的起始點，處理好左右兩條路徑上的數(shù)值。(我們看做可以向左或向右從兩端流出環(huán)，這樣就變成鏈了)L[i]表示環(huán)中第i點往左走的流量限制，R[i]表示向右。每個點往左右的流量和應(yīng)至少為crewSize。而且L[i]+R[i]=crewSize就完全可以不用增加了。不難想到調(diào)整完以后，L應(yīng)該盡量遞減，R盡量遞增。一個動態(tài)規(guī)劃的方法是用F[i][j]表示環(huán)中把前i個點的往左的流量都≥j，且都滿足各個位置上L[i]+R[i]>=crewSize，的最少調(diào)整次數(shù)。這樣就可以解決本題了。[復(fù)雜度]時間O(N*CrewSize)空間O(N*CrewSize)477AC★★★[題意]KingdomTour一棵N個節(jié)點的樹，現(xiàn)在從根出發(fā)走遍所有的邊。每條邊通過時都會有費用?，F(xiàn)在每條邊允許通過邊多次，而且還可以進行不多于K次傳送(從任意點到任意點)。每次傳送的費用都是L。求遍歷最后回到根的最小費用。[范圍]1≤N≤2001≤K≤100L與邊費用≤104[分析]樹型動態(tài)規(guī)劃首先可以研究路線的性質(zhì)。不難發(fā)現(xiàn)，一定存在一種最優(yōu)解，滿足一旦進入了一棵子樹，完成這棵子樹的遍歷之前都不會到子樹之外的地方去。這點可以通過微調(diào)法反證。那么第一感覺是這題比較像樹型背包DP.F[i][j]表示以i為根的子樹，用j次傳送的最少遍歷費用。但是光這樣狀態(tài)還不夠，我們必須弄清楚路線進出這個子樹的狀態(tài)。算法入選：F[i][j][k]表示i為根的子樹，用j次傳送的最少遍歷費用。這條路徑的端點有k個在樹根上。(k=0,1,2)k=0表示路徑是跳進這棵子樹來的，遍歷完時也不在根。k=1表示路徑是從根走進來的最后不在根，或，我們是跳入開始最后回到根。k=2表示路徑是從根進從根出的。根據(jù)狀態(tài)的定義可以按部就班設(shè)計轉(zhuǎn)移。這是一個比較直觀的做法，實現(xiàn)會稍有復(fù)雜。另一個想法：我們注意到一條邊只會被經(jīng)過1或者2次。我們忽略路徑的連續(xù)性。事實是我們是要把原圖改造成一個歐拉圖。歐拉圖也就是說所有點度為偶數(shù)。傳送的使用相當于把2個節(jié)點加上一個度，走重復(fù)的路也相當于加上2個度。在這個基礎(chǔ)上求價值最小。這樣可以得到一個比較容易實現(xiàn)的動態(tài)規(guī)劃F[i][j]表示i子樹，用傳送加了j個度，遍歷的最少花費。復(fù)雜度相同。[復(fù)雜度]時間O(NK2)空間O(NK)478AC★★[題意]RandomApple有N個盒子，M種蘋果。i盒子里有A[i][j]個j種蘋果。保證每個盒子都有至少一個蘋果?，F(xiàn)在任選一個盒子的非空集合(每個集合被選的概率相同)，再從選中的盒子中任拿一個蘋果(每個蘋果被選中的概率相同)。問最終拿到每種蘋果的概率。[范圍]1≤N,M≤500≤A[i][j]≤199[分析]概率，動態(tài)規(guī)劃本題是一道數(shù)學(xué)概率題。對于每個盒子的每種果子A[i][j]，我們來考慮它將會對最終答案產(chǎn)生多大貢獻。對于所有包含i的盒子集合S，貢獻為A[i][j]*1/Sum[S]也就是說，如果我們能夠求出R=Σ1/Sum[S](S為盒子的非空集合)問題就能得到很好解決。我們發(fā)現(xiàn)Sum[S]的取值范圍不大，為1到500000左右，我們想到：R中分母為i的項出現(xiàn)了f[i]次。就可以進行DP，f[i]+=f[i–ΣA[j][x]]類似于背包再計算再直接枚舉分母累加結(jié)果了。注意最后是除以2^n-1[復(fù)雜度]時間O(NC)C為果子總數(shù)空間O(NC)479AC★★★[題意]TheBoardingDivOne一維空間上有2N個位置，最初有N個人在1..N的位置上，它們要到N+1..2N去。每個人的目的地都是確定的，人和目的地一一對應(yīng)的。每單位時間內(nèi)，還沒到目的地的人會向后走一步，前提是后面的位置空閑。注意即將離開位置的人所在的地方也是空閑的，也就是說可以大家一起往后走。如果一個人走到了目的地，就會在原地停留74單位時間，這段時間沒有人可以通過該位置。74時間后，該人消失，位置空閑。按位置順序告訴你N個人的目的地在哪，有些人的目的地是-1，表示不知道，可能是任何一個已知沒出現(xiàn)過的目的地?，F(xiàn)在已知所有人在T時間之內(nèi)全部消失，求有多少種可能的目的地匹配方式。[范圍]1≤N≤181≤T≤222[分析]狀態(tài)壓縮動態(tài)規(guī)劃數(shù)字范圍告訴我們本題很可能是搜索或者狀態(tài)壓縮動態(tài)規(guī)劃。然而我們嘗試設(shè)狀態(tài)發(fā)現(xiàn)都不能完整表示。這時應(yīng)該注意到奇特的數(shù)字大小。74和222我們知道一個人在毫無阻攔的情況下至少需要74+1時間才會消失。被阻攔一次(有人停留擋路)，就會額外加上74的時間，此時為149.這時如果再被阻攔一次，就至少需要223點時間，已經(jīng)大于T的范圍。也就是說，一個合法的狀態(tài)中，每個人最多被阻攔一次?？梢哉f，如果P[1..N]是表示N個人的目標位置的排列，那么這個排列不會出現(xiàn)長度為3的連續(xù)遞減子序列P[i]>P[j]>P[k]ANDi<j<k如此一來DP就比較好表示狀態(tài)了。F[mask][j]表示已經(jīng)安排好靠后的mask這些元素(狀態(tài)壓縮)，此時P值最小的人導(dǎo)致的阻攔現(xiàn)象(只能被最小的人阻攔，否則一定>T)會把現(xiàn)在新加的人卡在j位置上。那么轉(zhuǎn)移的時候注意不能出現(xiàn)長度>2的遞減子序列，每次比較新加的P[x]和j即可。[復(fù)雜度]時間O(N22N)空間O(N2N)480AC★★★★★[題意]StringDecryption一個數(shù)字串可以通過如下方法編碼：從前往后用1個十進制數(shù)和1個數(shù)字代替一段極長的同字子串。例如”1122”變成”2122”(2個1+2個2)這種編碼是唯一的，但是這種編碼的解碼是可能不唯一的。比如”2122”可以被理解為”1122”或者”22222…2”(212個2)現(xiàn)在輸入字符串S[0..L-1]輸出所有通過兩次編碼以后變成S的不同字符串個數(shù)。輸出答案對1,000,000,009取余[范圍]1≤L≤500[分析]動態(tài)規(guī)劃如果題目是輸出一次反編碼的方案數(shù)，那么很簡單，我們可以用DP:F[i]表示前i位被翻譯為原串的方案數(shù)。F[i]=ΣF[j]S[j]≠S[i]且S[j+1..i-1]是合法數(shù)字對于2次反編碼，我們發(fā)現(xiàn)會出現(xiàn)大量同樣數(shù)字的情況。這樣事實上被反編碼1次出來的很長一段相同數(shù)字，再反編碼的情況會相對比較簡單。動態(tài)規(guī)劃：F[i][j][k]表示第一次解碼完成了原串前i位，第二次解碼的末尾數(shù)字是j。如果k=1表示第二次解碼把前i位恰好用完，如果k=0表示前i位的第一次解碼后還有剩余數(shù)字(開頭不允許為0)這個DP的原理在于，同一段長數(shù)字，是不能被譯成多個最終段的。因為他們數(shù)字都是一樣的。轉(zhuǎn)移的時候有很多情況需要注意。第一層轉(zhuǎn)移必須滿足表示數(shù)字的那段頭元素不為’0’不能從同樣的數(shù)字結(jié)尾轉(zhuǎn)移DP的初值特殊處理，可以采用一個額外的符號’@’如果是從第二層解碼用完前i符號的狀態(tài)轉(zhuǎn)移而來，那么一段長度為X的數(shù)字拆開有X-2種可能。如果是從有剩余的狀態(tài)轉(zhuǎn)移而來，那么有X-1種可能。第二層轉(zhuǎn)移的數(shù)字,不允許從’0’開始[復(fù)雜度]時間O(K2N2)//K為進制常數(shù)10空間O(KN)481AC★★[題意]TicketPrinter直線上有N個打印機，位置為A[1..N]，你需要打印N個數(shù)字，大小分別為B[1..N]。打印機內(nèi)部的初始數(shù)字依次為C[1..N]。你最開始在S號打印機上。移動1距離需要耗費1時間。每個打印機只能打印1次。打印一個數(shù)字需要花費1時間。更多的，你需要花費|C[i]-B[j]|的時間來把打印機調(diào)整成需要的數(shù)字。打印數(shù)字任務(wù)只要人經(jīng)過對應(yīng)的打印機就可以設(shè)定。調(diào)整和打印都是自動完成的不需要守候。你需要決定如何分配打印機，以及人如何行動。使得完成所有打印的時間最短。[范圍]1≤N≤16[分析]狀態(tài)壓縮動態(tài)規(guī)劃范圍非常具有啟發(fā)性。本題無疑是一道狀態(tài)壓縮的動態(tài)規(guī)劃試題。容易分析出的結(jié)論是：人一旦經(jīng)過某打印機，就一定會讓它打印。那么在一個時間人所安排了任務(wù)的打印機必然是一個包括S的連續(xù)區(qū)間。我們用F[L][R][mask][side]表示人安排完了L到R的打印機，還剩mask集合的數(shù)字未被安排，現(xiàn)在在side位置(side必須為L或者R，我們可以規(guī)定side=0表示L，side=1表示R)此后還需要的最長時間。最后求F[S][S][2N-1][0]轉(zhuǎn)移時考慮向左/向右擴充區(qū)間，以及新數(shù)字的選擇。唯一要注意的是216*16*16*2可能超過空間限制，我們對L,R稍作壓縮，由于必須滿足1<=L<=S<=R<=16，所以[L][R]最多只有不到100種可能。216*100*2就不會超過限制了。[復(fù)雜度]時間O(2NN3)空間O(2NN2)482AC★★★★★[題意]BalancingAct有N個已知重量砝碼，M個未知重量砝碼?，F(xiàn)告訴你M個未知砝碼的大小，問其他人可不可以在不知道的情況下通過天平確定出這M個砝碼分別的重量。砝碼重量都是1到100,000,000的整數(shù)。[范圍]1≤N≤201≤M≤4[分析]折半，枚舉由于每個砝碼可以選擇不放，放左盤，放右盤。天平的稱法有3^(N+M)種，不能直接枚舉。我們注意到未知砝碼不多，于是我們想，先放未知砝碼，然后用已知砝碼來確定兩邊未知砝碼的總和的差的范圍。我們可以把20個已知砝碼分為2組。把組內(nèi)可稱出的重量全部求出來排序。(最多310=59049種)對于一個34之一的未知砝碼的放法X，我們都可以通過枚舉，求出最逼近X真實偏差的已知砝碼重量組合。也就是說，我們對于每個未知砝碼的方法，都能確定一個最貼近的稱量法。如何確定砝碼重量呢。一個思路是，如果這個未知砝碼的值并非真實值時，我們得到的所有稱量結(jié)果仍然不變，那么我們就無法確定砝碼的值了。于是我們枚舉4個未知砝碼的偏差。看范圍是不是會發(fā)生改變。最終可以得出這個砝碼能否被確定。經(jīng)嘗試，只需要枚舉±4的誤差即可。(9M)即最壞情況：未知砝碼{a,b,c,d}a=2b=4c=4d此時{a,b,c,d}和{a+4,b+2,c+1,d+1}可能測量結(jié)果相同。[復(fù)雜度]時間O(3N/2N+2M*M)//均已忽略常數(shù)空間O(3N/2+3M)483AC★★[題意]SheepN只羊過河，羊有重量W[0..N-1]。過河只有一條船，船會有一個容量。每次擺渡，羊群用如下策略：一直往船上送最重的可以上船的羊，直到上不了。然后把這批羊運到河對岸去。(船不需要羊劃回來)現(xiàn)在羊群想在L次以內(nèi)完成擺渡，問船的容量至少應(yīng)該為多少。[范圍]1≤N，L，W[i]≤2000[分析]枚舉，貪心此題初看不難，很容易想到從小到大枚舉答案+貪心模擬，但是答案可能會很大：數(shù)據(jù)：2000*2000,限制1次此時答案達到最大4000000,是O(N2)的。時間復(fù)雜度：O(N4)在已知容量的情況下優(yōu)化模擬，我們先對羊群排序，加入使用跳轉(zhuǎn)標記，每次用二分找剩余容量內(nèi)的羊，如果不行就一直走跳轉(zhuǎn)邊。跳轉(zhuǎn)邊在走的時候應(yīng)該及時更新。這樣時間復(fù)雜度相當于并查集的路徑壓縮。我們簡記為線性的。枚舉答案從1開始是很劃不來的。我們可以算出一個下界：總重量/次數(shù)顯然答案不會小于這個值。所以我們從這個值開始枚舉即可。事實證明效果極好。需要注意的是，此題不能直接二分答案!因為容量變大以后羊渡河的方案可能會改變。換言之，該題的解不滿足可二分性。用二分求一個大概的答案范圍，再往小的方向找也是一種成功的解題思路。[復(fù)雜度]時間O(N3logN)空間O(N3)484AC★★★★[題意]NumberMagic魔術(shù)師要做一些卡片，每個卡片上寫恰好M個1到N的整數(shù)。魔術(shù)師會讓小孩從1到N中任想一個整數(shù)，然后依次詢問這個數(shù)是否在卡片上。小孩如實回答。問魔術(shù)師最少需要做多少卡片，可以保證根據(jù)回答猜出原數(shù)字。[范圍]1≤M＜N≤109[分析]數(shù)學(xué)，數(shù)論從魔術(shù)師如何區(qū)分數(shù)字的觀點來考慮。不妨給卡片編號，那么每個數(shù)字在卡片上的出現(xiàn)情況可以看出一個二進制數(shù)。由于我們要卡片盡量少，同時能夠區(qū)分出數(shù)字來，所以我們應(yīng)該選二進制數(shù)中1盡量少的N個不同的數(shù)。二分答案：x為卡片的張數(shù)那么分配的二進制數(shù)從0開始(不在任何卡片上出現(xiàn))可以分配C(x,0)個然后是1個1的二進制數(shù)，分配C(x,1)個然后是2個1的..分配C(x,2)個...這樣一定可以安排成出現(xiàn)的總數(shù)字最少?？墒菃栴}是這樣一定能排恰好每張M個嗎。我們注意到這種二進制編號法的可調(diào)整空間是很大的，事實上可以證明，所有的數(shù)字只要總共出現(xiàn)X*M次，那么一定可以調(diào)整成每張卡片都M個，而且仍然滿足要求。注意最開始需要M=min(M,N-M)以保證解的最優(yōu)性[復(fù)雜度]時間O(log3N)空間O(log3N)485AC★★★[題意]Deposit有兩個嚴格凸多邊形A和B，頂點數(shù)分別為N和M。A多邊形嚴格包含B?，F(xiàn)有如下操作:在A的邊上任選一點，往A邊界最遠點沿直線前進。如果中途進入B那么這個點可行。如果沒進入B那么這個點不可行。選點完全隨機。問選到可行點的概率。精確到1E-9[范圍]1≤N,M≤50[分析]計算幾何這題的選點有2條限制：1.到A的邊界最遠;(可證明最遠點一定是某個頂點)2.路線與B相交。我們不難想到分離事件線段的方法。對于條件1.我們可以求出A任意兩頂點連線的中垂線，中垂線與A的交點作為事件點。O(N3)對于條件2.我們可以求A上所有點和B上所有點之間連線。同樣在A的邊界上留下事件點。O(N3)以上兩個操作之后，A的邊界被分成了O(N2)個事件段。顯然每個事件段要么是全可行，要么是全不。那么我們?nèi)∶總€事件段的中點，用O(N)的時間尋找最遠點，再O(N)的時間做一次相交檢查，就能得出每個事件段的答案。累加即是總答案。本題需要用到很多計算幾何的方法，程序?qū)崿F(xiàn)比較麻煩。建議作為幾何的練習(xí)題。[復(fù)雜度]時間O(N3)空間O(N2)486AC★[題意]BatmanAndRobin給出平面上N個整點，現(xiàn)在需要用2個不相交的凸多邊形蓋住所有的點。求較大凸多邊形的面積的最小值。允許凸多邊形退化成線段或點。[范圍]0≤N≤50坐標絕對值1000以內(nèi)[分析]凸包，枚舉兩個凸包中，總有一條凸包上的邊所在直線把它們分開。我們枚舉2個點的連線，再枚舉這條分割線的微調(diào)，然后分開做凸包就可以了。微調(diào)只有2種：，實現(xiàn)時我們可以枚舉點p,q。在向量p,q右手邊的點全部納入集合1，其余的納入另一個集合。這樣由于p,q和q,p都會被枚舉到，所以可以考慮上圖的2個情況。注意凸包退化的情況，需要輸出0[復(fù)雜度]時間O(N3logN)空間O(N3)487AC★★[題意]BunnySequence給定整數(shù)m?，F(xiàn)在對于任意的整數(shù)x都有如下變換：如果x是m的倍數(shù)，那么x=x/m如果不是，那么x=x+1求恰好最少需要n次變換才到1的這樣的x的總數(shù)。答案對1,000,000,009取模[范圍]2≤m≤1060≤n≤106[分析]數(shù)學(xué)，動態(tài)規(guī)劃首先容易想到轉(zhuǎn)換問題：我們可以從1往x倒過來變換，每次可能有多種選擇。我們發(fā)現(xiàn)這個轉(zhuǎn)移圖像是不存在環(huán)的，也就是說可以直接第推不會有后效性。那么可以想出二維dp：F[i][j]表示第i次，現(xiàn)在對m取模是j，有多少到法。經(jīng)觀察，我們發(fā)現(xiàn)可以用部分和來優(yōu)化這個DP。實際上最終的遞推式就是S[i]=ΣS[i-k]1≤k≤m通過維護一個sum變量并動態(tài)對其進行更新，我們得出了一個O(N)的算法。注意最后輸出需要減去一個S[n-m]。轉(zhuǎn)移不能回到原點。特判n=0的情況[復(fù)雜度]時間O(N)空間O(N)488AC★★★[題意]TheBoringGameDivOne3個人玩游戲：A和B一隊，C一個人一隊。每輪游戲中，玩家可以任意射擊其它玩家。射死隊友-1分，射死敵人+1分。一旦被射死了玩家就不能再射擊。當某個隊全軍覆沒時，一輪游戲結(jié)束。然后大家復(fù)活重新開始?，F(xiàn)在告訴你x輪游戲后最終統(tǒng)計的分數(shù)ScoreA,ScoreB,ScoreC以及三個人被射的總次數(shù)KilledA,KilledB,KilledC.求最小可能的游戲輪數(shù)xMin和最大可能的游戲輪數(shù)xMax[范圍]輸入絕對值均在1000以內(nèi)[分析]數(shù)學(xué)，數(shù)論經(jīng)過研究發(fā)現(xiàn)，一輪游戲總共有9種可能結(jié)局。我們設(shè)這9種情況分別發(fā)生的次數(shù)為a[1]..a[9]那么根據(jù)已知的6個常數(shù)，我們可以列出6個方程。注意6個方程9個未知數(shù)是無法直接解的。(事實上只有5個線性無關(guān))經(jīng)過深入研究我們發(fā)現(xiàn)枚舉其中2個情況發(fā)生次數(shù)以后，原問題變得足夠簡單，以至于我們可以求出總場數(shù)，同時根據(jù)不等式判斷是否存在合法解。那么就可以求最值了。[復(fù)雜度]時間O(N2)空間O(1)489AC★★★★[題意]AppleTrees直線上有D個空位，相鄰空位距離為1?，F(xiàn)在要種N棵蘋果樹。要求第i棵蘋果樹不能與其它樹距離小于R[i]。問總共有多少種不同的種法。輸出答案對1,000,000,007取模。[范圍]1≤D≤1051≤N,R[i]≤40[分析]動態(tài)規(guī)劃本題很像動態(tài)規(guī)劃。但初看之下很難設(shè)計出一個計算方案的高效算法。但如果我們換一種角度思考：如果首先把樹的左到右順序排好，并且把樹之間的間距縮到盡可能小，此時我們計算D-1中還有多少個剩余間距，那么可以插入到N+1個空隙中并且都是不同的合法方案。注意到R[i]也都比較小，也就是說，最壞情況下，所有樹縮小間距以后占的總距離不會很大。那么我們用另一種動態(tài)規(guī)劃：首先把樹按R從小到大排序F[i][j][k]表示前i棵樹，目前形成了j個緊縮塊，所有緊縮快已經(jīng)占用的距離長度和是k，的總方案數(shù)。最后我們求ΣF[N][1][x]*C[D–x+N-1][N](0≤x＜D)[復(fù)雜度]時間O(ND+N2R)空間O(N2R)490AC★★[題意]InfiniteLab有一個無限多行，M列的網(wǎng)格地圖A。每連續(xù)的N行是一個循環(huán)節(jié)，也就是說A[i+N][j]==A[i][j]。網(wǎng)格上有空地、障礙物?？盏厣峡赡軙袀魉蜋C。每一行只會有0或2個傳送機，用于同行內(nèi)的傳送。也可以選擇不用傳送機。移動到相鄰格子(公共邊相鄰)或者使用傳送機都要1單位時間。求從(r1,c1)到(r2,c2)的最短時間[范圍]1≤N,M≤20r1,r2的絕對值≤10150≤c1,c2＜M[分析]BFS，動態(tài)規(guī)劃本題難在輸入的行號比較大，首先我們可以把循環(huán)節(jié)旋轉(zhuǎn)到以r1為起始行，那么r2=r2–r1,r1=0;方便處理接下來，我們可以求出從第一行走到下一個循環(huán)節(jié)的第一行，這M2個起止點對的最短路。同時求出(r2,c2)到所在循環(huán)節(jié)第一行各列的距離。這里可以用BFS,但是注意要多算幾層循環(huán)節(jié)，因為最優(yōu)解可能走出循環(huán)節(jié)再走回來。事實證明在80個連續(xù)循環(huán)節(jié)上做BFS可以取得正確答案。接下來F[k][i][j]表示從(0,i)走到(N*2k,j)的最短距離可以用類似矩陣快速乘法的方法來第推和計算答案。[復(fù)雜度]時間O(M3logN)空間O(M2logN)491AC★★[題意]FoxCardGame有2組實數(shù)A[],B[]，每組都是N個，大小為1.0到100.0。每次在兩組中各取一個沒選過的數(shù)a=A[i],b=B[j]分子+=max(a*b,a+b)分母+=min(a*b,a+b)問執(zhí)行K次時(分子/分母)的最大可能值是多少。精確到1E-9[范圍]1≤N≤50[分析]分數(shù)規(guī)劃，網(wǎng)絡(luò)流/貪心此題不難想出一個匹配的模型，首先二分答案Ans，然后對每一個配對計算對答案的影響值max(a*b,a+b)–Ans*min(a*b,a+b)以這個值為匹配費用，求流量限制為K的最小費用最大流并不斷調(diào)整答案直到滿足精度要求。這是一個正確的解答。然而這題的特殊性太多，例如我們會發(fā)現(xiàn)如果數(shù)字都≥2，那么必然匹配a*b>=a+b，可以證明此時選數(shù)不會發(fā)生大小交叉情況。也就是說，小的配小的，大的配大的。相反，如果a*b<a+b,那么必然是大的配小的，小的配大的那么另一種方法就是，首先對兩列數(shù)排序枚舉有多少對匹配是小-大大-小這樣的(從小數(shù)字開始)再對剩下要選的數(shù)做動態(tài)規(guī)劃，便可求出最大答案。事實上剩下的數(shù)也可以不做動態(tài)規(guī)劃，直接枚舉2列數(shù)從小的一端選多少個，剩下的全都從大的一端選。顯然不這樣取的方案一定可以通過調(diào)整變成這樣以后答案不減小。[復(fù)雜度]時間O(N4)空間O(N)492AC★★★★[題意]TimeTravellingGogoN個點，M條無向邊。你要從0走到N-1。有S段時間是不下雨的，只有當不下雨時你才能夠在路上移動，下雨時你必須躲在點里。你有一個時間機器，當你逗留在某個點的時候你可以花StartTime+x的時間把天氣變到x時間之前的狀態(tài)。也就是說，你可以倒退到不下雨的時間，但是你不會改變位置，你已經(jīng)花費的時間也不會被扣除。求最短需要花費的時間[范圍]1≤N≤201≤S≤200≤所有輸入的時間≤109時間段按照從小到大，并且均是獨立的時間段。1≤邊權(quán)，機器啟動時間≤109[分析]離散事件，最短路本題無疑是一個最短路模型，關(guān)鍵是如何建邊。我們不能用State[v][time]表示在v點，天氣運作到time時的最短路，因為time的范圍太大。一個很自然的想法是，我們是否能離散出一些關(guān)鍵的時間點來縮小狀態(tài)量呢。首先發(fā)現(xiàn)點數(shù)不多，我們不妨先做多源最短路把兩點間距離求出來。實際上在一段不下雨的時間中，我們也只會從一個點到達另外一個點。這樣為了時間最短，我們一定會盡可能在雨停的那瞬間從一點出發(fā)，或者使用時間機器時倒退到一個時間點使得出發(fā)以后剛好在要下雨的時候到達另一點。這些時間與位置就是我們尋找的事件狀態(tài)。我們也把時間機器是否打開看做另一維狀態(tài)。這樣一來，我們用State[v][time][is_open]來表示狀態(tài)，對于每一個v，最多可能有N*2*S個事件時間，源點多一個事件時間0。按照事件狀態(tài)間的轉(zhuǎn)移來在新圖里建邊，這題就不難了。用Dijkstra+Heap可以達到很好的效率，用SPFA也可以通過。[復(fù)雜度]時間O(N2Slog(N2S))空間O(N2S)493AC★[題意]AmoebaDivOne有一個2N*2M的01矩陣。輸入的字符串每一個字符為一個1位的16進制數(shù)，表示4個共角格子的0/1情況。比如’8’表示：0001現(xiàn)在要選出一塊連續(xù)的”0”,使得任何一行或任何一列上選的0都是連續(xù)一段。求總共有多少種選法，輸出答案對1,000,000,007取模。[范圍]1≤N,M≤50[分析]動態(tài)規(guī)劃此題是常見的區(qū)間動態(tài)規(guī)劃模型。F[i][x][y][p=0..1][q=0..1]表示我們選的形狀到第i行是x到y(tǒng),左/右邊線是否已經(jīng)縮小過了(p/q)，這種情況下有多少種方案。注意考慮轉(zhuǎn)移時邊界相等的情況。我們發(fā)現(xiàn)這樣是O(N*M5)的，需要優(yōu)化。容易發(fā)現(xiàn)可轉(zhuǎn)移狀態(tài)是列號上連續(xù)的，所以我們可以使用部分和優(yōu)化。G[i][x][y][p][q]表示ΣF[i][0..x][0..y][p][q]這樣就可以方便的O(1)轉(zhuǎn)移了[復(fù)雜度]時間O(NM2)空間O(NM2)494AC★★[題意]KnightsOut一個N*M的01矩陣，初始時全是0。選一些格子，做以下操作：例如選擇了#這個位置，那么要把#和標了1的位置的格子全部取反。(類似國際象棋的馬)010101000100#001000101010問有多少種選法，使得最后變成全1。輸出答案對123,456,789取余[范圍]1≤N,M≤150[分析]高斯消元本題模型是求模線性方程組的解的個數(shù)，(每個格子是否被選作為未知數(shù)，最后每個格子的相關(guān)點的異或值等于1作為方程)該方程組的解個數(shù)也就是2^x其中x為自由元的個數(shù)。但初始時是N*M個未知數(shù)，不能直接高斯消元。為此我們想到化簡方程組。經(jīng)過推算可以發(fā)現(xiàn)，一旦前2行以及前1列的格子對應(yīng)的未知數(shù)確定，就可以直接推導(dǎo)出所有的未知數(shù)了。我們選這些未知數(shù)為代表來列方程組，這樣一來方程組的大小縮小，可以求解了。注意使用位壓縮的辦法來提高效率，C++的同學(xué)可以使用bitset[復(fù)雜度]時間O(N4)空間O(N3)495AC★★★★[題意]StrangeElevator一棟大樓有H層(1到H)，有一個奇怪的電梯。電梯包含N個房間，兩房間的高度差是固定的，且沒有兩個房間在同一層樓。電梯可以上下移動，但是不會出現(xiàn)某個房間高度小于1或者大于H的情況。可以限制電梯只能在哪些高度開門。求有多少種電梯的設(shè)計方案滿足：每層樓都恰好只能從一個電梯房間到達[范圍]1≤N≤H≤109[分析]動態(tài)規(guī)劃此題數(shù)學(xué)味很濃。首先我們發(fā)現(xiàn)電梯一定會?？縃/N次，如果H不是N的倍數(shù)那么就無解。對于每一次?？?，電梯的每個房間都會對上一層樓。如果我們給樓層標上數(shù)字，就會發(fā)現(xiàn)每個數(shù)字的出現(xiàn)區(qū)域是全等的形狀。電梯1.1.....1.1......2.2.....2.2........3.3.....3.3......4.4.....4.41212343412123434一個關(guān)鍵的思路是，一個電梯方案如果可行，那么以其中某個房間到達的位置為新電梯位置的另一個新方案也可行。比如對應(yīng)上圖。(四個”1234”的位置)11..11............22..22................33..33............44..441122112233443344也就是說，一個(H,N)的問題是和(H,H/N)的問題完全等價的。我們把這種變換叫做變換1進一步分析，一旦有K個電梯房間是連續(xù)的，那么H還必須是K*N的倍數(shù)。在這個情況下，一定會把樓層每連續(xù)K個分成一段來算。然后縮小成(H/K,N/K)的新問題。為了避免重復(fù)統(tǒng)計，我們設(shè)計狀態(tài)：F[i][j]表示i層樓，j個電梯，而且不存在相鄰房間的方案總數(shù)。我們發(fā)現(xiàn)在變換1之后，一個不連續(xù)的電梯方案會變成有連續(xù)的；一個有連續(xù)的方案一定會變成不連續(xù)的。那么可以設(shè)計轉(zhuǎn)移：F[i][j]=ΣF[x][i/j]//x為i的非1約數(shù)。轉(zhuǎn)移的意思是說，求一個不存在相鄰房間的方案總數(shù)，通過一次變換1以后相當于求所有存在相鄰房間的方案數(shù)。然而有相鄰的情況下就可以縮小問題規(guī)模，當然必須滿足段的數(shù)目是層數(shù)的約數(shù)。(從F[i][j]=F[x][x/(j/x)]