最近參加了N多模擬賽……現在統一總結一下。
那些有代表性的題目總結一下。
（1）Aug.16
Poetize 杯NOIP模擬賽 I（竟然AK了，虐場虐得真爽）
第一題：容易發現如果新加入的那條邊連接的是同一個連通塊，結果乘2加1，如果是不同的連通塊，結果不變。證明：如果新邊(i, j)的是同一個連通塊，則原來i到j必然有路徑，設P為i到j的一條路徑，則在加入新邊以前，原圖的所有滿足條件的子圖都可以對P異或后得到一個新的圖，該圖僅有i、j兩個的度為奇數，其余點的度均為偶數，加入(i, j)之后得到一個新的滿足條件的子圖，所以乘2，注意(i, j)加上P也是一個滿足條件的子圖，所以加1；如果原來i和j不在同一個連通塊中，那么必定不存在包含(i, j)的滿足條件的子圖（否則這個子圖將(i, j)刪掉后會得到兩個頂點度數和為奇數的連通塊，這是不可能的），所以不變；
（2）Aug.17
Clover 杯NOIP模擬賽 I第一題：判斷一個點是否在三角形（其實對于所有的凸多邊形都是這樣）時，不需要引射線，只需把三角形的三個頂點按逆時針排序，然后判斷該點往三角形的三對相鄰頂點（按逆時針）的叉積是否都非負就行了；
第三題：枚舉起點，然后狀態壓縮DP，注意最后一個點必須壓縮一下才能不MLE；
（3）Aug.18
Vijos復活邀請賽第一題：比較WS的幾何題。判斷圓與邊平行于坐標軸的矩形是否相交的時候，可以采用以下的簡便方法：一個圓與一個邊平行于坐標軸的矩形相交，當且僅當矩形的四個頂點至少有一個在圓內，或者圓的四個橫縱坐標最值點（最上、最下、最左、最右的點）至少有一個在矩形內，或者圓心在矩形內。
第三題：主要難在s-t兩條路徑怎么找出來的問題，方法：以s為根建有根樹，找到到t的路徑后，將那條不在樹中的邊的兩端點到根的路徑上的所有邊都標記上，然后，若這棵樹中s-t路徑上的所有邊都沒標記，則s-t只有一條路徑，否則任選一條s-t路徑上的標記邊刪掉，然后再以s為根建一次有根樹，就可以找到第二條s-t路徑了；
（4）Aug.19
[Vani有約會]杯邀請賽 II第二題：本沙茶的80%做法有點另類，是狀態壓縮DP，因為對于N<=800的數據，只有2、3、5、7、11、13、17、19、23這9個質數可能出現兩次以上，其余的都只會出現一次，所以建立10個容器（別忘了1），分別分配1和這9個質數，再對剩下的質數狀態壓縮即可（一開始只建了9個容器，結果N=27掛了）；
（5）Aug.20
『Citric杯』NOIP提高組模擬賽 I第一題：這也太太太坑爹了吧囧……居然在精度上做手腳（Orz @sillycross），注意用long double就行了，不過正解是變除法為乘法；
（6）Aug.21
squarefk NOIP模擬賽第三題：對于一個這樣的序列A[0..N-1]：0<=Ai<=Ui，設F(A)為(A的0元素的個數)^(A的所有非0元素的乘積），問題就是求所有A的F值之積。顯然，指數是不能取模的，所以要設F[i][j][k]為前i位j個非0，底數為k的值，遞推式還是很容易的囧；
（7）Aug.22
Clover 杯NOIP模擬賽 II第二題：問的是無向圖中兩點間是否有且僅有一條路徑的問題。首先肯定是判是否在同一連通塊，然后，對每個連通塊任意建一棵生成樹，如果這兩點在生成樹上的路徑上的每條邊都是橋，顯然只有一條路徑（因為每條邊都必須經過），否則，必有其它的路徑（某條邊不是橋，也就是可以不經過），所以求橋之后就轉化為了一個經典模型了囧……注意求LCA用類似路徑剖分的算法比較好寫……
第三題：很容易想到遞推，F[i][j]：用i個布條，最后一個顏色為j，總方案數（下面的不解釋了），問題是，如果至少有一種顏色能和兩個或兩個以上的顏色相配，還不會有事，因為結果一定不會超過log
2(10
18)，但如果每種顏色都最多只能和一種顏色相配腫么辦？因此這個需要特判：首先那些不能和任何顏色相配的肯定只能長度為1，減掉，然后剩下的每種顏色開始的每個長度的旗幟都各有一個，除以顏色總數（上取整）即可。
（8）Aug.23
Poetize 杯NOIP模擬賽 II 暨Tyvj龍年七夕歡樂賽（第一題正解是貪心，本沙茶用費用流亂搞，T了兩個點）
第三題：A先mod B消去整數。首先考慮有限小數的情況。結果是有限小數時，設小數點后位數為M，則必有A*K^M mod B=0，顯然這個方程有解的充要條件是B的每個質因數也都得是A*K的質因數，只要把B的質因數當中減掉A的，再看看剩下的質因數K是不是都有，都有的話剩下的就是亂搞一下了囧……如果不都有說明是循環小數，設混循環部分位數為M，循環節位數為R，則有A*(K^(M+R)-K^M) mod B = 0，整理得A*K^M*(K^R-1) mod B = 0，注意K^M與(K^R-1)是互質的，也就是把B的質因數中減掉A的之后，剩下的每個質因數，要么就是K有，要么就是(K^R-1)有。這樣，可以用類似于有限小數的辦法來求出M，對于剩下的（K沒有的）質因數，設它們的積（包含指數）為W，則必有K^R mod W = 1，K和W互質，根據歐拉定理，phi(W)必然是一個解，但不一定是最小正整數解，不過，可以肯定的是，最小正整數解一定是phi(W)的因數（不一定是質因數！！），因為若最小正整數解R0不是phi(W)的因數，設phi(W)=P*R0+Q（0<Q<R0），因為K^(P*R0+Q) = (K^R0)^P * K^Q mod W = 1，而(K^R0)^P mod W顯然也是1，所以必有K^Q mod W=1，這樣就得到了一個比R0還小的正整數解Q，這與R0是最小正整數解矛盾。因此，枚舉phi(W)的因數，再用快速冪判斷即可。
（9）Aug.25
『Citric杯』NOIP提高組模擬賽 II第一題：這也太太太太太太太太太太太太太太太太坑爹了吧囧……其實題目描述有漏洞的，因為題目中并木有說表示結束的詢問一定是輸入的最后一個……
第三題：這題本沙茶的做法巨另類也巨繁瑣（就當字符串算法的綜合復習了囧……），首先一頭一尾兩段的字符串還是很好找的……結尾的那段直接枚舉長度，開頭的的那段可以在整個字符串左邊用一個類似KMP的辦法搞（其實只要知道KMP的原理就能用它解決N多奇特問題了囧……），難點在于中間的那段字符串，需要是一個長度為奇數的回文串。為了快速找出一段連續子串里最長的長度為奇數的回文串，可以設G[i]為以i為中心的最長回文串長度，這可以將整個字符串逆序一下后接在原串后面（注意中間要加一個未出現的字符），然后用后綴數組解決（經典模型）。注意在找最長回文串的時候不能直接求中間G[i]的最大值，因為可能延伸出去，正解是二分枚舉這個長度，然后在中間不會延伸出去的那一段里找G的最大值，看是否符合要求。總時間復雜度O(NlogN)。
（10）Aug.26
RQNOJ2012年八月月賽第二題：比賽的時候本沙茶用單調隊列硬搞搞不出來，后來寫樸素了（悲劇）……正解是將所有的前綴和按照先值遞增，再下標遞減排序，并串成Dancing Link，然后從按下標從大到小依次刪掉每個前綴和，這樣，每個前綴和左邊的那個一定是比值比它小的前綴和中值最大（值相同則下標最小）的那個，剩下就不解釋了囧……
（11）Aug.28
「Clover」杯NOIP模擬賽 III第三題：先把每條無向邊拆成兩條有向邊，然后對這個有向圖求源點為1的單源最短路徑圖（就是由所有滿足D[i] + W<i, j> = D[j]的邊<i, j>組成的圖），顯然從這個圖的點1開始無論怎么走都是最短路徑，而且這個圖顯然是無環的（因為原圖中的每條邊權值都是正數，說實話，如果不滿足這個條件，這題就巨難做了，至少本沙茶不會做了），題目中要求的樹就是在這個新圖中從點1開始的一棵外向樹，由于這個新圖無環，所以只需要將每個點（除了1）都找一個父結點就行了，結果就是除1外的所有點入度之積。