page1 Simpson各種優(yōu)化主要是加速圖形與直線的求交過程復(fù)

Author:

BZOJa-TheR-PeriodsofWordso-ProfessorSzut-Tetriss-Theg-t

y 。復(fù)雜度nlogn搜索。精確覆蓋問題。dancinglinks n^2logn平衡樹(跳表)nlogn??len+tlogn使用STL中的rope。注意不要一個(gè)字符一個(gè)字符輸出，要 nlogn， 輸出復(fù)雜度len+tlogn。move可過。??nlogn^2n^2logn使用并查集,n^2α(n)dist:逐行掃描，每列上的點(diǎn)只有離這行最近的才有用。單調(diào)隊(duì)列，斜率優(yōu)化。復(fù)雜度n^2?xy，求出(xi+yi)/2和(xi-yi)/2的中位數(shù),分別作為(x+y)/2和(x-y)/2。但為了保證xy都是整數(shù)，11就行了，nlognO(n)V1、V2X1-V1-Y1、X2-V2-Y2均為一條

如圖，設(shè)X0,X1,...,Xn是當(dāng)前解中的一條鏈，Y0,Y1,..Ym是原樹的最長(zhǎng)鏈（m>nX0、，Xk鏈的中點(diǎn)?)2l-1條路徑使得覆蓋的點(diǎn)最多，n+llogn或O(n)。。x到葉子方向的最長(zhǎng)鏈，id[x]xx-id[x]路徑上的點(diǎn)標(biāo)為已，每次只收縮未點(diǎn)向下的最長(zhǎng)鏈。正確性的證明也很容易。n+l*lognO(n)。正確性證明比剛才的還要直接。用桶來葉鏈，就可以做到O(n)。L>1時(shí)應(yīng)該怎么辦呢？中的葉子節(jié)點(diǎn)全部刪除，得到樹T2……如此重復(fù)下去，直到第k次得到的樹Tk中只有1個(gè)或2L求最小值，最后再求一次和就可以了。j-The分別以凸包上每個(gè)為基準(zhǔn)點(diǎn)，對(duì)凸包作三角剖分。f[i][j][k]ij-k個(gè)三角S[i][j]i為基準(zhǔn)點(diǎn)，第j-k個(gè)三角形內(nèi)的點(diǎn)權(quán)和。按極角排序，O(m)s[i][?]。sO(m)f后就O(1)得到三角形內(nèi)的點(diǎn)權(quán)和了。最后枚舉三角形的三個(gè)頂點(diǎn)，O(1)得出點(diǎn)權(quán)和。復(fù)雜度n*mlogm+n^3/n*m+n^3k-?k-費(fèi)用流/KMt?yBZOJ1442：[Poi2006]Crystals?l的逆序插入字母樹中(注意空間問題，可使用塊狀鏈表/鏈表/mapBZOJ不卡空間)，枚舉rev(B)C的分C是回文串(Manacher判斷)且在字母樹中找到了rev(B),則更新答案。注意到當(dāng)分割點(diǎn)向右移動(dòng)時(shí)O(L)L*|Σ|Llog|Σ|Lsqrt(|Σ|)sn-記錄每個(gè)在i之后最早出現(xiàn)某個(gè)數(shù)字是在什么地方，然后枚舉所有可能的編碼，判斷否符合這段。當(dāng)某個(gè)編碼符合的數(shù)達(dá)到n時(shí)++ans。復(fù)雜度10^4*nn-?m-Toy?aPiggy設(shè)i的在j里，則j向i連一條邊。構(gòu)成的圖所有點(diǎn)的入度為1，出度任意。若連通塊中o-knightnkn*klogk單調(diào)隊(duì)列n*ks-二分答案，最大流。把每場(chǎng)比賽作為一個(gè)點(diǎn)，Smid21T1t-AJourneyto單調(diào)隊(duì)列。復(fù)雜度O(n)m-Fibonacci2：ifa[0]=1thena[11a-Tem相鄰兩個(gè)下標(biāo)的距離<=i+1j長(zhǎng)度覆蓋所有的充要條件。非減的，所以用個(gè)變量最大值即可。c-Specialnlogn^2(即x坐標(biāo)x)n^2。t-The掃描線，平衡樹DP。復(fù)雜度nlogna-Twou-Double-?i-?s-Mirror?1016:[JSOI2008]?ronmanRaceinnlogn^2angingtheoboticnlogn2913:[Poi1997]XORGatesk大的是幾：f(x,s)1-xs的數(shù)的個(gè)數(shù)。數(shù)位DP。先二分出答案的f判斷。1nk是第幾大的:f11018252627283032353943475156616798711122344556111224445533的兩個(gè)數(shù)可以歸k個(gè)“單獨(dú)值”k/2k個(gè)“單獨(dú)值”，會(huì)產(chǎn)生(k+1)/2個(gè)等差數(shù)列。線段樹的節(jié)點(diǎn)上記錄9個(gè)值：左右孩子l,r，左端值le，右端值re，左端單獨(dú)值的個(gè)數(shù)ld，右datadd。nlognjmask這個(gè)狀態(tài)的串有多少個(gè)，直接進(jìn)行DP就可以了，但是比較麻煩42的時(shí)候才要求輸出，于是可以dfs直接從DP終止?fàn)顟B(tài)回溯，每次從一個(gè)狀態(tài)拓展時(shí)，dfs注意到如果AB，BC顯然不會(huì)用AC...從上到下，從左到右考慮，那么每列最多一個(gè)是有用的人小DPnlogn。我們需要q，隊(duì)列中每個(gè)元素 i，以決策i為優(yōu)決策的位置的左端點(diǎn)l，右端點(diǎn)r。對(duì)于每個(gè)i，我們依次執(zhí)行以下三步操作：取隊(duì)頭元素為最優(yōu)決策，計(jì)算出f[i]將i從隊(duì)列的 i為最優(yōu)決策的區(qū)間，刪除隊(duì)尾元素(隊(duì)尾指針-1);若對(duì)于隊(duì)尾元素的右ii加入隊(duì)列。n^4，Ba2b2A方法得到的結(jié)果相同。顯然a1+b1=a2+b2f[a1,b1,a2]n^3lueMary二分答案，hashn^2logn。2.f[i,j,k,l]表示以A的(i,j)、B的(k,l)為右下角的最大邊長(zhǎng)lueMarynlogn線段樹nlognnlognlueMarylueMaryOpen]f[i,j]ij的情況下，所能滑的最大距離。f[i,j]f[i+1,j],],j]pre[j]j有多門課程！轉(zhuǎn)移方法：f[ij]轉(zhuǎn)移到f[i+L[kA[k]]L[k]、A[k]分別為當(dāng)天某個(gè)課程的Open] +1就nlognOpen]求出每條直線與圓的交點(diǎn)，排序后邊掃描邊樹狀數(shù)組。復(fù)雜度nlognJan]損壞Jan]f[i,j]jiiJan]徑上的最后一條邊上。問牛i在不遇到小的前提下從起點(diǎn)到達(dá)牛棚i的最短路徑。ShortestPathTreevpparent1號(hào)點(diǎn)到v的不經(jīng)過(p,v)的ShortestPathTree1v1號(hào)點(diǎn)先v，這條路徑上不能有邊(p,v)v的邊，后通過邊(u,v)v。uuv，1uShortestPathTreev走。1->uu)ShortestPathTree的葉子結(jié)點(diǎn)（深度最大，然后處理深度次大的點(diǎn)……重復(fù)此過程，直到根（1號(hào)點(diǎn)）處理完。葉子節(jié)點(diǎn)的處理方法，葉子節(jié)點(diǎn)不會(huì)出現(xiàn)情況二。對(duì)于葉子結(jié)點(diǎn)vv相鄰的點(diǎn)放在一個(gè)堆里（為什么用堆之后討論uudist[u]+w(u,v)。dist[u]1->u的最短路徑（不考慮是否經(jīng)過(p,v)1->v的答案。如果所要處理的節(jié)點(diǎn)v不是不是葉子節(jié)點(diǎn)，那么還有可能出現(xiàn)情況二。先類似葉子節(jié)點(diǎn)處理v的每個(gè)childu1->u的結(jié)果求出來。根據(jù)我們的處理順序，這一點(diǎn)能uuw(u,v)vw(u,v)uu的路徑，需要再走一步(u,v)v。還有，1->uv的descendant作為中間節(jié)點(diǎn)，這是不符合要求的答案，要從堆v中刪除。nlognnlogn^2。2.首先不考慮小，用spfa或堆優(yōu)化的dijkstra求出“最短路徑樹也就是通過這棵樹上uv開始，在最短路徑樹上不斷向各自的父親節(jié)點(diǎn)移動(dòng)這兩個(gè)點(diǎn)，vlen-dis[u(v)]更新ans[u(v)]，同時(shí)把這個(gè)點(diǎn)向上移動(dòng)到其父親節(jié)點(diǎn)，重復(fù)上述操作直到u=v。注意到如果僅僅這樣做，時(shí)間復(fù)雜度還是太高。由于我們已經(jīng)把環(huán)nlogn+nα(n)Feb]用堆。復(fù)雜度nlogn或nloglognFeb]StockFeb]RevamK(最多更新次數(shù))*k(期望為常數(shù))*m(用spfa)/Km+Knlogn(dijkstra+fibonacci堆)dijkstraHol]Cattle nlogn。Hol]TransmissionDP。f[i][j]ij0的情況下，有多少種可能的輸出f[n][k]=f[i][j]+=f[i+1][j+1]iff|j<A|&&|pos0[j]-i|<=df[i][j]+=f[i+1][j]iff|i-j<B|&&|pos1[i-j]-Hol]Holiday--1515*nlognMar]MoonDP。復(fù)雜度O(n)Mar]Cleaning每一步f[i]表示不度為i的最前面的數(shù)的位置。顯然i<=sqrt(n)。復(fù)雜度nsqrt(n)。ythonMar]Earthquake其中(x,y)key[x][y]的特殊點(diǎn)，key[x][y]>prev>=totisum{f[r][c][i][j]}j>=iDP。f[i][j]ij堆的答案。枚舉上一堆，前綴和。復(fù)雜度n^2*ksetnlognnlognO(n+W)Dec]TrickorTreatDP+環(huán)。復(fù)雜度O(n)Dec]SecretDec]Largest處理)n^3lognn^3Feb]Makingthenlognp[i]i結(jié)點(diǎn)對(duì)應(yīng)的線段的左端點(diǎn)。2i，ld[i+i]+rd[i+i+1]>=d是否成立，成立則找到答案；lognmlogn2.用平衡樹每段連續(xù)的空位。操作1：一段空位因?yàn)楹喜⒌拇螖?shù)不會(huì)多于的次數(shù)，所以復(fù)雜度nlognJan]nlogq+qlogq^2Jan] 從題目可以知道，草地的連接是一棵樹。樹形DPO(n)3f[p][0]=∑min{f[p.son][0..2]f[p][1]=∑min{f[p.son][0..1]]<=f[p.son][0]-f[p.son][