信息學(xué)-集訓(xùn)隊(duì)作業(yè)

IOI2011中國(guó)國(guó)家集訓(xùn)隊(duì)第二次作業(yè)第一部分:TopCoder題目泛做(截止日期：CTSC10天，具體待定：提交方式:通過(guò)考試OJ[說(shuō)明50道題,并填寫(xiě)每題題目大所有題目來(lái)自于TopCoder: 以下表格給出SRM的序號(hào),Arena→PractiseRooms→SRM中尋找,SRMDivI的分?jǐn)?shù)最高一題(LevelThree,1000分)TopCoderArena僅接受面象語(yǔ)言Java/C++/C#/VB.因此使用Pascal的同學(xué)可以考慮學(xué)習(xí)使用C++,或者也可以去TopCoder主頁(yè)上測(cè)試數(shù)據(jù)進(jìn)行離線測(cè)試。測(cè)選擇一個(gè)DIVILeader(點(diǎn)ID前面的黃色小圓點(diǎn))→進(jìn)入到Statics之后選擇最下方相應(yīng)的 ．[泛做表格．Mn個(gè)數(shù)，從左到右a1,a2剛開(kāi)始方向向右．每次可以前方向ab，那么得到的分?jǐn)?shù)就是a和b之間所有數(shù)的和（ab，跳現(xiàn)在最多可以跳k次，負(fù)的情況下，總分最p1,p2…pm，那么一定存在一種p1r[p2]p2，再跳若干次p2~r[p2]p序列．西，①跳的次數(shù)；②總分的目的1n1k很容易理解因?yàn)樽詈罂隙ㄊ窃谀硞€(gè)時(shí)間復(fù)雜度：O(n2logn*m每個(gè)格子的右下角，那最多只需要關(guān)心周?chē)?所以按照行優(yōu)先的順序?qū)Ω褡觨pt[x][y][mask]表示到達(dá)了(x,y)這個(gè)xy1x1行第y–2到第m個(gè)格子m+2個(gè)格子的mask，所需的最小方塊數(shù)．稱(chēng)(x–1,y–2)為格子(x,y)的白的1n,m驅(qū)格子時(shí)間復(fù)雜度：O(nm*m1maphashNDD值實(shí)在太大了，矩陣乘法在時(shí)間上i（即從右到左d[ia[i]a[i+1]d[Na[N]Nd[i]非負(fù)，并且d[i9嘗試dNNA=10i1a[i]N以推得：A=111...1d[i] p[i]=由于d[N]必須大于0，所以嘗試A的所有位的數(shù)字都減1，依然滿(mǎn)足所d的范圍都一樣了，都是[0,8]r少個(gè)N0，滿(mǎn)足數(shù)字從最到低位單調(diào)不降D1N1DA滿(mǎn)足下面兩個(gè)條件，就是符合題目條件的一個(gè)NN①p[i]d[i]p[N](modN②0d[i]8p[ip[i–1]*10+1pD的余數(shù)遲早會(huì)出現(xiàn)循環(huán)．所以我們將除以D余數(shù)相同的p[i]對(duì)應(yīng)的d[i]放C[i]Dipv[i][C[i]]sum[i]①sum[i]ip[N](mod②s0sum[i]opt[i][mod][s]id已經(jīng)全部確定，第①個(gè)條件里的余數(shù)為法．可以先將所有盒子放上1個(gè)蘋(píng)果yx1+x–1,x)C(y+x–1,y)，可以n個(gè)隊(duì)伍進(jìn)行足球同的球隊(duì)之間展開(kāi)，3現(xiàn)在每個(gè)隊(duì)4場(chǎng)比賽沒(méi)有進(jìn)行，也代表著還有2n場(chǎng)比n支隊(duì)伍目1支隊(duì)伍可能的最高名1n（輸?shù)拇螖?shù)，平的次數(shù)15種不同6場(chǎng)，2場(chǎng)，2場(chǎng)．從這個(gè)例平得最多的一個(gè)隊(duì)伍平了max場(chǎng)，那么sum是偶數(shù)2maxsum，證明可以用數(shù)學(xué)歸納法，根據(jù)maxmax-1的情首先輸?shù)膱?chǎng)數(shù)要等于贏的場(chǎng)數(shù)，那opt[i][delta][sum][max]表示前i個(gè)隊(duì)場(chǎng)數(shù)等于delta，平的總場(chǎng)數(shù)是sum，平得最多的隊(duì)伍平了max場(chǎng)，此時(shí)最少有多少個(gè)隊(duì)伍在1號(hào)隊(duì)伍之前．由于max5sum88，有一個(gè)無(wú)限大的表從上往下從1開(kāi)始對(duì)行格，填的是1開(kāi)始連續(xù)的整數(shù)，如下表S(i)代表以i所在的格子為右下角1所在的格子為左上角的矩形中所有數(shù)的f(i)代表以整數(shù)i所在的格子為右下角1所在的格子為左上角的矩形中所有數(shù)的f的和．N1,000,000,0071N了[1,i2]中的所有整數(shù)把所有在第i1234223433344444很容易求出N所在的根號(hào)N級(jí)別么根據(jù)F以及F的奇偶性，很N的坐標(biāo)(x,y)．先考慮較為簡(jiǎn)單的xy相等．由于F比較小，很容易想到一層一vvf就等于1v2v2v21)2v行1v1列的格子：v–1a1,a2…av-1，第v1行對(duì)應(yīng)列的格子是b1,b2bv-1，f(a1)=f(b1)+a1f(a2)=f(b2)+a1+a2f(av-1)=f(bv-1)+a1+a2+…+av-所以先好上一層最后一行f的和的值就可以得到f的和a1*(v–1)+a2*(v–2)+…+av-定是一個(gè)1或者-1的等差數(shù)列③第v列1行到第v–1行的格子：xy不相等．．O(N計(jì)算坐標(biāo)的時(shí)候32位整數(shù)和64位整n個(gè)結(jié)點(diǎn)的一共有n*m種數(shù)對(duì)，嘗試用動(dòng)opt[i][mask]表示前i個(gè)數(shù)對(duì)全部使用完（有的可能沒(méi)使用），樹(shù)邊的狀態(tài)是mask的最小費(fèi)用．opt[nm][2n-11]．的任務(wù)是對(duì)于一個(gè)數(shù)對(duì)(root,i)，找出所有root為根且和第i棵變幻樹(shù)同由于數(shù)據(jù)范圍比較小，可以用2n的時(shí)間枚舉該子樹(shù)是哪些結(jié)點(diǎn)組②結(jié)點(diǎn)總數(shù)等于第i棵變幻樹(shù)的結(jié)點(diǎn)總root的祖先．然后再去判斷這棵子樹(shù)是否和第i棵變幻樹(shù)同根樹(shù)m棵變幻樹(shù)（是有根樹(shù)i次變幻選擇一個(gè)(root,i)個(gè)變幻樹(shù)同構(gòu)的所有邊的狀態(tài)反1次11n1m1t[i]nx[i]和和值域都為整數(shù)集的f(x)，滿(mǎn)足：f(2f(x)x1)f(x)f(a)=t，根據(jù)題目，f(2t–a+1)=tC(*)b2ta1b帶入*f(2(tC1bt2Cf(a2C)=t+n|f(x[iy[i|其中C是給定的常1C根據(jù)上述得到的性質(zhì)可以做出2C的余數(shù)分類(lèi)，那么只要確定了某個(gè)同②(*)式將若干對(duì)同余類(lèi)溝通了起來(lái)，確先對(duì)所有f(x[i])–y[i]做一y[i]f(xx[ix[ixx[iy[i]，再自變量全部控制在了[0,2C)．2C，來(lái)計(jì)算a和b之間的邊權(quán)．這條邊xx[i]ab的目標(biāo)b+2kCk是整數(shù)．根據(jù)(*)式，得f(a*21ab2kCab1f(a)sumkC的形式．f(a)=sum+kC代入(*)f(b)=2sum–f(a)+C．這樣一來(lái)，ab這條邊對(duì)目標(biāo)函數(shù)的影響就能表示成|f(aConst[i|的形式，Const[i]看成數(shù)軸上的點(diǎn)f(a)距離中位數(shù)越近f(asum+kC，很容易找到最小的邊權(quán)．接下來(lái)的事情就是對(duì)這個(gè)左邊有CC個(gè)點(diǎn)的二分完全圖，求最優(yōu)完全匹配C比較小，可以用時(shí)間復(fù)雜度：O(C2*空間復(fù)雜度：O(C*第一次提交：Runtimeen*n設(shè)R[i]為第i行的總數(shù)向移動(dòng)到一個(gè)中．求最少得jR[j]兵用a[i][j]表示最后的局面ij列的格子上是否有士兵（0有，1沒(méi)有，在步數(shù)最少的前提下，要使a數(shù)組的字典序最?。?n行把0，代表有一個(gè)士兵要移動(dòng)；1n3)從②中所有點(diǎn)到它們各自所屬于的貢獻(xiàn)0，代表這個(gè)列最多有這么多點(diǎn)．接著對(duì)這個(gè)流網(wǎng)絡(luò)求著最小步數(shù)關(guān)于最小字典序的問(wèn)題先求更小的費(fèi)用0，那么這個(gè)格子改變費(fèi)用，相當(dāng)于一次“退流,3)（為了以后4a0,n，將它的質(zhì)因子按照4的余數(shù)34142n2k*M的M就是②③的乘積．k0a2=a1+a3并a0=(k–1)*a2a0,a20．如a0a2根據(jù)a1a3判斷是否存在MAp1n1*p2n2*…*p3n3．Bq1m1*q2m2*…*A表示的是②的乘積B表示的有yy 指數(shù)之和為偶數(shù)的情況一定大于等于指所以，a1x*y，a3x*y2 a1=a3y為偶數(shù)，Ma1a3a1要能夠被它們的差整除a1a3nn40a01a12a230aim個(gè)人，第一RMax(nm)．n*m陣中填入[1,R]中的整數(shù)，使得知道每一個(gè)數(shù)出現(xiàn)的次數(shù)比賽分成根據(jù)題目最小字典序的要求行一行處理．假設(shè)已經(jīng)處理完了前出現(xiàn)的次數(shù)加上nrow都大個(gè)人進(jìn)行了出字典序最小的．設(shè)Aij代表第一支隊(duì)伍ijnrowT，A11,A12A1m,A21,A22…A2m…An1,An2j列，那么將它們?cè)诙謭D中連邊．不會(huì)有相同的數(shù)字（匹配會(huì)有（連邊的條件1n,m（緊急數(shù)1并且滿(mǎn)足緊急數(shù)的需求n個(gè)結(jié)點(diǎn)的無(wú)向圖，沒(méi)有重邊．現(xiàn)簡(jiǎn)單路徑可達(dá)，至多有兩條簡(jiǎn)單路徑可達(dá)添加的方案數(shù)除以1,234,567,8911n先考慮加完邊之后的圖是一顆樹(shù)的dfs搜出整個(gè)圖的所有連通塊，用所塊，設(shè)它們的大小為ab，連接的方案ab種．最后方案數(shù)還要除以(-1)的階乘，因?yàn)橥豢脴?shù)會(huì)被重復(fù)計(jì)算用map<vector<int>>進(jìn)行化搜split(x)x分成若干個(gè)正整數(shù)的和的方案數(shù)，那么split(n)就是上述split(n)split很容易發(fā)現(xiàn)，split(n)=2n-1，是可以上述dp的值即可；否則枚舉設(shè)了k個(gè)連通塊它們的大小分s1,s2,s3…sk．①k1C(s1,2s11)種 2種不 i2．最后將環(huán)的連通塊合并成一個(gè)大連通塊和環(huán)為的連通塊形成樹(shù)的時(shí)間復(fù)雜度：O(2n*int的范圍了．ni根L[i]．n條木棍邊，其中有一條邊的最多只可以將一條木．最大面積看待，所以最多只有兩種情況先考慮墻的對(duì)邊完全由原來(lái)木棍組成的設(shè)所有總長(zhǎng)為tot，對(duì)于一個(gè)墻的長(zhǎng)度L墻的鄰邊的長(zhǎng)度就是(tot–L)/2,這個(gè)鄰邊的長(zhǎng)度一定可以需要考慮原來(lái)的木棍可以組成哪些，，，，2n的長(zhǎng)度SL(tot22L=tot時(shí)，面積取到最大值．所以要做的就是使L盡量接近tot/顯然不可能算出所有2n種組合，取而代之的是非常經(jīng)典的搜一半做tot/2L．當(dāng)墻的一條鄰邊完全由原來(lái)的tot4時(shí)間復(fù)雜度：O(n*xx最小，我將第一個(gè)的代n個(gè)結(jié)點(diǎn)的有向12圖中有一條邊<u,v>只有u的時(shí)候才知最優(yōu)策略情況12最1n從u到2號(hào)點(diǎn)的最短路徑為了情況，bad[u]u出u2的最短路徑最下一個(gè)點(diǎn)，問(wèn)題就又變成和u一樣的問(wèn)題于是設(shè)d[u]表示從1走到u，之前都還沒(méi)有被破壞的邊，之后走d[u]=max(bad[u],min(d[i]+g[u][i]))其中g(shù)[u][i]表示u到i有向邊的距離．時(shí)間復(fù)雜度：O(m*spfa(n坐標(biāo)分別為a<b<c，①ba的②bc的a可以跳到它關(guān)于b的對(duì)稱(chēng)點(diǎn)；c可以跳到它關(guān)于b的對(duì)稱(chēng)點(diǎn)．跳過(guò)b往左跳或者往右跳b–ac–b不等的可以讓a或者c往里b–a②一個(gè)結(jié)點(diǎn)做回溯操作就可以得到CommonAncestor)．由于要走恰好K步，所以先找出初始結(jié)點(diǎn)向上的K個(gè)祖先，然后從目LCA．如果沒(méi)有碰到，肯定無(wú)解．由于是滿(mǎn)二叉樹(shù)只需要關(guān)心兩個(gè)結(jié)點(diǎn)距離它們LCA的距離就可以LCAx，目標(biāo)結(jié)點(diǎn)距離LCAy的方案總數(shù)．①x0,②x0,y0，此時(shí)當(dāng)前結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)③x0,y0，此時(shí)兩個(gè)結(jié)點(diǎn)重合，要么結(jié)點(diǎn)到根的距離LCA是opt[K][0][0]初始狀態(tài)K次1,000,000,0071018abc0Kn*m每個(gè)格子可以是起對(duì)于任意一個(gè)中間狀態(tài)會(huì)知道opt[x][y][mask][D]，xy為當(dāng)表示已經(jīng)確定安全的顏色的集合；D則表示一個(gè)顏色(0..6)，如果當(dāng)前還沒(méi)有走到格子，D=7．整個(gè)狀態(tài)值表示轉(zhuǎn)移顯然是枚舉下一個(gè)格子(a,點(diǎn)、終點(diǎn)、還七種顏色中間的一每種顏色有率是的一個(gè)人要從終點(diǎn)哪些顏色是的不過(guò)一旦走到某個(gè)知安全性是否是的．這人最多只能走到①(a,b)為或色，概率為②(ab)③(a,)是空地或者是一個(gè)已經(jīng)確定安全的格子opabmaskD；④(a,)的顏色c安全的，轉(zhuǎn)移到opabmask∪cD]，轉(zhuǎn)移代價(jià)為該顏色安全的概率；第二種要當(dāng)沒(méi)有遇到過(guò)格子移到opabmaskc率．opt[x][y][mask][D就取以上幾種轉(zhuǎn)移中概率最大的一種，對(duì)應(yīng)了題目里的．bfs，再配合化搜索進(jìn)行dp．時(shí)間復(fù)雜度：O(nm*27*空間復(fù)雜度：O(nm*27*互相有些看似很像互相關(guān)聯(lián)的單向關(guān)聯(lián)也被STL格子，求略1n,m1*np1dn，也就是當(dāng)前這個(gè)人的位置在[n–dn]p的概率獲得勝利，也有(1–p)的概率回到這個(gè)區(qū)間，所以這1n號(hào)．有一個(gè)，[1,d]假設(shè)一個(gè)人當(dāng)前在a+b<na+a+b=n，勝a+b>n2nab，也就是像飛行棋一樣退回wwp1–p)2*w，w=1/(2–p)；②先手已經(jīng)勝利而后手還區(qū)x的人先，求對(duì)于第①種情況枚舉兩個(gè)人各ab步進(jìn)入了熱區(qū)，那么，w；對(duì)于第②種情況枚舉先手經(jīng)1dna+bopt[step][node]表示從起點(diǎn)走了nodelast，nodelast不能在受．其實(shí)last一定屬于續(xù)的區(qū)間，預(yù)處理出部分和就可以O(shè)(1)轉(zhuǎn)移，計(jì)算出了opt數(shù)組就可以知道要么是白的，k個(gè)黑格子，，opt[Rmask][Cmask][Rleft][Cleft表示Rmask/Cmask進(jìn)制表示）一般行/列的剩余個(gè)數(shù)是Cleft種選擇；Rleft種選擇；④一般行，一般列，有時(shí)間復(fù)雜度：O(nm*22k*空間復(fù)雜度：O(nm*它所在的行和列1n,m0kndansans，并且字典序sk個(gè)．S[c]ans+’a’,ans+’b’…成；②任意連續(xù)的個(gè)字符ansc之一s求長(zhǎng)度和它相等字典序大于等于它第i+1位的字符就應(yīng)該是最小的合法cS[c]kkk1dn1k1018nLen(s)s的合法字prefix，s①prefixv，0②prefixva[i]i+1位的字符（d很容易想到動(dòng)態(tài)規(guī)劃的方法，用opt[i][state]表示i位已確定n-位的狀態(tài)是statestate為同一個(gè)數(shù)字，比如aabcba，標(biāo)記為這樣每個(gè)狀態(tài)中110時(shí)間復(fù)雜度：O(Len*2n*空間復(fù)雜度：O(Len*prefixv相同有一棟n層的大樓，從1到ki．兩個(gè)站臺(tái)的樓層相鄰1n層能放超過(guò)一個(gè)哨兵10nnKiKi1n層相鄰的情有一個(gè)10．然而所有的站臺(tái)總數(shù)不站臺(tái)數(shù)10．于是就可以枚舉這層樓的站臺(tái)時(shí)間復(fù)雜度：O(210*ABn小到大排序，所以初始序列一2n種．沒(méi)有可看，他看就到此為止Ti，求有多少種初始序1n1Ti么時(shí)候會(huì)出現(xiàn)A看不完的情況：假設(shè)A看完了初始序列的，此時(shí)沒(méi)有可看了，那么要滿(mǎn)足TB[b1]-Sigma(TA[ai])>0A看完了初始序列和b1，沒(méi)看了，那么要滿(mǎn)足Sigma(TA[ai])+TA[b1]TB[b1]SumA看完自己初始序列中的初始序列的前i部所需的時(shí)間；TimeB[i]B看完自己的初始序列的i那么A看不完的情況，當(dāng)且僅SumTimeA[i]-TimeB[i+1]<0n個(gè)有一個(gè)很關(guān)鍵的發(fā)現(xiàn)：A看不完電個(gè)時(shí)刻A沒(méi)看了，那它的初始序列的肯定全部加到B的隊(duì)列末端，B肯所以分別計(jì)算出A看不完的初始序列個(gè)數(shù)以及B看不完的初始序列個(gè)數(shù)，用2n減去即可．由于時(shí)間的范圍很小嘗試用動(dòng)opt[i][Min][cur]表示前i個(gè)分配完畢，差值最小Min，當(dāng)前的差值是cur的方案總數(shù)．DpSum是在不斷變化的，因?yàn)椴恢揽偟腟um是Min設(shè)下一部A需要看La的時(shí)間BLb①該放到A的隊(duì)尾，那么+=La,cur+=②該放到B的隊(duì)尾，那么Sum沒(méi)有變化，MinMincur-Lb的最小值，cur+=La-Lb．效地避免無(wú)效狀態(tài)n*m干個(gè)連通塊．每種獨(dú)自為以是空地、城市是62種中的種．每種要么中給出．每種不城市是成對(duì)k某些（每必須一起去掉進(jìn)而聯(lián)想到動(dòng)態(tài)規(guī)劃的方法：用opt[x][mask]x2n1m1kmask所需要的最①合并以x為根的兩棵子樹(shù)x的父親yM=mask∪v，v是y（無(wú)需知道y是否在x上述兩個(gè)轉(zhuǎn)移其實(shí)對(duì)應(yīng)了一個(gè)optmax(opt[i][mask])城市的最小生成森林，轉(zhuǎn)移的時(shí)候枚舉mask的子集Mf[mask–M]，轉(zhuǎn)移ret[MM里，不時(shí)間復(fù)雜度：O(n2*空間復(fù)雜度：O(n2*n個(gè)向量的方向任意然后從第1個(gè)向量到第n個(gè)向量不斷將此時(shí)的和向量就稱(chēng)作該次調(diào)整的即向量(a,b,c)(-a-現(xiàn)在問(wèn)如何安排這n它們的和向量的模1nn*m每個(gè)格子都是要修改k個(gè)相鄰的格子同色（有一個(gè)非常關(guān)鍵的發(fā)現(xiàn)：要么每行是abab…ab1n,m0k于是先考慮行滿(mǎn)足上述性質(zhì)i行頭兩個(gè)格子aba、bc,dabcd這四種顏色兩前兩行的前兩個(gè)格子的顏色，再進(jìn)行計(jì)k種顏色的．iTi方案總數(shù)除以1,000,000,0091n,m1kTikTin*iopt[i][x][y]表示前i種顏色的車(chē)，已經(jīng)占據(jù)了x行y列并且沒(méi)有的方案總數(shù)n最后的答案就是opt[k][x][y]x0xopt[i][x][y]opt[i1][xa][yb]a1wC[x][a]C[y][b]f這其中C[a][b]表示組合數(shù)，a個(gè)數(shù)里b個(gè)的方案總數(shù)．f[T][a][b]則表示，T個(gè)車(chē)ab列的方案總數(shù)．這個(gè)問(wèn)題也要通過(guò)一個(gè)動(dòng)態(tài)規(guī)劃來(lái)T實(shí)際占據(jù)扣除aa][][[]wC[a][aC[']][b']a’b’amn．n個(gè)結(jié)點(diǎn)的樹(shù)還有一個(gè)n結(jié)點(diǎn)的一次．換句話說(shuō)，就n各結(jié)點(diǎn)的匹i號(hào)結(jié)點(diǎn)必須存在邊(p[i],p[j])．求有多少種滿(mǎn)1nmask）x為根的子樹(shù)，用掉了mask集合里的點(diǎn)的方案總數(shù)．但很x和它的孩子在圖中是否有邊是很有必要加上一維狀態(tài)refer，代表x它到圖中的結(jié)點(diǎn)refer．對(duì)于狀態(tài)opt[x][refer][S]需要將S–{x}分配給refer．所以要進(jìn)行dp：F[i][mask]i個(gè)孩子，用掉時(shí)候mask的子集irefer．轉(zhuǎn)移方程如下：F[i][mask]F[i1][maskS']*opt[Ch[i]][ireferx在圖里有邊連接xS，Sdpdp只需要做一次．n場(chǎng)有m個(gè)題目的考根據(jù)題目輸入里給的信息可計(jì)算出每只兔子的最高可能得分和x個(gè)兔子里任意選出y個(gè)．分?jǐn)?shù)越高越求在隨意安排“提交y個(gè)1n,m501yx可能得分得分，這y只兔子依然x名之內(nèi)．為了避免重復(fù)計(jì)算某些組合要里可以枚舉選的y只兔子里的最高以上select個(gè)兔子的組合總數(shù)．y++，這只兔子不能是枚舉的分?jǐn)?shù)線；xopt[n][i][y]．ilonglongn個(gè)結(jié)點(diǎn)的無(wú)經(jīng)過(guò)的人的所以整個(gè)圖是由若干個(gè)環(huán)以及若干橋組成的．這個(gè)題的整體思想就是將k（最糟糕的情況k個(gè)人1號(hào)結(jié)點(diǎn)，求最少添加多少的容量限制（dfs樹(shù)上的深度．對(duì)于一個(gè)橋邊(ifa[i])i→fa[i]的容量至少要為k，因?yàn)橛锌赡躪個(gè)人都i．k個(gè)人剛開(kāi)1號(hào)點(diǎn)？或者輸出i1號(hào)點(diǎn)．C2…CnkCi的時(shí)候，這時(shí)候1n1k0Capi，若干人往右到達(dá)i，分別稱(chēng)之為L(zhǎng)i單調(diào)不增，假設(shè)某Li<L(i+1)Ci的向左的容量必LiL(i+1)并且答案不變RiLi單調(diào)不增，Ridp想法：opt[i][last]C1,C2…CiL都已確定，其中Lilast時(shí)，最小的增加量．轉(zhuǎn)移的時(shí)候L(i-1)i-1個(gè)階段的后綴最小值O(1)轉(zhuǎn)移．n加k次，但捷徑只能走一次2x每條捷徑可以連接意兩個(gè)結(jié)點(diǎn)向的樹(shù)的次數(shù)，肯定是偶數(shù)次Xx內(nèi)捷徑端點(diǎn)個(gè)數(shù)奇偶性相同X1n0k經(jīng)不是很重要了關(guān)心的只是每個(gè)樹(shù)里有多少個(gè)捷徑的端點(diǎn)xtot最后的答案為max(opt[Root][2i]+iw)，其中0ikn個(gè)盒子，m種蘋(píng)i個(gè)盒子里有s[i][j]j種蘋(píng)果．nn=50的數(shù)據(jù)范圍顯然不能去枚舉所有可能的盒子組合（2n–1種．①第①種思路雖然是讀完題后最直觀比較所以考慮第種思路．對(duì)于每一個(gè)盒子只考慮盒子組組合關(guān)心的只是它的蘋(píng)果總數(shù)．所以每當(dāng)知道一個(gè)包含當(dāng)前考慮的子的盒子組合的重量就能計(jì)算在（不能不選能的盒子組合選的概率也是一樣，，由于所有盒子的重量是有限的，在n-1個(gè)盒子做一次背包，時(shí)間是承受不住于是在考慮包含第i個(gè)盒子的盒子組合的時(shí)候，枚舉n-1個(gè)盒子形成wtot，那此時(shí)的v[i]總數(shù)j案的貢獻(xiàn)就是tots[ij](2n1)w1n,m0s[i][j]n74222222=因?yàn)橐粋€(gè)乘客自己坐下來(lái)需要74他1次后面比他大的會(huì)被卡住兩次稱(chēng)[n-k+1,n]k位置①如果放的人在[n-k+1,n]里有順序站在飛機(jī)的i74秒否則如果他人或者向前移動(dòng)花的時(shí)間小于等于的初始序列總數(shù)（某位乘客1n0k中最大的，如果不是最大的②如果放的人在[n-k+1,n]沒(méi)有比他為i的人在的位置的．那么為了滿(mǎn)足[n-k+1,n]中所有的編jpos(jpos(x)jx．設(shè)g(x)=x–pos(x)，上述式子即g(x)g(j于是嘗試動(dòng)態(tài)規(guī)劃：用opt[mask][min]mask這個(gè)g的最小值是min時(shí)間復(fù)雜度：O(n2*空間復(fù)雜度：O(n*連續(xù)相同的數(shù)字用個(gè)如000100202就是兩次的數(shù)字串，求有500．opt[i]表示加密串前i個(gè)字符，對(duì)應(yīng)多少種不同的原串．轉(zhuǎn)移ji個(gè)字符0．?dāng)U展到二維之后依然可以用類(lèi)0，需要多記錄一些東西．opt[i][last][R]表示加密串前i個(gè)字，，，，原的是[i+1,j]這一段判斷a[i]a[j]a[i+1]0．①這一段原封不動(dòng)加上去，轉(zhuǎn)移到0．a(chǎn)[j]lasta[j]不為來(lái)說(shuō)：設(shè)[i+1,j-1]x，方案移的前提是有夠用的數(shù)字并且a[j]不等于last，特別要注意如果a[j]0，那么R必須非0，否則就產(chǎn)生了前導(dǎo)0．轉(zhuǎn)移到有n個(gè)，在一n個(gè)不同的位置．每個(gè)始數(shù)字，你要打印出n只能打恰好一個(gè)數(shù)k號(hào)打印過(guò)數(shù)字，你可以讓它的時(shí)間為該意時(shí)刻打印過(guò)數(shù)字的形成了一個(gè)opt[L][R][mask][To]，當(dāng)前打印過(guò)數(shù)字的的區(qū)間是[L,R],mask代表打Todp的定義有一點(diǎn)含糊：到底是1n子結(jié)構(gòu)dp是暫時(shí)行不通的．是走完除了[LR]所需要的最少時(shí)間，這max(當(dāng)前小時(shí)間)．由于根據(jù)L以及mask1的個(gè)數(shù)，RR這一維．時(shí)間復(fù)雜度：O(n2*2n空間復(fù)雜度：O(n*n個(gè)標(biāo)明重量的砝碼，m個(gè)沒(méi)有標(biāo)明重量的砝碼，但是輸入都會(huì)給你這n+m個(gè)砝的重量都應(yīng)該是[1,砝碼組合，天平會(huì)告知道，m個(gè)不確定的1n1m的砝碼所組成的所有砝碼組合在天平上-1，放10．對(duì)于任意的重量和稱(chēng)之為該組合的閾值．更顯然的，x一共有3x種砝碼然后枚舉未確定的砝碼的所有如果大于它的閾值中最小的小于它的閾值中最大知道這個(gè)未確定的砝碼組合的閾值范圍了．，，現(xiàn)在的問(wèn)題就是對(duì)于一個(gè)未確定砝碼組合合里的大于它的最小閾值以及小于它的最大閾值顯然是時(shí)間不允許然后對(duì)于每個(gè)未確定的砝碼枚舉一個(gè)重量變化值（經(jīng)試驗(yàn)±5即可，O(3m3n2log[3n22n比10頭羊，重量分別為3233的時(shí)候就不可二分是不行的，嘗試枚舉答案．設(shè)sum為所有羊的重量和，那么容量至少為sum/m（整除．從這個(gè)容vsum/mv1肯定是一個(gè)可行的解個(gè)回合所運(yùn)載的羊的重量和肯定大于m+2次．下面要解決的問(wèn)題就是給定船的容量，看這個(gè)容量能否將所有羊運(yùn)完頭羊有一個(gè)重量個(gè)固定的未知的容量船可以來(lái)回最多a岸中的最重的一頭a羊了或者船裝不下bm個(gè)回合內(nèi)b岸．1n,m,w．．預(yù)處理出小于等于i的最大的羊是2000，可以直接確定了．ok[i]表示當(dāng)前狀態(tài)，運(yùn)走了）i,那么下一個(gè)要上船的羊就是ok[i]ok[i]-1合并，用路徑C(x,0)1C(x,i)個(gè)數(shù)字出i張卡片里．那最多能寫(xiě)多少個(gè)數(shù)字就是有C(x,x)xC(x,x-1)x-1張卡片里….L個(gè)數(shù)字，最R個(gè)數(shù)字，那么[LR]中的任意一個(gè)都Min(x)MxMax(x)Mx則是單調(diào)遞增的，從這一點(diǎn)看似乎m1~n間不同所出現(xiàn)的卡片集合2n1m可以用二分答案．但要Max(x)也但很快就能發(fā)現(xiàn)：n,mn,可以保證mn2，所以Max(x)nxMin(x)n/2Max的不等號(hào)已經(jīng)成立了，這x了．MxM個(gè)數(shù)大于M那一定可以從數(shù)字的那M個(gè)數(shù)字．時(shí)間復(fù)雜度：O(log給定兩個(gè)多邊形a和b，an個(gè)點(diǎn)，b有ma包含b．現(xiàn)在要在a的邊上任選一個(gè)點(diǎn)，找到在①a邊上的一些a上的所v，那第一步要做的，就是看哪些點(diǎn)和ｖb有交集．做法是求出v和凸多邊形ba的交點(diǎn)，應(yīng)的極角范圍a上的點(diǎn)，和vb有交集．“某段a的邊．處于這個(gè)極角范圍內(nèi)的一個(gè)點(diǎn)（等概率任意選擇一b有交集a3n,mv的點(diǎn)所形成的線段總長(zhǎng)是枚舉一個(gè)和v競(jìng)爭(zhēng)的點(diǎn)u，要去點(diǎn)和ul的同一側(cè)u對(duì)于v來(lái)說(shuō)，lv就沒(méi)有用了，u完全可以替代它；③uv分居直線的兩側(cè)，uvluv．uv之間的距離，后，還要除以a的周長(zhǎng)．n個(gè)不同的點(diǎn)，現(xiàn)在要把這n凸包，這兩個(gè)凸包不能有交集，并且面積1n肯定能找到一條直線，將兩個(gè)凸包分隔果將直線上的點(diǎn)x排序的就屬于另外一個(gè)點(diǎn)集．它們屬于直線確定了點(diǎn)集之后只需用高效的n1時(shí)間復(fù)雜度：O(n4lognm．有一個(gè)BB[0]x,B[iB[i-1]m，否則B[i]=B[i-1]+g(x)B數(shù)列x的時(shí)候，最小的下標(biāo)k滿(mǎn)足xg(x如果從1出發(fā)，每次的B[i-1]就B[i]m，要么是比如根結(jié)點(diǎn)只能m；或者某個(gè)時(shí)候該2，那它就不能減一；又或者某個(gè)時(shí)刻，該結(jié)點(diǎn)的數(shù)字除以m余數(shù)是1，那它減一得到的將是一個(gè)m的倍g(xnx總個(gè)數(shù)（0層．i層的結(jié)點(diǎn)總數(shù)f[0]=f[1]=f[i-1]*im，會(huì)出現(xiàn)1=f[i-1]*i=m+1，仍然是沒(méi)有異常；1mm的倍數(shù)，這也就等于往上數(shù)第m+1層的結(jié)點(diǎn)總數(shù)，都是通過(guò)它們乘以m得到的，于是f[i]=f[i-1]*2－f[i-m-1]．有一個(gè)，John和Brus邀請(qǐng)到了他們的FriendJohnBrus9①FriendFriend②Brus一輪大家可以③John相，如果某個(gè)④John錯(cuò)rus，然后被Friend殺刻某個(gè)人被了⑤BrusJohnFriend⑥FriendJohn,Brus他不能再被也⑦FriendBrusJohn能再，并且下⑧BrusFriend輪．如果某一的人了，該輪然后想將killedB,killedJ每一個(gè)隊(duì)友扣killedF用①~⑨表示出來(lái)分，一個(gè)對(duì)手killedB=killedJ=killedF=分以及被殺死的次數(shù)，求進(jìn)行的數(shù)的最大值和最小1000score10000killed1000所以確定了⑧和⑨就可以知道以枚舉它們Friend贏的輪數(shù)d的數(shù)d個(gè)位置可以n棵樹(shù)，每r[i]，照從左到右將樹(shù)的寫(xiě)下，這是一個(gè)nn要滿(mǎn)足max(r[i],x,y的距離法除以1d1n1r[i]的種樹(shù)方案可不可以一起計(jì)算呢？答案是肯定的這n棵樹(shù)按照這個(gè)排列dis，那么還剩d-dis-1個(gè)位置沒(méi)有放．這個(gè)排列對(duì)應(yīng)的方案數(shù)其實(shí)可以把相鄰兩棵樹(shù)看個(gè)區(qū)間要把這d-dis-1個(gè)位置分給這n+1．f[i][tot]表示將tot個(gè)位置分給i個(gè)f[i][tot]f[i1][j這個(gè)方程很類(lèi)似組合數(shù)，可以轉(zhuǎn)移：f[i][tot]=f[i-1][tot]+f[i-1][tot-1]．上述問(wèn)題一解決剩下來(lái)需要dis．對(duì)于這類(lèi)和排列有關(guān)的一般使opt[i][j][dis]i棵樹(shù)，i-1個(gè)個(gè)狀態(tài)表示里，j這一維是精華，它很好轉(zhuǎn)移的時(shí)候嘗試第i+1①這棵樹(shù)和前面的兩棵樹(shù)確定兩個(gè)j種方法；②這棵樹(shù)和前面的一棵樹(shù)確定一個(gè)間隔，那連上頭尾，一共有(j+1)*2種方j(luò)+2種方法．最后從頭到尾最小距離為dis的排列opt[n][0][dis]．距離為它們r(jià)中的較大值 ，，rdp類(lèi)似的題目ceoi2010day2的時(shí)間復(fù)雜度：O(nd空間復(fù)雜度：O(nd0的迷宮部分：先保證r1r2，如果個(gè)點(diǎn)的橫坐標(biāo)范圍落在[0,n-1]r1(r1%nn)%nr2可以根據(jù)原來(lái)的距離確定．徑有可能繞的很遠(yuǎn)，繞出這個(gè)單位迷宮．所以bfs的時(shí)候，要將整個(gè)地圖k個(gè)(kr2/n)單位迷宮，我個(gè)單位迷宮的頂端再到第三個(gè)單位迷宮的頂端……最后走到最后一個(gè)單位迷宮用opt[i][j]表示走到第i個(gè)單位迷宮的頂j列的最短路徑，那么：opt[i][j]Min(opt[i1][k]g[k][g[k][j]表示從單位迷宮的(0,k)度無(wú)限，第i行第,i的范圍是所有整數(shù)而j的范圍是[0,w-nw的是橫坐標(biāo)范圍在不停地所得要么是，要么可以行走的可能有一個(gè)傳送器．每一行傳送器，要么有傳送器可以互相傳現(xiàn)在詢(xún)問(wèn)兩個(gè)點(diǎn)(r1,c1r2,c2)1n,w1015r1,r2．們要嘗試用矩陣乘法優(yōu)化這又不是以參見(jiàn)08年集訓(xùn)隊(duì)同學(xué)的時(shí)間復(fù)雜度：O(bfsw3logR空間復(fù)雜度：O(bfs有一個(gè)判斷是否有解的地方，粗心將>=0寫(xiě)成了>0．將所有單位迷宮里的點(diǎn)都作為了一bfs，其實(shí)沒(méi)必要，起點(diǎn)只0c1,c2的分?jǐn)?shù)－的分?jǐn)?shù)×ans=0．kA[i]=a[ib[iB[ia[i]*b[i]．k])n個(gè)[1,100]k須分屬于兩個(gè)數(shù)組kab的分?jǐn)?shù)加上的分?jǐn)?shù)加上的得分除以的分最大化1n分完全圖k條邊的最大權(quán)匹配．也可以將源拆點(diǎn)，設(shè)置出源的流量k，時(shí)間復(fù)雜度：O(Mincostflow(nn2*N個(gè)點(diǎn)的無(wú)向只能在陽(yáng)光明媚的時(shí)[Li,Ri]．一次出行，a到時(shí)b完全包含了區(qū)間[a,個(gè)比當(dāng)前時(shí)刻小的非負(fù)時(shí)刻x，t+x的時(shí)間（t是一個(gè)常數(shù)．使01N二元組(pos,time)pos位置，time的最小耗時(shí)．先用floyd預(yù)處理出任意點(diǎn)之間x①Li;③Lid[x][y]Li+d[x][y④Rid[x][y]Rid[x][y4．但光有pos和time也是不行的，我open01數(shù)字，代表此時(shí)不是具體時(shí)刻pos點(diǎn)有關(guān)的①postime0postime+1,N,m20,T②postime1postime-1,1，t，代表開(kāi)始使用時(shí)光機(jī)．0，代表停止使用時(shí)光機(jī)．,N*M．DPopt[i][p][q][st][en]表示第i行選了st到en，aibipq段的時(shí)候的方案總數(shù)，其中0pq1，這里第0ai處于不升狀態(tài)、bi處1段類(lèi)似．此時(shí)也要時(shí)刻保證狀態(tài)的，也就是第i行st到en列是否有．a(chǎn)i,bi處p1a[i-1]a[i]一定要嚴(yán)格單調(diào)增，也是續(xù)的區(qū)有些格子有．在要選出通（4-連通） 1N,Mp=q=0．109+7，導(dǎo)致越界．N*MNM個(gè)未知數(shù)，NM個(gè)方程的方程組，而O(n3m3)，不能在時(shí)限內(nèi)出解．5枚舉第一行的開(kāi)關(guān)的使用狀態(tài)，那么接下來(lái)所有的開(kāi)關(guān)的使用狀態(tài)就確考慮(3,2)，它可以利用(1,1)這個(gè)開(kāi)關(guān)，為了使(1,1)這盞燈亮，