集訓(xùn)隊作業(yè)part1topcode50題part

1、第一部分: TopCoder 題目泛做： : 說明50 道題, 并填寫每題題目大所有題目來自于TopCoder :關(guān)于TopCoderArena的使用可見SRM的序號, 可到ArenaPractiseRoomsSRM中尋找, SRM僅需做DivI 的分?jǐn)?shù)最高一題(LevelThree, 1000分)TopCoder Arena 僅接受面象語言Java/C+/C#/VB. 因此使用Pascal 的同學(xué)可以考慮學(xué)習(xí)使用C+, 或者也可以去TopCoder 主頁上測試數(shù)據(jù)進(jìn)行離線測試。測試數(shù)據(jù)的方法為：打開TopCoder 主頁AlgorithmMatch Archive選擇相應(yīng)的比賽選擇一個DIV

2、 I Leader(點ID 前面的黃色小圓點)進(jìn)入到Statics 之后選擇最下方相應(yīng)的/stat?c=problem 泛做表格狀態(tài)1，方向指向N。并往反方向進(jìn)行下一走K(K=4*108)步能取i1方向起ai 設(shè)數(shù)組 fi記錄兩個信息：1）到達(dá)i1 方向的最小步數(shù)；2）設(shè)數(shù)組ci表示從位置i1fi更新 fj(i=0 的最小非負(fù)整數(shù)tmp時間復(fù)雜度是O(1)算法總復(fù)雜度為狀態(tài)在 兩行，而且M=22，所以很容易聯(lián)想到狀態(tài)壓縮 DP。M+1 個格子覆蓋狀態(tài)為k 所用的最值得注意的是，k 最大為 223，如由于只有四種連通塊可用，它們對 k 值的影響是有限的，也就是說，很多 k 值次只需要枚舉出現(xiàn)過的

3、 k 值就可以，不k 216。算法總復(fù)雜度為狀態(tài)定義有趣數(shù)為：十進(jìn)制下，每一位（非首位）數(shù)字都比它前一位divisor(divisor=500) 整qi表示i 1 的十進(jìn)制數(shù)。有趣數(shù)可表示成 qa1 + qa2 + 500qi%divisor是循9q 出來。fijkij個 q組成的數(shù)余數(shù)為k的個數(shù)。轉(zhuǎn)移時需要1狀態(tài)有 n(2=n=50) 支球隊，0到n-1。每支球隊都有一個初始分4 場比賽1分0球隊最高是多少？4n個結(jié)果，必須保證贏的個數(shù)fijki支球隊，贏球隊0 的最高。轉(zhuǎn)移時，對每支球k 場匹配。注意：為使球隊0 靠前，規(guī)時間復(fù)雜度為O(n*8n*4n*43)5狀態(tài)4 7 組成的數(shù)為幸運(yùn)數(shù)

4、，能被幸運(yùn)數(shù)整除的數(shù)為近似幸運(yùn)數(shù)。問：a到b之間，1b的近似幸運(yùn)數(shù)1 a-1 的近似幸運(yùn)數(shù)個數(shù)。數(shù)倍數(shù)的幸運(yùn)數(shù)，共有 1000 多個。狀態(tài)按照下圖規(guī)律構(gòu)建f(x)示左點集前i 位匹配右點集狀態(tài)j 費(fèi)用。轉(zhuǎn)移時，枚舉左點集 i狀態(tài)N*N(N=18) 第 i 行字符C的個數(shù)為 Ai?，F(xiàn)可以將C往向干，要求使得第 i 列字狀態(tài)定義除數(shù)四元組a,b,c,d為存在某個數(shù)的所有約數(shù)%40,1,2,3枚舉四元組a,b,c,d，總共是 504O(1)狀態(tài)在 N*M 的矩陣要求每一行或每一列都不能有相同的數(shù)，問：字典序最小的填法？ r*c 的矩陣存在合法填法當(dāng)且僅當(dāng)任意 di都小于等于 min(r,c)。 N(

5、N=20)個點的無向圖，現(xiàn)要求添加連通塊，并且任意兩點之間最多只有兩條簡單路徑，問：有多少種不生 成樹個 數(shù)公式： nm2 m ai。n 是總點數(shù)，mb12*b22*bk2*(k-1)!/2。結(jié)合(b1 b2 bk) (b1 + b2 bk) (k1)!nmk1 m ai。根據(jù)乘法 k 的乘積和。進(jìn)而求出情況 3。 起來比較疼狀態(tài)花園里有一堵墻，現(xiàn)要用給出N(1N=40)條邊靠墻圍一塊矩形許把任意一條邊砍成兩段，問：矩形面積最大Sum 為是所有邊的總和。假設(shè)墻X 沒有包考慮墻的鄰邊Y 時，可轉(zhuǎn)換成X 狀態(tài)N(2=N=100) 個點，M(=50)條邊的有向圖，每條邊都有一個距Ace0走到點一條邊

6、是損毀不能走 e 問，情況下，Ace從點0 1 首先對于點 i，求出任意刪去連接它的邊后，情況下，到達(dá)終點1 的距然后從終點 1 出發(fā)做一次特殊的 dijstrai的最短路必須大于等di。10 的最狀態(tài)K（K=100）跳看作父節(jié)點，中兔子往左跳看作設(shè)數(shù)組fijk表示經(jīng)過i次跳躍當(dāng)前位置深度為 j，當(dāng)前位置與目標(biāo)位置 LCAk 的方案數(shù)。轉(zhuǎn)移只需要考100次跳躍，j的范圍也就只有 200。時間復(fù)雜度為狀態(tài)給定一幅 N(N,=50)地圖里有一個和一個出空和還有77 種顏色，可壓縮表示。fijvk當(dāng)前位置(i,j)安全顏色狀態(tài)為v，顏色為k 狀態(tài)下到達(dá)pi的機(jī)率是的?，F(xiàn)最多只能經(jīng)過一次的格子，問：根

7、據(jù)最優(yōu)狀態(tài)N(N=5000)個格子，終點在格子 N，有一顆 子，為1至d。每一次移動，用扔出一z，然后棋子向前移z步，假如超過了N，Alice的棋子所在的位置 x， Bob 棋子所在的位置y，Alice 開始，Alice 和 當(dāng)棋子到達(dá)N-d,N-1后，他每一次子都在N-d,N-1A獲勝概率為 A N-d-x 步就能保證棋子到達(dá)N-d,N-1BN-d-y 步。因AB N-d-min(x,y)就能保證兩者都在N-d,N-1，可用公式直接計算A 的獲勝概率。狀態(tài)給 定 一 幅 N*M 8 個。Alice 能對Alice 共有多少種不同的假如用二進(jìn)制表示行和列是否已經(jīng)被全變成黑色，那狀態(tài)將到達(dá) 24

8、0。仔細(xì)觀察可以發(fā)現(xiàn)，那些初始時不存在黑而不存在黑點的行和列只需要個fijrc表示初始存在黑點ij，和初始不存在rc 的狀態(tài)下方案 d(n,d=9)和一個原始串 s(s.size=50)， 定義合法s.size相等，任意連續(xù) n 個字符出現(xiàn)的不同字符小于等等于原始串 s 的合法字k(k=1018)小的合法字符串是什fiji 個字符已經(jīng)固nj的狀態(tài)能字符是可以任意取的，所以最后 n 個字少個字符。因此定義 n 個字符壓縮規(guī)則當(dāng)前新加字符在最后 n 個中沒有出現(xiàn)，則在j 末入1；2，當(dāng)前新加字符在s k 狀態(tài)給定一幅無向圖，有若干個點，總點數(shù)不100i 行上的點i-1i+1行存在邊n行會與1行存在

9、邊。問：該圖的n 為偶數(shù)，那圖10。那么把這一層單獨提取N=47 部分配AliceBob看。A和 兩人都把所有看AB的隊列A 的隊列空的情況，分配給 A的需要t時間看完，B看完第一部需要 tb1，假如 ttb1，則 A 隊列空了。B看完第二部需要時間tb1，假t+ta1=2 時，必定是每一行或是每一列以 XYXY 這種字符交替出現(xiàn)N或M1時特殊處理?，F(xiàn)只討N,M=2。最終答案是行的方案數(shù)+列的方案iXYXYk格子的方XYXY出現(xiàn)的，只要規(guī)定一2*2 的矩陣，就規(guī)定了這幅圖。最多狀態(tài)在一副 放至多 10 種不同的棋子，每種有若干顆，總棋子數(shù)=N*M。任意一行或一列只允許擺放相同種類的棋子。問：有

10、多少種不同的擺放方gkijk 種棋子恰好占據(jù)了 i 行 j 列的方案數(shù)。設(shè)數(shù)組fkij表示前k種棋子恰好占據(jù)了 i 行 j 列的方案數(shù)。通過數(shù)組 g 組合出來。狀態(tài)給定一幅N(N=14)N 個點的有根樹，問：圖中進(jìn)行求解。DP Fijk表示表示圖k，以點 j 為根的生成樹有多少狀態(tài)有N(N=50)只兔子算出兔子的最高以及最低得分?，F(xiàn)給定 x 和 y(x,y=N)，問：最終排x y 只兔子設(shè)數(shù)組Fijk表示兔子i 為選中的k 兔子的組合。為了方便轉(zhuǎn)總的時間復(fù)雜度為狀態(tài)給定一幅 N(N=50)個點的有向圖， 0同在任意一點都能到達(dá) 0。 反方向通過人數(shù)的上限?，F(xiàn)在圖上隨機(jī)分布 修改一些邊上的權(quán)值，

11、使得任何情況下，所有每一個點必須保證順時針和逆時針走到出口的人數(shù)和不小于 N。而且對于相鄰的人數(shù)是 Num，那么點 j 往同方向的必須不少于NumDP fij表ij 人順時針走到出口，逆時針有 N-j人的代價。DP轉(zhuǎn)移要稍微優(yōu)化一下。算法時間復(fù)雜度是O(N*M)狀態(tài)給 定 一 棵 N (N=200)的有根樹，最多可添加 K(K=100)條額外邊，問：從根出發(fā)遍歷樹上所有邊后回到2*k 個表示以點i 為根的里固定了j 個額外狀態(tài)有NK種子里某一種蘋果最多有 子的集合，然后這些箱子里選一個蘋果。問：每種蘋果被選中的概率fiji，蘋果j k 種蘋果的概率為N Sum_Apple fijNum / j

12、i=1 k in 重點在于如何求fij，Sum_Apple 最多500000i 都單獨求一次定義數(shù)組gj表示不包含箱子i 組成j 的概率，tj表示所有箱子組成蘋果總數(shù)為ji蘋果處理出所有箱子的 g 時間復(fù)雜度是狀態(tài)N 個人按某順序排現(xiàn) 給 定 限 定 時 間 T(T=222) ， 人 數(shù)N(N=18)以及排列的限制，問：有多少種排列T 時間里所有人都443222即，假如被兩個人卡住，則所需的當(dāng)前的不是未集合中最大的，但比已經(jīng)的最小的大，那么未中最大的人必定當(dāng)前的比已經(jīng)的最小 小，那么，比它大的的人只會示狀態(tài)，i 表示已的集合，j 表示排列。時間復(fù)雜度為O(N*2N)狀態(tài)一種數(shù)字加密方 法：把連

13、續(xù) X 個相同的 個長度=500 的經(jīng)過來若干個不相鄰的字符作為 Y，而且要求若干個不相鄰的字符作為 Y，而且要求Y不能相等。而這里的可選的Y 跟一次還原的X 有密切關(guān)系。DPFijk表示狀態(tài)，i表i個已經(jīng)進(jìn)行還原一次還原，j表示狀態(tài)經(jīng)典的路人關(guān)燈問題+特殊的二分圖限制條件。問：最小的花費(fèi)只有16 臺和16 個數(shù)，數(shù)據(jù)規(guī)模不大，考慮用壓縮 DP 進(jìn)行求解。DPFijk表示狀態(tài)，i表示當(dāng)前經(jīng)過的的區(qū)間的左端點；k是二進(jìn)制數(shù)，表示哪些數(shù)還沒打印；j表示當(dāng)前位置在左端點還是右端點。 Fijk記錄打印剩余的數(shù)需要還需要狀態(tài)有N(N=20)個已知M(M=4)個待定碼可選-1,0,134種情況，每種狀態(tài)現(xiàn)

14、有 重量 X，每一次都會用給定N(N=N)，L(x)x 張卡表需寫的個數(shù)的上限。答案必定符合 狀態(tài)有兩個點數(shù)不超過 50 的凸包，外凸含著內(nèi)凸包。隨機(jī)在外凸包上選一個點，找到凸經(jīng)過這兩點的直線穿過a 和凸包上的一條邊，求出該邊a 為最遠(yuǎn)點的點集區(qū)間。枚舉bab的中垂線，求出a b 點優(yōu)a 為光源，求內(nèi)凸包O(n3)。思路很清狀態(tài)平面上有N(N=50)個點，要求畫兩個互不相交的凸包覆蓋所有的點，問：兩個凸包面積較大值的最小值是多N2 條邊。枚舉狀態(tài)定義函數(shù) f(x)=x/m (x m 的倍數(shù))x+1m,n (m,n=106)，問：有多少個數(shù)經(jīng)過n次f函數(shù)后剛好第一次變成 1？g(x)x 次恰好第

15、一次1 有多少個。一個數(shù)經(jīng)過一步可變成兩個數(shù)，一個是 x-1，一個是 x*m。簡單推算 g(x)=g(x-1)*2。但這樣會出現(xiàn)一些不合法的情況。例如 1*m-(m-1)=1。 狀態(tài)Alice,Bob F 三人玩射擊，給出每個9 種，每一列 舉 每 種 結(jié) 果 對 scoreA,killedA,數(shù)最小可能是多少，最入絕對值都小于等于 121,2組出現(xiàn)的次XF 取勝的回合數(shù)。根據(jù) 1,2 組的次數(shù)，對 killedF F 取勝回合數(shù)X 是否合法。最時間復(fù)雜度為O(10002)狀態(tài)m(m=40)棵樹，能種在每棵樹要求相鄰的樹與它有一定距離，問：有DP Fijki 棵樹，j+1 塊緊連著的連接塊，j

16、 個間隔，m棵樹連成一塊連接塊需要占 后m+1個位置空格，那方案數(shù)就是狀態(tài)一幅上下無限延伸的 地 圖 由 N*M(N,M0mid需要變大，否則mid 需要變小。ai bj 匹配的費(fèi)用是-max(a*b,a+b)+mid*min(a*b,a+b)，求取 K 個匹配的最小費(fèi)用。spfa 求 狀態(tài)給定一幅 N(N=20)個點的無向圖，通過每現(xiàn)有 M(M=20)個晴天段，每次移動都要在晴天下。時光機(jī)能回到過去時刻，但花費(fèi)時間是過去時刻與當(dāng)前時刻的時間差，而且時光機(jī)啟動一次需額外花費(fèi)時間 T(T=109)，問：從 0到 N-1 所需的最小時AB，枚舉可能用KA到Bdijkstra作預(yù)處理，然后再用類似d

17、ijkstra 計算從關(guān)狀態(tài)N*M (N,M=100)的圖，里面有空地，有，現(xiàn)要在空地中選一些點組成一個凸型，問：有多少Fvijk1k2：v表示第幾行；i，j表示連續(xù)塊的左右端點；k1，k2 分別表示 算法總時間復(fù)雜度O(N*M2)狀態(tài)) 黑白矩陣?yán)?，每次選定一個格子使它與周圍 方）都取反色。初始全部格子都是黑色，每個格子只能點一次，問：列中涉及的元的個數(shù) k。最后答案為 狀態(tài)大樓有H 層， 0H-1N 座電梯， 0至N-1。電梯有初始的位置，并且它們移動時相對距離不變。電H/N 步，要求每一層都有電梯停留過。問：有多少種不同的初始分布 組合 ？ 把電梯初始位置看作遞增數(shù)組 a， b，b0=0

18、ai+bjFij表示連續(xù)塊大小大于 1，j 座電梯覆蓋 i 層的方案數(shù)；Gij表示連續(xù)塊大小等于 1，j 座電梯覆蓋 i 層的方案數(shù)；DD1個單位，方案數(shù)則是 a,b 數(shù)組的互補(bǔ)性質(zhì)，要求連續(xù)塊大小為 1a11b1必定等于 1 ，由此得出， Gij 實質(zhì)就是 最終答案就是要求出 FHN + FHH/N。H和N都非常大，但實際需 有 N=50 個字符串，任意兩個串 s1，s2Len(s1)2s2)2( 定義 Len(s)為字s 的長度)。問：從 1 串的最短路LCP長度LCP 長度的平方和就要最大。在此引入 LCPtrie 葉節(jié)點LCP長度平0 1 未必是相并不影響 LCP。那么可經(jīng)過交換一些點0 1 是相鄰的LCP給 非 負(fù) 整 數(shù)狀態(tài)K,A,B,lower,upper 和正整數(shù)N(所有數(shù)f(X,Y表示 1*K%N,2*K%N答案表示為 f(B,upper) - f(B,lower-1) - sqrt(X)段，每段 sqrt(X)sqrt(X)求的是0,Ysqrt(X)*K%N 第二段里0,Y 內(nèi)的數(shù)相對于第一段里之 后 同 理 。 時 間 復(fù) 雜 度 為狀態(tài)在平面內(nèi)，Alice 在 (Tx,Ty=800每一步她(badi,badi即邊長為 好到達(dá)(Tx,Ty的方案數(shù)？（badi10 的倍先忽略 bad（原地不動可看作一種 bad ）限制，考慮橫坐標(biāo)，設(shè) DP 數(shù)組 sum