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

MIPTSolutionByMoony本解題報(bào)告是我在參考了前幾屆國(guó)家集訓(xùn)隊(duì)選手的報(bào)告后，在許多大牛的幫助下寫(xiě)的（在這里特別感謝劉汝佳前輩有內(nèi)容可能會(huì)和他人的相似但我相信站在巨人們的肩膀上能看得更遠(yuǎn)本題解不但對(duì)很多前輩報(bào)告能讓你或多或少學(xué)到一些東西。本題解中有不少不明顯的link，大家。S+Sumof不需要高精度的A+B問(wèn)一道有一定難度的A+B問(wèn)題Autumnisa+Maxof求n大家可以研究一下求n個(gè)數(shù)的第k大值的各種算法Θ(netc.）+Set求兩個(gè)集合A與B排序+掃+Contest給定一張有向圖，對(duì)于兩個(gè)不同結(jié)點(diǎn)i和j，邊(i,j)和邊(j,i)存在且僅存在一Hamilton鏈。SWC(SearchWithoutClothingcanbealsocalledNude否則必然存在一個(gè)在當(dāng)前鏈L上的點(diǎn)Li，使得邊(Li和(this,Li+1)+每個(gè)物品有2個(gè)值mi與si，如果有si<sj則mi<mj每個(gè)物品i，它前面物品的m的和不超過(guò)它自己的si，即∑j<imjsi，則稱這給出n個(gè)物品，求最多可以取出其中幾（n≤100000，mi,當(dāng)年題目中的nO(n2)的動(dòng)態(tài)規(guī)劃算法AC，后來(lái)ELJudge改了數(shù)據(jù)，就只能用貪心了。一道類似的貪心題：CTSC2007pendant+descendingatree葉結(jié)點(diǎn) W。求∑W*(1)Di， 中Di表示i的深度+Three0至n3個(gè)非負(fù)整數(shù)枚舉可以AC，復(fù)雜度是O(√n3)當(dāng)然，你也可以把這道題想象成求生成函數(shù)+x4+x9+x16+x25+…)3展開(kāi)后x0x1,…,xn中系數(shù)為0的項(xiàng)的+Space求n*m*d此類矩陣問(wèn)題大都需要先預(yù)處理一個(gè)sumsum[a][b][c]表示∑i≤a,j≤b,k≤cmati,j,k，這樣，在后面的運(yùn)算復(fù)雜度是O(n5)+棧（只用記+Fibonacci求Fibonacci數(shù)列第n項(xiàng)學(xué)習(xí)用矩陣乘法O(logn)求Fibonacci數(shù)列第n項(xiàng)的算（很多遞推都可以用矩陣乘法加速）+NewYear求二分圖G(X,Y,E)的最大匹配匈牙利算法直接AC學(xué)習(xí)最優(yōu)匹配的KMUSACO2004MarchGreen有另一道很BTMooUniversityEmergencyPizzaOrder，直接用匈牙利算法+Brackets法，不同種括號(hào)不能交叉。棧+Correct相當(dāng)于給定一個(gè)有向圖G，判斷是否是一個(gè)DAG。（|G|<=1000略+有n個(gè)有序三元組(xi,yi,zi)，有xi≤xi≥xj,yi≥yj,zi≥zj。求最小鏈覆蓋這道題就是對(duì)于給定的二元組(x1y1x2y2xnM1:(x11,y11),(x12,y12),…,(x1m,M2:(x21,y21),(x22,y22),…,(x2m,…Mk:(xk1,yk1),(xk2,yk2),…,(xkm,對(duì)于任意的i,j,p(p>1)都 且yij≤yij，并且使- p- 盡量小（即最小分割O(nlogn)O(nlogn)的LIS得解?；氐紹oxes，卻無(wú)法用O(nlogn)的方法解決。其實(shí)有一O(n2)。O(n2)更快的算法呢？劉汝佳前輩堅(jiān)定地告訴有！2003TCODivisionI,LevelThreeNestable就是這個(gè)問(wèn)題的加強(qiáng)版（題意略有改動(dòng)，盒子i可以包含j當(dāng)且僅當(dāng)xi>xjyi>yj,zi>zj，求的直接是盒子套盒子能組成的最長(zhǎng)鏈），N高達(dá)用動(dòng)態(tài)規(guī)劃f[j]=max{f[i]+1|i<j且box[i]可被box[j]包要取得更快的算法需要用平衡樹(shù)等高級(jí)數(shù)據(jù)結(jié)構(gòu)來(lái)加速。逐個(gè)按照xi遞增的順序考慮盒子，在運(yùn)算過(guò)程中需要一些集合T[]T[i]這個(gè)集合內(nèi)的元素都滿足：以其為最下標(biāo)最大的非空集合T[i]，那么i就是所求答案。當(dāng)考慮到某個(gè)盒子B的時(shí)候，可以使用二分查找，找出存在可被k包含盒子的所有集合（一定是從開(kāi)頭開(kāi)始連續(xù)的）的最后一個(gè)集合T[i]，并在T[i+1]中B。但是有一個(gè)很嚴(yán)重的問(wèn)題——如何快速判斷一個(gè)集合中是否存在可以被B包含的盒由于一個(gè)集合中的所有盒子都不互相包含，所以當(dāng)它們按照優(yōu)先yzyz是不增的。那么在這樣的集合中，只用在O(lon的時(shí)間內(nèi)找到第一個(gè)z小于Bzy是由也小于By就可以知道是否存在了。當(dāng)然，這一切順序都要在的時(shí)候。分析到這里，得到了理論復(fù)雜度很好的算法2能取得很好的效果。+給定K求一個(gè)長(zhǎng)度為N的句子，使其包含的所大小為M。最后的答案可以通過(guò)DP得出：以串的長(zhǎng)度為階段，為了保證表示長(zhǎng)為Ns結(jié)尾的所有滿足要求的字符串中最大值得注意的是s的取值，如果以一切字符串為取值范圍，顯然復(fù)雜度太高了。但可以只動(dòng)態(tài)規(guī)劃中的“當(dāng)前串”中的于是s的取值范圍即為所有模式串的所有前綴組成的集合。，，，，枚舉一個(gè)字符集中的字符c加在ss’s+c，并求出新的s”s”s’s”s”c]完成。然后就可以得到通過(guò)opt(N,s)擴(kuò)展到opt(N+1,s”)的恐懼值：為opt(N,s)+weight(s”)weight(s”)表示所有是s”后綴的模式串的恐懼值總和。weight(s”)數(shù)組也可以總數(shù)*字符集總數(shù)=N*K*模式串長(zhǎng)*M可以將將長(zhǎng)度超過(guò)N的單詞在一開(kāi)始就刪除，于是模式串最長(zhǎng)為N，所以動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度是O(N2MK)的。但仍一個(gè)問(wèn)題是如何高效的求出next數(shù)組和weight和O(N2K2)的（不考慮字符串比較時(shí)間，否則還要乘一個(gè)N因度。更高效的算法是建立一個(gè)自（可以參見(jiàn)Maigo2006集訓(xùn)隊(duì)《Trie圖的構(gòu)建、活用與改進(jìn)》），在O(NMK)的時(shí)間內(nèi)得到next和weight數(shù)組；或用KMP算法在O(NK2)+One在[0100]*[0,100]的矩形內(nèi)找一個(gè)n個(gè)給定點(diǎn)都不在矩形內(nèi)（可以在邊WC2002奶牛浴場(chǎng)也和此題一樣，是求最大空心子矩形。做這類問(wèn)題有兩種不同的方法，它們的復(fù)雜度分別是O(LW)和O(n2)O(LW)USACOARectangularBarn的解題報(bào)告。根據(jù)這道題的數(shù)據(jù)規(guī)模，顯然O(n2)的方法更優(yōu)它的四邊都不能再擴(kuò)展。將所有的點(diǎn)按照x坐標(biāo)從左到右排序，對(duì)于每個(gè)點(diǎn)ii，而右邊緊貼某個(gè)在i右側(cè)的點(diǎn)j的極大矩形（設(shè)updown記錄矩形的上下邊，在枚舉j的時(shí)候可以u(píng)p和down），更新最優(yōu)解。另外+Two在[0,Mx]*[0,My]的矩形內(nèi)找二個(gè)面積和最大的平行坐標(biāo)軸的矩形，使得n（n≤100，Mx,015Onerectangle所解決的問(wèn)題?？倳r(shí)間復(fù)雜度為O(n3)解法二：（周源前輩的題解若要求一個(gè)指定的有點(diǎn)的矩形中的最大空矩形。首先枚N加入點(diǎn)，相當(dāng)于在一個(gè)垂直的區(qū)間中加入一個(gè)點(diǎn)，但順序這些區(qū)間，即使采用線段樹(shù)，每次復(fù)雜度也O(log2N)的，而且算法可能至每次操作O(N)。但反向作就不存在這些問(wèn)題了：先將所有點(diǎn)從上到下建一雙鏈，然后從右到左依次刪去點(diǎn)并雙鏈，而每次只得到一個(gè)新的更大的區(qū)間，因此只需要一個(gè)最大值即可這樣用O(N2)的時(shí)間算出了任意從左到右某個(gè)區(qū)間中最后，最樸素的方法也能在O(N)的時(shí)間內(nèi)得到最優(yōu)解同理水平分界線的情況最后算法的時(shí)間復(fù)雜度為O(N2)，空間上稍微大一些，也需O(N2)，但應(yīng)該可以用一些數(shù)據(jù)結(jié)構(gòu)降低這個(gè)級(jí)別給出N行command這是MIPT多道表達(dá)式處理題中的一道，如果你將所有這些definition或者identifier，下面做完了，那么在表達(dá)式處理方面你就成仙得道了Alpha::=a-zA-如果得到的command是definition，那么將其identifiernumeric::=0-expression剝離并記錄。如果command是identifiercommand::=identifier|definit計(jì)算其記錄expression的值并輸出，同時(shí)判斷是否errordefinition::=identifier':='+Arithmeticaidentifier::=alpha最關(guān)鍵的部分是需要多次調(diào)用的計(jì)算expression的值。當(dāng)expression::='('expresson')'偷懶的方法是O(n2)的遞歸，每次找出優(yōu)先級(jí)最低的運(yùn)算符integer_number|identifier|expression('+'表達(dá)式分離成兩部分然后遞歸計(jì)算O(n)的表達(dá)式處理'*'|'-')一次處理expression每個(gè)元素，如果是數(shù)值（或已知數(shù)值integer_number::='-'?符號(hào)）如果一行command是identifier，棧的尾元素計(jì)算（將數(shù)值棧尾兩個(gè)數(shù)和為一個(gè)），處理，括號(hào)的優(yōu)先級(jí)也要設(shè)定，具體的實(shí)現(xiàn)可以參（N<100，command都不超過(guò)個(gè)字符有的同學(xué)可以去看看表達(dá)式樹(shù)的理論+Whatisthe0小于1，你可以詢問(wèn)“這個(gè)數(shù)是否小于r”。給出N，問(wèn)情況下，最少要問(wèn)2~N數(shù)的個(gè)數(shù)你可以枚舉+來(lái)求，最好的方法是2~N每個(gè)數(shù)的歐拉函數(shù)的和（不懂歐拉函數(shù)？請(qǐng)用Baidu和思093Whatisthenumber(Part+給出一個(gè)N*N的棋盤(pán)（N為奇數(shù)），以獲勝則輸出1；如果當(dāng)前一方無(wú)論如+Islandofstraight在平面上，給定n樹(shù)，樹(shù)邊一定是直線段，且不能穿過(guò)給定的m條線段。（n,愛(ài)的voronoi和DT~~+（+expressionI給定一個(gè)文本串A，一個(gè)含*的（但不中*，使得A=B。（|A||B|1000，答案保證不超過(guò)用F[i,j]表示A[1..i]匹配B[1..j]的方案數(shù)，下面是遞推F[i-1,j]+F[i,j-1]F[i,j]{F[i-1,j-1]0+Wayamong給出一些線段和兩個(gè)點(diǎn)AB，判斷是“房間”，如果兩個(gè)房間不同，則輸出NO，否則輸出YES，判判斷A是否能到B?？嗨稼は氤鰜?lái)的錯(cuò)算法（截至200712月尚可以AC），請(qǐng)?jiān)赗P充足的情況下使用：建立這樣一張圖——頂點(diǎn)是A和B以及各線段頂點(diǎn)，邊是圖上能從AB的路徑那么曲線存在。很明顯此算法本題與Sgu的一道GtOut很相似，可以首先將所有的交點(diǎn)和頂點(diǎn)列出來(lái)，接著將直接有邊相連的點(diǎn)之間連一條邊，在這（fstree上添加邊的辦法，依次檢查ABYES。此算法可能是最好實(shí)現(xiàn)的正確算法，只4)。1.枚舉圖中所有圈是的復(fù)雜度是階乘級(jí)別的（情況是完全圖——圈數(shù)是N!）。利用DFSTree得到的圈是DFSTree（u是v的祖先v是w的祖先Root…-u-a-v-b-(v,bwv)，(uav,bwu)。少了一個(gè)圈：(u,a,v,w,u)，發(fā)現(xiàn)是上面兩個(gè)圈的一個(gè)/---\/---|A|B\---/\---點(diǎn)即不在A,也不在B，必然就不在A,B的內(nèi)。所以DFSTree。。如何快速判斷點(diǎn)是否在多邊形內(nèi)(上)。判斷Q是否在多邊對(duì)于滿足Min(Pi.x,P(i+1).x)≤Q.x<Max(Pi.x,P(i+1).x)的邊(Pi,P(i1))。若Det(Pi,P(i+1),Q)>0Count++;若Det(Pi,P(i+1),Q)<0Count--。若|Count|=2，則Q在多邊形內(nèi)；若|Count|0，則Q即以Q做x垂線它與多邊形的所有交點(diǎn)所在的邊，相臨交點(diǎn)所對(duì)應(yīng)的邊的方向一定不同。利用邊方向交錯(cuò)的性質(zhì)，就可以找到Q判斷，所以在DFSTee中可以用部分和的方法，存下當(dāng)前點(diǎn)到根的路徑上的統(tǒng)計(jì)信息。找到圈就可以O(shè)(判斷了。+Arithmetica對(duì)于含+-*()的運(yùn)算表達(dá)式求值又是一道表達(dá)式處理017+Theoptimal在平面上在給定線段PQ上行走的速5求從A到終點(diǎn)B用的最少時(shí)應(yīng)用Fermat光行最速原理，路就可以了。有兩種走法直接從A到B從A到達(dá)PQ，然后在上PQB兩側(cè)；入射角的正弦和折射角的正弦成正比n。而n又等于入射光線所在介質(zhì)的光速v1除以折射光線所在介質(zhì)的光速v2目中已給出速度，可以看作光路從某垂直于PQ的垂足處+i=i-若i是偶數(shù)用最少的步數(shù)使得i=0。開(kāi)始時(shí)，i=可以遞推，或者貪心：i2，當(dāng)imod4=1i3時(shí)減1，剩下的加1將i01的串相間。來(lái)看末尾的一塊，若這塊為02串長(zhǎng)度減少1，而對(duì)0串的加減操作對(duì)前面的1串不會(huì)有正面影當(dāng)末尾為1串時(shí)， 1。。(1串長(zhǎng)+1)位）；若此時(shí)選擇減1操作更優(yōu)，那么會(huì)一1行一次減操作，總次數(shù)為(2*串長(zhǎng)-1)，再考慮較之加1操作略。當(dāng)然了特殊情況3，此時(shí)要減1，因?yàn)榧?并沒(méi)有1多消除一位。+Odd有n的正整數(shù)，其中只有一個(gè)值重復(fù) 將所有數(shù)XOR起來(lái)，就得到了答案。+Circle給定K，有2K個(gè)人圍成圈，從1號(hào)開(kāi)始每次殺掉第M個(gè)人使得殺掉的前K3const+Stormina給定一個(gè)國(guó)家的N*M的矩形地圖，其2*2的格子不可能屬于4個(gè)省份任意一個(gè)“田”中4個(gè)格子不能分屬4個(gè)省份。初看似乎沒(méi)什么因此可以把這些省份縮成一個(gè)點(diǎn)S，添加一個(gè)源點(diǎn)T與所有的邊界省份相連，問(wèn)題轉(zhuǎn)化為求S到T的最短路。答案即為最短+Disclosingof024+Minimalsumof因?yàn)樗悬c(diǎn)的坐標(biāo)在-15到15并且所求的解要求保留小數(shù)0.130020.001求使得z=∑nfi*d(x,y,xi,y達(dá)到最小的點(diǎn)(x,y) ））d(x,y,ab)表示在平面上(x,y)到(a,b)0觀察zz的形狀總是向最低點(diǎn)塌陷的。于是可以設(shè)當(dāng)前解為P(x,y)，以一個(gè)步長(zhǎng)len，走到一個(gè)隨機(jī)點(diǎn)Q（滿足|PQ|=len）。若Q的值比PQ取代P若干次在該步長(zhǎng)下都沒(méi)有較優(yōu)解，則len=len/2len小+StarWar(epizode給定平面上N個(gè)圓，求一條直線最多穿因此可以窮舉任意兩個(gè)圓，對(duì)其公切線進(jìn)行檢查（只用檢查外公切線，因?yàn)榧僭O(shè)可以通過(guò)某兩個(gè)圓的內(nèi)公切線得到毀。此算法時(shí)間復(fù)雜度為O(n3)，空間復(fù)雜度為O(n)至于求公切線的方法多種多樣，用計(jì)算幾何的方法+次相連可以組成N2個(gè)角形。在任意一對(duì)角形之間存在已知的不等根據(jù)已知的大小關(guān)系建立一個(gè)有向圖A<B則連一條有向1至N2，由于這題中，邊的個(gè)數(shù)是O(N2)級(jí)的，因此拓?fù)渑判虻臅r(shí)間雜度可以優(yōu)化至O(N2)+給出底部），告訴你下雨的雨量H 中的O(N)算法：，，，，求積水的深度最大可能值10000）解法三：（郭華陽(yáng)對(duì)于每個(gè)點(diǎn)p，向左找出第一個(gè)比它高的點(diǎn)L[p]以及右邊第一個(gè)比它高的點(diǎn)R[p]；記錄顯然L[p]~R[p]可能形成一個(gè)pond，記錄這pond為容易證明，extended[p]和所有可能的pond是一一對(duì)應(yīng)記錄LT[p]為(L[pp)中最高的點(diǎn)，顯然，(L[pp)是一個(gè)可能的pond，并且等于extended(LT[p])；同樣的有結(jié)構(gòu)完美的反應(yīng)了所有pond之間的關(guān)系；接下來(lái)，……我用的是最后法。得到二叉樹(shù)結(jié)構(gòu)后，從上往下遞具體實(shí)現(xiàn)的時(shí)候有很多trick（可以參見(jiàn)程序），寫(xiě)得好的O(N)。+經(jīng)典的Camelot問(wèn)題：有一個(gè)國(guó)王和M個(gè)騎士被放置在一個(gè)N*N的棋盤(pán)上USACOTrainingGate也有這道題，不過(guò)數(shù)據(jù)沒(méi)這道題大。優(yōu)化，網(wǎng)上有很多題解，USACO上也有，如果實(shí)現(xiàn)不好的同+Two完全就是體力活24種旋轉(zhuǎn)，或者Const出來(lái)旋+um給出N種物品(PiMiQi)，PM是質(zhì)量，Q是物品最多可取個(gè)數(shù)直接背包的復(fù)雜度是O(NBQ)的，可以通過(guò)此題。此題還可，，的質(zhì)量總和在[A,B]內(nèi)且利潤(rùn)最大，如果無(wú)法取出[A,B]內(nèi)的質(zhì)量，輸出-1設(shè)狀態(tài)是opt[i][j]表示前i種物品質(zhì)量總和為j時(shí)的最大opt[i]jmodMi分類的和opt[i][jb]，若有opt[i][ja]+(jb-ja)/Mi*Pi≤opt[i][jb]（ja<jb），那么明顯ja是不會(huì)對(duì)jb之后的狀態(tài)作出貢獻(xiàn)的，因而可以將之從隊(duì)列中刪除。在j增大的同時(shí)根據(jù)Qi刪除隊(duì)首元O(NB)+Rootsof1。（設(shè)方程為f(x)=0，其中f(x)=aNxN+aN-1xN-1+…+a1x+a0。那么可以設(shè)aN=1（簡(jiǎn)單的變換可以得到）。新構(gòu)造一個(gè)矩陣Aij（1≤ij≤N），1(i-Aij{-ai(j=N)那么顯然方程f(x)=0的根就是A矩陣的特征值，于是問(wèn)題可以轉(zhuǎn)化為問(wèn)A1。這也就等價(jià)于問(wèn)AN0+CalculatingXORviaAND位數(shù)后存在AND操作（返回n位數(shù)）設(shè)該操作為ANDn(A)，同理可定義給定n，求滿足m<n的條件下，最大的m值，并滿足：存在一個(gè)g1，將2m位數(shù)為m位數(shù)，并且對(duì)于XORm(A)操作，有2m個(gè)不同返回值，每個(gè)返回值有個(gè)與之對(duì)應(yīng)的自變量A。對(duì)于ANDn(A)操作，雖然有2n個(gè)nnin），求一個(gè)m（m<n）2mm設(shè)k3k≥2m那么有Ck+Ck+1+? ≥ +Murderofmister圖），Mr.S在其中的一個(gè)點(diǎn)上（Mr.B位移動(dòng)到相鄰的點(diǎn)。Mr.B每個(gè)時(shí)間單位轟炸一個(gè)頂點(diǎn)，問(wèn)Mr.B能不能確保存在一個(gè)一定將Mr.S炸死的方案。（么每次你能消除一個(gè)1，而下次只要與1相鄰（本身不算），目 打掉一個(gè)點(diǎn) ，， 1的數(shù)目無(wú)限擴(kuò)充，10|0-0-0-0-0-0-0-2的分叉：1-0-1-1-（消除0-1-1-1-（消除1-0-1-1-0-1-0-1-如果多個(gè)分叉，那么如法制，把所有的分叉奇偶分家3，無(wú)法做到了。如果一塊相連區(qū)域沒(méi)有奇數(shù)偶分家，那么這區(qū)域只有一次的空閑，如果兩次空閑，那么1又會(huì)兩塊沒(méi)有奇偶分家的塊，除非像長(zhǎng)度小于2的分叉，通過(guò)一步之相連時(shí)，Mr.S可以ESC。Rubik'sCube2××2*2*2啊哈，近段時(shí)間看了哈玩Cube的專業(yè)選手，居然蒙著眼睛都o(jì)rz，簡(jiǎn)直就是個(gè)計(jì)算機(jī)。+LCS（經(jīng)典DP有的同學(xué)可以想想當(dāng)序列只有0和1的時(shí)候怎么優(yōu)化+將區(qū)間按照左端點(diǎn)排序后DP，復(fù)雜度為O(NlogN)此類問(wèn)題在區(qū)間范圍較小時(shí)直接以坐標(biāo)為下標(biāo)DP編寫(xiě)起來(lái)方+Frame給出X*YX*Y的矩形架。給出N個(gè)詢問(wèn)：是否可以用A*1（3≤X,Y,+Picture給定一個(gè)X*Y的BMP格式的文件，（X,Y<1025很好玩的題，可以學(xué)習(xí)BMP直接將給出的BMPfloodfillOKBest個(gè)集合，對(duì)集合S，若|S|=k，那么定義這個(gè)集合的D距離的平方和除以k。進(jìn)行恰當(dāng)?shù)姆纸M使得D值總和盡可能OAC……偶菜飄過(guò)。題目描述和評(píng)測(cè)標(biāo)準(zhǔn)……NP問(wèn)3（否則可以分成兩部分而D值和更?。?，還有點(diǎn)在一條直線+12233444555開(kāi)頭的數(shù)列f(i)，其中每個(gè)數(shù)字x重復(fù)f(x)次。已知n，求f(n)。答案和√n同階，可以先求出i=1到106（其實(shí)只用到673365）的f(i)值，得出每個(gè)數(shù)出現(xiàn)的次數(shù)，然后在O(√n)的時(shí)間內(nèi)判斷第n個(gè)數(shù)f(n)是多少——相當(dāng)于求最小的i使得f(1)+f(2)+f(i)≥N，當(dāng)然，這一步還可以改進(jìn)成求最小i1*f(1)+2*f(2)+i*f(i)≥N+Chessend-264*64王固定c3不能移動(dòng)，白方會(huì)用最在得到狀態(tài)后，用何順序計(jì)算各所需狀態(tài)的最長(zhǎng)拖延值，是個(gè)很讓人困擾的問(wèn)題。開(kāi)始的時(shí)候我曾嘗試用化搜索，但是對(duì)于邊界以及棋局出現(xiàn)環(huán)的處理我一直沒(méi)有想出來(lái)好的解決方如果前繼是黑方走，那么僅當(dāng)該前繼的所有子狀態(tài)都被擴(kuò)（，注意這里要處理和不算贏的情況。不少博弈問(wèn)題和最大最小思想有關(guān)，如min-max過(guò)程及其alpha-beta剪枝，題目：EastCentralNorthAmerica1999ProblemA.TriangleWar。+numberofsteps幣），你還可以用k*100個(gè)硬幣跳過(guò)接下來(lái)的k步，但是第一步和最后一步最直接的做法是O(N2)DPopt(i,j)表示前i個(gè)手續(xù)，只辦理了jopt(ij)=max(opt(i-1,j)-100,opt(i-1,j-1)+第i步硬幣得失數(shù)量)，而不可能達(dá)到O(N)方法+Tworegular給定兩個(gè)含"?*"的正則表達(dá)式R1和R2S能被R1、R2同時(shí)（|用opt(i,j)表示同時(shí)滿足R1[1..i]與R2[1..j]的最短字符串長(zhǎng)度。狀態(tài)轉(zhuǎn)移時(shí)可直接由opt(i,j-1)opt(i-1,j)得出opt(i,O(N2)+Strange +按順勢(shì)針順序給出一個(gè)1至N的全排列直接搜索，時(shí)限對(duì)于10!=3628800來(lái)說(shuō)很寬裕同學(xué)可以參見(jiàn)2008集訓(xùn)隊(duì)。+Love給出有向圖G，求沒(méi)有弦的最長(zhǎng)圈搜索……Searchingwithunderwear+Mine給定M個(gè)的坐標(biāo)，以及點(diǎn)A和B。求RA到B，其上所有點(diǎn)離的距離均超過(guò)100000的實(shí)數(shù)可以先通過(guò)二分法枚舉R，將所有距離小于等于2R的相023Wayamongsticks的算法了。但需要說(shuō)明的是，本題有另外法，就是對(duì)這個(gè)圖建立一個(gè)VoronoiDijkstra算法，就可以得到兩個(gè)圓的最大半徑了，時(shí)間復(fù)雜度約為O(Mlog2M)。一個(gè)二分或增量算法求R，等價(jià)變換后如下：求出MT（其實(shí)平面最小生成樹(shù)就可以拿Voronoi搞），從小到大枚舉不在樹(shù)上的邊(i,j)，判斷這條邊和T中路徑(i,j)構(gòu)成的通路是否分離了AB。時(shí)間復(fù)雜度：+Trip給定平面上N個(gè)點(diǎn)，若點(diǎn)距不超過(guò)R，A到點(diǎn)B且經(jīng)2、3象限上的點(diǎn)的最短路長(zhǎng)度。（3≤N≤300，0≤R≤300，坐標(biāo)為(-100000,100000)內(nèi)的實(shí)數(shù)分別以點(diǎn)A，點(diǎn)B2、3象限的中轉(zhuǎn)點(diǎn)pdis(Ap)+dis(pB)更新最優(yōu)值即可。+Best用opt[0..2N-1]的狀態(tài)表示N個(gè)點(diǎn)中的將其兩兩配對(duì)后+Hacker's24bits的數(shù)a、b、c，設(shè)經(jīng)過(guò)mod224a1、b1、c1一組滿足要求的a、b、c+Aliseand一個(gè)數(shù)，Basilio來(lái)猜，Alice可以對(duì)BasilioYESNO。已知Alice1,2,…,N各ni次，根據(jù)這個(gè)Malvina寫(xiě)了個(gè)程序讓猜測(cè)這樣問(wèn)題就轉(zhuǎn)化為了較簡(jiǎn)單的Huffman編碼問(wèn)題，即對(duì)頻次為ni的N個(gè)字符編碼，然后程序的詢問(wèn)相當(dāng)于在Huffman樹(shù)有關(guān)Huffman以及其他各種編碼譯碼的問(wèn)題可以參見(jiàn)我+一些錄在時(shí)間為N分鐘的磁帶上，制的曲目不能重復(fù)）+要寫(xiě)一個(gè)程序?qū)τ蠳簇的磁盤(pán)上的K個(gè)文件做整理，使得大小為Si（包含Si個(gè)簇）文件ii-1后的Si簇（11到S1optimizationneeded"。O(N)。+Bi表示滿足i<j且Ai<Aj的j的個(gè)數(shù)。給出B，求A。直接按照i從小到大的順序，用鏈表每次取出剩余元素中Bi+1大的即為Ai，復(fù)雜度為O(N2)，可以通過(guò)此題O(log2N)的時(shí)間內(nèi)查詢，總復(fù)雜度為O(NlogN)+過(guò)不匹配的正則表達(dá)式R，判斷一個(gè)字符串SR匹配。好像Ruby，Python等語(yǔ)言有內(nèi)置正則表達(dá)式匹配，可以直此類匹配問(wèn)題大都可以在O(N2)的時(shí)間內(nèi)解決，用狀態(tài)g(ij)表示目標(biāo)串前i位和模板前j位是否匹配或者最多匹配多少位等，轉(zhuǎn)移通常是常數(shù)級(jí)別的，如此題每個(gè)狀態(tài)只和g(i-1,j)、g(i,j-1)，以及當(dāng)遇到’]’時(shí)找到其匹配括號(hào)’[’的位置所產(chǎn)生的不知道有沒(méi)有O(N)的算法+給出一個(gè)長(zhǎng)寬為偶數(shù)的棋盤(pán)，上面有n棋盤(pán)上有3類位置：1個(gè)點(diǎn)互相對(duì)稱，2個(gè)點(diǎn)互相對(duì)稱，4個(gè)經(jīng)存在q個(gè)jewel的位置。給出一些二元組(pq)，p=1,2,4，0<=q<=p；從中選出一些二元組，使得p=N，并且q最大。先不考慮(1,q)；如果Nmod40，那么選取的(2q)必然是偶數(shù)個(gè)，也就是說(shuō)，(2q)必然是成對(duì)選取的；按照這個(gè)思想，如果選兩個(gè)(2,q)，必然是選q最大的兩個(gè)二元組，依次類推；那么，可以把所有的(2q)轉(zhuǎn)化成(4q’)，每次挑選兩個(gè)q最大的二元組(2,q1)(2,q2)合并成(4,q1+q2)即可。如果Nmod42，那么先挑一個(gè)q最大的(2,q)，剩下的合如此，只需要面對(duì)的就是(4,q)，相信對(duì)于這樣的貪心們是可以輕松解決的+MaxDay2的投籃（shooting），給出n個(gè)整數(shù)分成m組，使+Queuefor有Ni個(gè)人買(mǎi)一張票需要Ai秒，兩張需要Bi秒，三張需要Ci秒。連續(xù)的幾個(gè)人（最多三個(gè)）+Counting給出一張分成了*N次放上K1Li的起點(diǎn)不同的黑紙片詢問(wèn)最后白方格個(gè)數(shù)或者白連通塊個(gè)數(shù)。集，當(dāng)上一行存在的集合沒(méi)有延伸到當(dāng)前行時(shí)，累加這種復(fù)雜度，時(shí)間復(fù)雜度為O(MNlogK)。 2005WC的解題報(bào)告。RP），使用類似于C++中的bitset或者vector<bool>減少使用類型浪費(fèi)的3比特這樣O(MN)的空間是可以承受（MIPT64Mb），然后K條黑紙片直接在讀入時(shí)存進(jìn)矩陣（雖然K*max(M,N)很大……），之后用BFS實(shí)現(xiàn)FloodFill統(tǒng)計(jì)連通塊數(shù)。厄……惡寒中，當(dāng)年偶真是無(wú)+求所有{23n,n+1}的排列A，使得任意i都有Aimodi=0。Searchingwithunderwear搜吧，搜吧，人總要學(xué)著搜索長(zhǎng)大+在n*n有的棋盤(pán)上覆蓋最多的不的塊將棋盤(pán)黑白間隔染色，以黑色為x部，白色為y部，得到一個(gè)+GraphSearchingwithunderwear+Squarerootof本問(wèn)題以及置換群的各種冪運(yùn)算的具體方法可參見(jiàn)的，，集隊(duì)+求最大的正整數(shù)L，使得Sum[Floor[A[i]/L]1≤i≤n]≥K成立。（0≤A[i]≤10000000，二分查找L，當(dāng)當(dāng)前L值滿足條件時(shí)，說(shuō)明L可以取更大值，復(fù)雜度為O(NlogL)。0（好像MIPT很多題都不+Chess90度）一個(gè)面上有值的正方塊，24個(gè)結(jié)點(diǎn)，連好邊后直接dijkstra。+Enclosingpointwithpolygon給N個(gè)點(diǎn)和點(diǎn)P，選一些點(diǎn)組成多邊形使得P在它的 （注意P不能在多邊都過(guò)K，要求多邊形周長(zhǎng)盡量小4位小數(shù)的形式給出）回憶一個(gè)判斷點(diǎn)P是否在多邊形C的算法：從C向外作一條射線，若與P的交點(diǎn)為奇數(shù)條則C在 ，否則在外部（參見(jiàn)Problem023本題可以看作是要找出一條最短的閉合路線。使得被P向外的射線經(jīng)過(guò)奇數(shù)次。記錄（u,v,k）表示一條由uv的路線，使得Pk（k=01那么答案就是min(F(u,u,1)。F可以通過(guò)最短路算法來(lái)求解。值得一提的是，由于求的是最短路，求出的多邊形一定是簡(jiǎn)單多邊形，不會(huì)有邊自交的情況，如下圖所示：DA 此題最容易錯(cuò)的地方是判斷線段是否和P引出的射線相交，如判斷nPOI05SpecialForcesManoeuvres一題是此題二維版本：要求一個(gè)平面上n個(gè)圓是否有交集。首先，若干個(gè)圓的交中橫，。，。小的。設(shè)n個(gè)圓為C1C2CnPxmax(P)，相應(yīng)地定義xmin，上面的結(jié)論寫(xiě)成公式就xmax(?nCi)=xmin{xmax(Ci∩Cj)}推廣到三維球的情況，只用求出每三個(gè)球的交集的z坐標(biāo)+Rootofthe解方程x^(x^(x^(x^(個(gè)A，其中x1此題相當(dāng)于求xA=A的解，于是x=AA，注意A>e或+Bracketstructure（如”)))…)(…(((”O(jiān)(N)。如果LRmdiv2+ndiv2+mmod2+nmod2。+N皇后問(wèn)題Searchingwithunderwearor強(qiáng)烈一道有位置的N皇后問(wèn)題：。這道題需+Next給出一個(gè)長(zhǎng)為L(zhǎng)的單詞，求所含字符相可以直接調(diào)用STL中的next_permutation算法next_permutationstr，求字符序與其相鄰的較大一個(gè)，可以找到str從右往左第一個(gè)滿足str[i]<str[i+1]的i，將str[i]和str[i+1]交換，然后將+(00)，求光源對(duì)多邊形的照度。知的常數(shù)，r是光源到點(diǎn)的距離。對(duì)于高度為hdl的垂直元線段（可以dI=I0·|cosA|·dl·hA對(duì)于照度可以這樣理解：I0·|cosA|·dl·h=k·(|cos=圓上的一段弧長(zhǎng)（物理競(jìng)賽中常用的微元法@_@），ds/r就是圓心角。于是問(wèn)題就轉(zhuǎn)化為求k*h*[從光源看全多邊形的圓。。來(lái)減少誤差。這道題是NEERC98的，數(shù)據(jù)和標(biāo)程都很好找^_^+給出一個(gè)M*N的字謎，每個(gè)（20*20很明顯的搜索題，VIJOS上也有一道同樣的題，但是好像難過(guò)好像不少的小都被搞成了ACM題@_@Swimming在一個(gè)MX*MY的矩形房間中有N個(gè)圓形，求一個(gè)能放在房間中的最大的由于所有半徑相同，于是可以對(duì)所有的圓心O(N2)地構(gòu)造DT（轉(zhuǎn)化為求Voronoi圖），然后對(duì)于DT中的每個(gè)三角形，求出和三個(gè)頂點(diǎn)上的外切的最大圓，只有O(N)個(gè)。（沒(méi)寫(xiě)過(guò)Voronoi，是洪驥同學(xué)告訴-_-Clusterizationofbinarywords兩個(gè)串的hammingdistanceD+2-SAT問(wèn)題：?jiǎn)杗個(gè)變?cè)欠翊嬖谝粋€(gè)解滿足m個(gè)最多只有兩個(gè)變經(jīng)典算法，可參見(jiàn)2003集訓(xùn)隊(duì)：伍昱的《由對(duì)稱性2-SAT問(wèn)題》。這篇文章也有詳細(xì)的講解+Farthest（點(diǎn)數(shù)個(gè)指針i和j掃描一圈即可，j表示離i最遠(yuǎn)的對(duì)踵點(diǎn)，j一定沿i掃描方向前進(jìn)。+一個(gè)等邊三角形A'B'C'使得r=max(|A'A|,|B'B|,|C'C|)假想已知r的上限。這樣A’,B’,C’的范圍就是3個(gè)半徑為r的圓。那么首先令A(yù)’=A,B’=B，那么可以求出一個(gè)C’（不妨設(shè)這個(gè)C’初始位置為D）。C’也在相應(yīng)的半徑為r圓心為DA’，移動(dòng)B’C’繼續(xù)移動(dòng)了至多rC’C為圓心rDC的距離≤3r。所以可以知道r=(以A,B為頂點(diǎn)的等邊三角形第三點(diǎn)和的距離的最小值)/3Cr 那么根據(jù)前面的結(jié)論。所求的C’在此時(shí)僅有唯一確定的點(diǎn)，也就是CD的三等分點(diǎn)中比較靠近C的點(diǎn)。同理可以求出A’，B’。很巧妙的是這樣求出的?A’B’C’恰好是一個(gè)等邊三+給出n!的值，求n直接高精度乘上去的時(shí)候判斷，如果想偷懶就用Java，直接乘，較大時(shí)看log10(乘出來(lái)的數(shù))是否和log10(讀入的double值)的差在較小范圍內(nèi)（如1），是則輸出答案+判斷一個(gè)含"&|!"與最多n個(gè)變?cè)牟糚roblem030p-adic數(shù)(a0a1p代表a0p0a1p1+...，其中ai為[0,p-1]的整數(shù)且p為素?cái)?shù)。那么可以定義p-adic設(shè)A和B分別是自然數(shù)a和b的p-adic數(shù)形式，那么設(shè)p-adic數(shù)X=a/b，則有B*X=Aa，b和pa/b得p-adic表達(dá)，輸出最短非循環(huán)部分pB*X=A可以看作將b乘到X的每一位上最后得到了可以從xo開(kāi)始逐個(gè)求出X先預(yù)處理一個(gè)數(shù)組inv[]，其中inv[i]滿足p)+p-adic計(jì)算時(shí)當(dāng)前計(jì)算的X位Xiinv[amodp]，然后將a(a-b*Xi)/p。如此循環(huán)計(jì)算直到a為非正數(shù)，這時(shí)已計(jì)算出位就是X的開(kāi)頭的非循環(huán)部分。若此時(shí)a0+8-8公司的Astar某次總決賽就是比誰(shuí)的8數(shù)碼算得快-_-|||。8數(shù)碼搜法A*之類的個(gè)人認(rèn)為最好寫(xiě)的是直接廣搜，80~8的全排列，總狀態(tài)數(shù)不多，具GraphO(n2)的DMP算法能過(guò)，還有Hopcroft-Tarjan平面判定法……有的同學(xué)可以去查看資料151000沒(méi)時(shí)間做-_-|||。和8數(shù)碼不一樣的是空間和時(shí)間都不允許））剪枝，以及將最后幾步const出來(lái)等來(lái)優(yōu)+給出一張有向圖G(V,E)，在其中選最0O(E)+Whatisthenumber(PartII)?答案對(duì)應(yīng)的N的區(qū)間const下來(lái)（答案范圍很小），N后+PS表示法表示的圖只能有并聯(lián)串聯(lián)兩種形式。求一個(gè)用PS表示法表示的電（電阻值在[0,100000]內(nèi)，輸入長(zhǎng)純粹的物理題，用遞歸（或模擬遞歸）+PS-graph。即可以從一條邊經(jīng)過(guò)若干次double和split操作得到。（如果有兩條重復(fù)邊，那么肯定是由一次duplicate操作得如果有一個(gè)點(diǎn)出度入度均為1，那么肯定是有一次split操PS圖以通過(guò)事實(shí)——操作12不會(huì)將一個(gè)PS-graph變?yōu)榉?PS-graph。即可以從一條邊經(jīng)過(guò)若干次double和split操作得到。（如果有兩條重復(fù)邊，那么肯定是由一次duplicate操作得2，且兩邊不重復(fù)，那么肯定是有一次split操作得到，合并為一條。PS圖樣用C++中的STL實(shí)現(xiàn)會(huì)很方便Cutted把n個(gè)矩形拼成一個(gè)大矩形，要求用一直接搜0+Upgradingto0的點(diǎn)u0的點(diǎn)v，那么連(v,u)如果存在不能到達(dá)的點(diǎn)v，那么連(v,u)0的點(diǎn)v，那么連(v,u)否則亂連一個(gè)(v,u)0PS-scheme,給出有理電阻值R=M/NM和N最少的電阻值為1的單位電阻，且能用PS表示法表示這個(gè)電阻網(wǎng)路。（1≤M,本題是094錯(cuò)誤貪心是這樣的：對(duì)于M=N直接一個(gè)電阻，M>N則用一個(gè)單位電阻和剩余的串聯(lián)，M<N則并聯(lián)盡量多的單位電阻和N/(MmodN)的電阻。2007長(zhǎng)春賽區(qū)ProblemG 和N都不超過(guò)512，下面解題報(bào)告：點(diǎn)就是要注意到，m/n和n/m的組成是正好對(duì)稱的）。m/n，428/22615214/11316。這就是題目描述最后一段的用意，根據(jù)這個(gè)限制，m/n只需要計(jì)算到512就可以了。+NimGame--Whoisthewinner?有k堆石子，每次可以從任意一堆里拿人獲勝。已知k和石子的分配情況，求（k<50，每堆石子數(shù)經(jīng)典的Nim問(wèn)題，直接將k個(gè)數(shù)xor起來(lái)，得到當(dāng)前局面xor值，如果xor0可以簡(jiǎn)單地發(fā)現(xiàn)，xor0的局面無(wú)論怎么操作都會(huì)得到非0局面，而可以使得一個(gè)非0局面的后繼是0局關(guān)于博弈問(wèn)題，如SG函數(shù)等，可以參見(jiàn)張一飛的《由感還有很多有關(guān)gametheory的外文書(shū)籍，有的同學(xué)可以去網(wǎng)上搜索。+StoneGame--有k將所有的石子個(gè)數(shù)mod30、1、2進(jìn)行xoristhe出2的冪個(gè)石子，拿走最后一顆石子的人獲勝。已知k和石子的分配情況，求（k<50，每堆石子數(shù)0與Problem10020mod31,21mod32，因此必勝者可以不斷進(jìn)行使得對(duì)手得到的局面的xor值總0。+StoneGameII--whoisthewinner?有k堆石子，每次可以從任意一堆里拿k和石子的分配情況（k<50，每堆石子數(shù)此題要用到著名的Sprague-Grundy而多個(gè)并行的博弈的總SG值就是他們各自的SG值得xor值——P100和P101也都用到了SG函數(shù)。當(dāng)一個(gè)局面的SG0時(shí)，就是必?cái)B(tài)，否則為必勝態(tài)。而此題的每堆石子的SG值再簡(jiǎn)單的列舉后可以發(fā)現(xiàn)就是f(x)={xdivf(xdiv這樣只要計(jì)算初始狀態(tài)的f+NimGame--Give有k堆石子，每次可以從任意一堆里拿人輸。已知k和石子的分配情況，求先（k=4，每堆石子數(shù)這就是是大名鼎鼎的MisèreNim。其實(shí)本題的算法和Problem100是一樣的，只是當(dāng)所有的石子數(shù)都≤1時(shí)，將同樣可以一個(gè)xor計(jì)算后的序列，使其始終全0。但就要使xor1+CamoGame--whoisthe輸。告訴你M和石子分配情況，求先手得出SG函數(shù)：SG(x)=min{n|n!=SG(L)xorSG(R)}。最后將所有m列的SG值xor起來(lái)得到最終的SG值。當(dāng)然你也可以找找SG值的規(guī)律。Problem100-104是優(yōu)秀的博弈問(wèn)題，特別是SG這方面的入門(mén)題目，當(dāng)年曾讓我獲益匪淺。除了P048中提到的極大極小思想外，SG也是博弈方面很重要的內(nèi)容大家去看看胡伯濤PT07比賽的ProblemA:PlaywithaTree。+MRQ經(jīng)典RMQ問(wèn)題：在給定n個(gè)元素的序列上詢問(wèn)一段區(qū)間中的最小值m個(gè)詢問(wèn)。采用SparseTable，O(NlogN)–O(1)：F[i,j]表示區(qū)間[i,i+2j-1]內(nèi)的最小值，然后按照j從小到大計(jì)算值，求區(qū)間最小值時(shí)將區(qū)間分為中間可能部分的2?的兩個(gè)區(qū)間查詢。此題很容易MLE，其實(shí)只要不使用double類型，使用Pascal中的real或者C中的float就可以了。還有法也可以節(jié)23——F[i,j]表示區(qū)間[i,i+3j-1]內(nèi)的最小+給出一張有M，，，，+Infixtopostfix（遞歸著做寫(xiě)起來(lái)可能容易些，關(guān)于表達(dá)式處理可參見(jiàn)P087分+GrammarofaGreatMachine(Correctwords1)3SSS||7SSSSSSS)，給出串一個(gè)（輸入為一行由0-7組成的長(zhǎng)度不超0串（用棧實(shí)現(xiàn)，從前往后貪心的掃描）0串Half-planes+Graph（1000個(gè)用類似于Kruskal最小生成樹(shù)的方法判斷哪些是邊，然后重Reductionto給出一個(gè)多項(xiàng)式SS::=|R(('+'|'-')NUMBER:=<integernumberlessthan10000inmoduli>PNUMBER:=<postiveintegernumberlessthan1000>R::=A('/'A)?A::=|'x'('^'|'('NUMBER|'('C(('+'|'-')C)*C::=(NUMBER'*')?'x'('^'或者”0”的形式，要求(p(x),低。’*’的結(jié)合性是從左到右，即a-b-c是((a-b)-c)。（10002000000000+一個(gè)n*m迷宮有K個(gè)出口，有些格子由于是網(wǎng)格，邊比較少，直接SPFA可以通過(guò)。Plane（0<N≤1000，坐標(biāo)為絕對(duì)值不超100000的整數(shù)直接建圖然后DFS（對(duì)每個(gè)點(diǎn)按照邊的極角序拓展+Unique給N個(gè)形如X*Y=Z或X+Y=Z的等11的串，如果進(jìn)制可以唯一確定那么X，Y，Z不會(huì)超過(guò)264-1226The給一個(gè)由dot,hyphen0組成的表可能是hyphen）0使得所有連續(xù)hyphen的長(zhǎng)度為給定值。0一定是-，“000”連續(xù)的“-”長(zhǎng)度為2，則只能確定中間那個(gè)0為-，原串二維DP可以求出可行性問(wèn)題，計(jì)算唯一性實(shí)際上可以看作是一個(gè)。以f[i][j]表示第一個(gè)串的前N個(gè)匹配到第二個(gè)串的前J可能。那么f[n][m]表示整個(gè)輸入數(shù)據(jù)是否可能。注意到，題目就是要求一個(gè)f[n][m]到f[0][0]的必經(jīng)點(diǎn)集（如HardNEERC可參見(jiàn)胡伯濤07年和作給P和A0,…,Ap-1，求次數(shù)不超過(guò)P-的多項(xiàng)式Q(x)使得Q(x)=Axmod所有系數(shù)均在{0,1,…,P-1}中+Universalparser達(dá)式的+RangeADDxy—在平面上添加一個(gè)者"ALREADYEXISTS