信息學-集訓隊作業(yè)mipt.all

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