Mato is No.1

     摘要: 原題地址本題就是，有N個變量，其取值只可能有三種：1、2、3。現在已知它們之間的一些大小關系，求有多少對變量(I, J)滿足(I的值+J的值)一定>或=或<(A的值+B的值)，A、B是指定的兩個變量，且I、J、A、B互不相同。首先，對于值相等的變量，直接建出無向圖，按連通塊縮點，再考慮大于/小于關系，如果I的值大于J則在I所在連通塊與J所在連通塊之間連一條有向邊（從I到J）…...  閱讀全文

RQNOJ187 巧置擋板
———————————————————————————————————————————————————
【背景（神犇不要囧視，3x）】
本沙茶最近開始猛攻搜索、近似、隨機等算法，目標是A掉AHOI2012的后3題（在哪跌倒就從哪爬起）。昨天晚上找到這題，發現是搜索，于是開始捉……結果被折騰了一晚上加一上午才A掉，不過，看在這題可以系統性的反映DFS優化的一般步驟，忍了……另外，這題是本沙茶在RQNOJ上通過的第400題……回想起通過第300題的時候已經是近三年半之前了……真頹廢啊……
———————————————————————————————————————————————————
普通DFS（不加迭代）的優化方法主要有：
（1）可行性剪枝，如果遇到已經無法產生可行解的情況就剪枝，有時候，可行性剪枝也可以指在搜索過程中對不合法情況的剔除；
（2）最優性剪枝：如果遇到已經無法產生比目前得到的最優解還要優的解的情況就剪枝，這其中包括啟發式最優性剪枝（即分支限界），對目前解的進展情況作樂觀估計，如果估計值都不能超越目前的最優解，則剪枝；
（3）通過改變搜索順序，盡早得出較優解，從而為后面的剪枝提供余地；
（4）通過預處理等手段，提前得到啟發值或者較優解，為后面的剪枝提供余地；

一般步驟：
（1）預處理，當然是寫在最前面，在搜索前得到啟發值等東東；
（2）搜索過程中，先寫最優性剪枝（包括已經到達搜索終點了，也應該判斷一下，提前排除不是最優解的情況）；
（3）再判定搜索終點，如果到了，也不要馬上更新解，而是要判定這個解是否符合要求，再更新；
（4）若未到終點，再寫可行性剪枝；
（5）最后寫搜索過程，包括需要改變搜索順序的情況。

注意事項：數組的分層問題。
這是一個很嚴重的問題，因為分層出錯很可能會導致一些很怪的錯誤出現，難以發現。在搜索題的調試技巧這一篇中，已經提到了這個問題，本題又涉及到了。
一般來說，搜索過程中使用的數組（包括變量，可以視為零維數組）可以分為以下三類：
（1）在搜索過程中，只會引用其值，不會修改的數組（比如預處理中得到的那些東東），相當于常量；
（2）在搜索過程中，會改變其值，但在搜索完畢后能改回原值的數組；
（3）在搜索過程中，會改變其值，且在搜索完畢后也改不回原值的數組。
對于（1）（2）類數組，不需分層，但對于第（3）類數組一定要分層。這是因為這些數組在多層搜索中都需要修改，而且搜索完了也改不回來，如果不分層，則當后面的搜索完畢以后，要繼續搜索前面的，引用的將是后面的值，就會出錯。
對于第（3）類數組，有的已經“自然分層”（每層搜索修改的元素都不一樣），比如本題代碼中的R[][]、C[][]。然而有的并沒有自然分層，比如本題的len、pos[]、tmp[]等，因此對于這些數組，需要再加一維，對于不同層使用該維不同的元素即可。

下面是本題的算法：
使用DFS搜索每個位置的擋板是否需要放。搜索時，先搜豎的再搜橫的，由于題目要求每個連通塊都必須是矩形，因此對于豎的，如果該位置的上方兩個相鄰位置的橫的沒有全放（包括只放了一個），則該位置的豎的放不放取決于其上一行對應位置的豎的有沒有放（第一行除外），如果兩個橫的都放了，則這里的豎的既可以放也可以不放（先搜不放的情況）。當然，一行的兩個1之間必須至少有一個豎的，這是可行性限制。在搜橫的的時候，按照該行所放的豎的，分成若干段，顯然每一段要么下面都用橫的封上，要么一個都不封上。其中，如果該段所在的連通塊里面有1，且下一行對應位置也有1，則必須封上；若該段所在連通塊里面沒有1，則不能封上（因為不能有一個連通塊里一個1都沒有），否則可以自由選擇封還是不封（當然也是先搜不封的）。這樣一直搜到最后一行的豎的后，還要判斷最后一行有沒有連通塊里沒1，若沒有，則為一個可行解。啟發式優化：設D[i]為第i行及以后至少要幾個擋板（若某行有K個1，則至少需要(K-1)個豎的；若某列有K個1，則至少需要(K-1)個橫的，累加起來即可，顯然這是樂觀估計），D[i]可以預處理出來，當做啟發值。

代碼：

原題地址
典型的二次遞推/DP的題目。
首先，題目中的“不便利值”指的是某個點到根的路徑上的木有被選定鏈覆蓋的邊的條數。

第一問：設F[i][0..2]分別為當子樹i中結點i的狀態為不參與鏈（0）、作為某鏈端點（1）、作為某鏈中間點（2）時，子樹i中的結點到i的最小不便利值。為了得到F，需要設立G[j][k(0..2)]表示結點i的前j棵子樹中，有k棵的根結點與結點i接上的最小的最大不便利值。顯然，不和i接上的，狀態為0、1、2都行，但不便利值要加1，而和i接上的狀態只能是0或1，不加1。

問題是第二問。第二問的難點在于，當i取得最小不便利值時，i的每個子結點并非都取到最小不便利值。舉個例子，結點i的最小不便利值為3，它的某個子結點j的最小不便利值為2，則當j與i接上時，子樹j的內部既可以取不便利值為2的解，也可以取不便利值為3的解。所以，為了解決第二問，需要求出結點i的最小不便利值為x的解的總數。萬幸的是，x的范圍并不是太大，可以證明，x不會超過log₃N（下取整），也就是當N=100000時x最大為10。因此，最后仍然不會T掉。

這題的一個啟示就是，在求類似于“最優解計數”的問題中，不要認為當后面的狀態取得最優解時，前面的狀態一定取得最優解。因此，不能只記錄某狀態取得最優解的個數，而要記錄該狀態取得每一個可行解時的個數。

代碼：

相關鏈接

由此看來，省隊（準確來說是“省集訓隊”）的壓力減小很多了囧……因為即使省選題目再坑爹，也有NOIP的40%墊著……
顯然，NOIP必須得高分，甩開別人，甩得越遠越好，這樣才能在省集訓隊的選拔中占據優勢……
不過，進了省集訓隊之后又腫么選，就不知道了……

而且估計明年的省選應該木有這么坑爹了囧……
其實……最近發現即使是AHOI2012的后3題，只要會各種搜索+近似也是可以搞到很多分的……至少加起來100分木問題（總分200就A隊了）……

所以，實力終究是硬道理！！！！！！！！！！！！！！！！！！！！！！！！！！！！

我要進省隊！！！！
我要進國家集訓隊！！！！

最近做了兩道LIS模型題，感覺到模型比較好，總結一下囧。
【1】[HAOI2007]上升序列
預處理：設F[i]為以i開頭的最長上升序列的長度，怎么求不用說了吧囧……
假設目前需要求長度為M的、標號字典序最小的上升序列，顯然其第一個元素A[i]必須滿足F[i]>=M（注意，不是等于，是大于等于！），找到滿足這個條件的最小的i即可。然后，設目前已經求出了該序列的第x個元素為A[y]，則第(x+1)個元素A[z]需要滿足的條件是A[z]>A[y]，且F[z]=F[y]-1，找到滿足這個條件的最小的z即為該序列的第(x+1)個元素。按照這種方法，掃描一遍就可以求出整個序列，時間復雜度為O(N)。如果整個序列的最長上升序列長度<M，則無解。

代碼：
【2】[HAOI2006]數字序列
首先，由于序列的所有元素都是整數，所以可以將原序列的所有元素減去它的下標，這樣就把上升序列轉化為不下降序列了。
第一問的結果顯然就是(N-新序列的最長不下降序列長度)。關鍵在于第二問。以下A均表示新序列。
設F[i]為以A[i]結尾的最長不下降序列長度（同樣，求法不用說了），G[i]為在A[i]不修改的前提下將A[0..i]轉變為不下降序列的最小修改量。首先求出F[i]，然后在求G[i]時，枚舉上一個“不動點”（就是不修改的元素）A[j]（顯然必須滿足A[j]<=A[i]且F[j]=F[i]-1），這樣最小修改量就是G[j]+(將A[j..i]轉變為不下降序列的最小修改量）。可以證明，A[j..i]的最優修改方案必然是將A[j+1..t]全部修改為A[j]，A[t+1..i]全部修改為A[i]，這里t是一個[j..i]范圍的值。問題就是如何求出最優的t？
一開始，假設t=j，即把A[j+1..i-1]全部修改為A[i]，計算出修改量，設為S。然后，由于A[j+1..i-1]之間的元素要么小于A[j]，要么大于A[i]（這個是顯然的囧），我們把小于A[j]的元素稱為“小數”，把大于A[i]的元素稱為“大數”，則當t取t0時，修改量為S-(A[i]-A[j])*(A[j+1..t0]中的“小數”個數減去“大數”個數）。這樣，只需掃描一下，求出使得(A[j+1..t0]中的“小數”個數減去“大數”個數）值最大的t0即可。
當然還有一個問題，對于同一個i，滿足“A[j]<=A[i]且F[j]=F[i]-1”的元素個數可能有很多，如果一個一個枚舉，一個一個掃描，會很慢的囧……解決方法是，求出滿足這個條件的j中最小的一個，設為j0，然后把A[j0+1..i-1]中的所有“小數”和“大數”全部處理出來，然后用類似前綴和的方法就能搞了囧……當然，為了找到j0，需要建一個二分圖，邊為(F[i], i)。
最后，為了方便，可以把A序列的左邊加一個-INF，右邊加一個+INF。最后總的時間復雜度，理論上為O(N²)，但由于是隨機數據，所以遠遠達不到這個級別。

代碼：

     摘要: 原題地址這個算法是由本沙茶在現場使用的那個做法擴展得來的……其實AC不了，后兩個點會因為常數過大而T掉……但在BZOJ上算總時間的話能AC……首先考慮樹的情形。設F[i]為從點i開始，往子樹i里面走，到達葉結點的期望長度，則很容易得到遞推公式：F[i] = (ΣF[j] + W(i, j)) / K，其中j是i的子結...  閱讀全文

最近參加了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₂(10¹⁸)，但如果每種顏色都最多只能和一種顏色相配腫么辦？因此這個需要特判：首先那些不能和任何顏色相配的肯定只能長度為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外的所有點入度之積。

從今天開始，本沙茶的這個空間重新啟用。
———————————————————————————————————————————————————
AHOI2012，恥辱的過去，
AHOI2013，光明的未來，
為了自己的集訓隊夢想，從今天開始，全力復仇！！！
———————————————————————————————————————————————————
以后這個空間里的文章題目都會以【AHOI2013復仇】為前綴……