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

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

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

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

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

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

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

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

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

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

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

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