最近參加了N多模擬賽……現(xiàn)在統(tǒng)一總結(jié)一下。
那些有代表性的題目總結(jié)一下。

（1）Aug.16 Poetize 杯NOIP模擬賽 I
（竟然AK了，虐場虐得真爽）
第一題：容易發(fā)現(xiàn)如果新加入的那條邊連接的是同一個連通塊，結(jié)果乘2加1，如果是不同的連通塊，結(jié)果不變。證明：如果新邊(i, j)的是同一個連通塊，則原來i到j必然有路徑，設(shè)P為i到j的一條路徑，則在加入新邊以前，原圖的所有滿足條件的子圖都可以對P異或后得到一個新的圖，該圖僅有i、j兩個的度為奇數(shù)，其余點的度均為偶數(shù)，加入(i, j)之后得到一個新的滿足條件的子圖，所以乘2，注意(i, j)加上P也是一個滿足條件的子圖，所以加1；如果原來i和j不在同一個連通塊中，那么必定不存在包含(i, j)的滿足條件的子圖（否則這個子圖將(i, j)刪掉后會得到兩個頂點度數(shù)和為奇數(shù)的連通塊，這是不可能的），所以不變；

（2）Aug.17 Clover 杯NOIP模擬賽 I
第一題：判斷一個點是否在三角形（其實對于所有的凸多邊形都是這樣）時，不需要引射線，只需把三角形的三個頂點按逆時針排序，然后判斷該點往三角形的三對相鄰頂點（按逆時針）的叉積是否都非負就行了；
第三題：枚舉起點，然后狀態(tài)壓縮DP，注意最后一個點必須壓縮一下才能不MLE；

（3）Aug.18 Vijos復活邀請賽
第一題：比較WS的幾何題。判斷圓與邊平行于坐標軸的矩形是否相交的時候，可以采用以下的簡便方法：一個圓與一個邊平行于坐標軸的矩形相交，當且僅當矩形的四個頂點至少有一個在圓內(nèi)，或者圓的四個橫縱坐標最值點（最上、最下、最左、最右的點）至少有一個在矩形內(nèi)，或者圓心在矩形內(nèi)。
第三題：主要難在s-t兩條路徑怎么找出來的問題，方法：以s為根建有根樹，找到到t的路徑后，將那條不在樹中的邊的兩端點到根的路徑上的所有邊都標記上，然后，若這棵樹中s-t路徑上的所有邊都沒標記，則s-t只有一條路徑，否則任選一條s-t路徑上的標記邊刪掉，然后再以s為根建一次有根樹，就可以找到第二條s-t路徑了；

（4）Aug.19 [Vani有約會]杯邀請賽 II
第二題：本沙茶的80%做法有點另類，是狀態(tài)壓縮DP，因為對于N<=800的數(shù)據(jù)，只有2、3、5、7、11、13、17、19、23這9個質(zhì)數(shù)可能出現(xiàn)兩次以上，其余的都只會出現(xiàn)一次，所以建立10個容器（別忘了1），分別分配1和這9個質(zhì)數(shù)，再對剩下的質(zhì)數(shù)狀態(tài)壓縮即可（一開始只建了9個容器，結(jié)果N=27掛了）；

（5）Aug.20 『Citric杯』NOIP提高組模擬賽 I
第一題：這也太太太坑爹了吧囧……居然在精度上做手腳（Orz @sillycross），注意用long double就行了，不過正解是變除法為乘法；

（6）Aug.21 squarefk NOIP模擬賽
第三題：對于一個這樣的序列A[0..N-1]：0<=Ai<=Ui，設(shè)F(A)為(A的0元素的個數(shù))^(A的所有非0元素的乘積），問題就是求所有A的F值之積。顯然，指數(shù)是不能取模的，所以要設(shè)F[i][j][k]為前i位j個非0，底數(shù)為k的值，遞推式還是很容易的囧；

（7）Aug.22 Clover 杯NOIP模擬賽 II
第二題：問的是無向圖中兩點間是否有且僅有一條路徑的問題。首先肯定是判是否在同一連通塊，然后，對每個連通塊任意建一棵生成樹，如果這兩點在生成樹上的路徑上的每條邊都是橋，顯然只有一條路徑（因為每條邊都必須經(jīng)過），否則，必有其它的路徑（某條邊不是橋，也就是可以不經(jīng)過），所以求橋之后就轉(zhuǎn)化為了一個經(jīng)典模型了囧……注意求LCA用類似路徑剖分的算法比較好寫……
第三題：很容易想到遞推，F(xiàn)[i][j]：用i個布條，最后一個顏色為j，總方案數(shù)（下面的不解釋了），問題是，如果至少有一種顏色能和兩個或兩個以上的顏色相配，還不會有事，因為結(jié)果一定不會超過log₂(10¹⁸)，但如果每種顏色都最多只能和一種顏色相配腫么辦？因此這個需要特判：首先那些不能和任何顏色相配的肯定只能長度為1，減掉，然后剩下的每種顏色開始的每個長度的旗幟都各有一個，除以顏色總數(shù)（上取整）即可。

（8）Aug.23 Poetize 杯NOIP模擬賽 II 暨Tyvj龍年七夕歡樂賽
（第一題正解是貪心，本沙茶用費用流亂搞，T了兩個點）
第三題：A先mod B消去整數(shù)。首先考慮有限小數(shù)的情況。結(jié)果是有限小數(shù)時，設(shè)小數(shù)點后位數(shù)為M，則必有A*K^M mod B=0，顯然這個方程有解的充要條件是B的每個質(zhì)因數(shù)也都得是A*K的質(zhì)因數(shù)，只要把B的質(zhì)因數(shù)當中減掉A的，再看看剩下的質(zhì)因數(shù)K是不是都有，都有的話剩下的就是亂搞一下了囧……如果不都有說明是循環(huán)小數(shù)，設(shè)混循環(huán)部分位數(shù)為M，循環(huán)節(jié)位數(shù)為R，則有A*(K^(M+R)-K^M) mod B = 0，整理得A*K^M*(K^R-1) mod B = 0，注意K^M與(K^R-1)是互質(zhì)的，也就是把B的質(zhì)因數(shù)中減掉A的之后，剩下的每個質(zhì)因數(shù)，要么就是K有，要么就是(K^R-1)有。這樣，可以用類似于有限小數(shù)的辦法來求出M，對于剩下的（K沒有的）質(zhì)因數(shù)，設(shè)它們的積（包含指數(shù)）為W，則必有K^R mod W = 1，K和W互質(zhì)，根據(jù)歐拉定理，phi(W)必然是一個解，但不一定是最小正整數(shù)解，不過，可以肯定的是，最小正整數(shù)解一定是phi(W)的因數(shù)（不一定是質(zhì)因數(shù)！！），因為若最小正整數(shù)解R0不是phi(W)的因數(shù)，設(shè)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還小的正整數(shù)解Q，這與R0是最小正整數(shù)解矛盾。因此，枚舉phi(W)的因數(shù)，再用快速冪判斷即可。

（9）Aug.25 『Citric杯』NOIP提高組模擬賽 II
第一題：這也太太太太太太太太太太太太太太太太坑爹了吧囧……其實題目描述有漏洞的，因為題目中并木有說表示結(jié)束的詢問一定是輸入的最后一個……
第三題：這題本沙茶的做法巨另類也巨繁瑣（就當字符串算法的綜合復習了囧……），首先一頭一尾兩段的字符串還是很好找的……結(jié)尾的那段直接枚舉長度，開頭的的那段可以在整個字符串左邊用一個類似KMP的辦法搞（其實只要知道KMP的原理就能用它解決N多奇特問題了囧……），難點在于中間的那段字符串，需要是一個長度為奇數(shù)的回文串。為了快速找出一段連續(xù)子串里最長的長度為奇數(shù)的回文串，可以設(shè)G[i]為以i為中心的最長回文串長度，這可以將整個字符串逆序一下后接在原串后面（注意中間要加一個未出現(xiàn)的字符），然后用后綴數(shù)組解決（經(jīng)典模型）。注意在找最長回文串的時候不能直接求中間G[i]的最大值，因為可能延伸出去，正解是二分枚舉這個長度，然后在中間不會延伸出去的那一段里找G的最大值，看是否符合要求。總時間復雜度O(NlogN)。

（10）Aug.26 RQNOJ2012年八月月賽
第二題：比賽的時候本沙茶用單調(diào)隊列硬搞搞不出來，后來寫樸素了（悲劇）……正解是將所有的前綴和按照先值遞增，再下標遞減排序，并串成Dancing Link，然后從按下標從大到小依次刪掉每個前綴和，這樣，每個前綴和左邊的那個一定是比值比它小的前綴和中值最大（值相同則下標最小）的那個，剩下就不解釋了囧……

（11）Aug.28 「Clover」杯NOIP模擬賽 III
第三題：先把每條無向邊拆成兩條有向邊，然后對這個有向圖求源點為1的單源最短路徑圖（就是由所有滿足D[i] + W<i, j> = D[j]的邊<i, j>組成的圖），顯然從這個圖的點1開始無論怎么走都是最短路徑，而且這個圖顯然是無環(huán)的（因為原圖中的每條邊權(quán)值都是正數(shù)，說實話，如果不滿足這個條件，這題就巨難做了，至少本沙茶不會做了），題目中要求的樹就是在這個新圖中從點1開始的一棵外向樹，由于這個新圖無環(huán)，所以只需要將每個點（除了1）都找一個父結(jié)點就行了，結(jié)果就是除1外的所有點入度之積。