Mato is No.1

水題就不說了囧……

【1】Oct.30 TYVJ “掃地”杯III NOIP2012模擬賽 day1
（本沙茶這個其實木有參加，是之后捉的……還好AK了囧……Orz liouzhou_101！！）
第一題：
若n=1，則只有當y=x*x時才有唯一解x（這個一定要特判）；
若n>1，由柯西不等式得(a₂²+a₃²+...+a_n²)(1+1+...1（n-1個1）) >= (a₂*1+a₃*1+...+a_n*1)²，
即(n-1)(y-a₁²)>=(x-a₁)²，當且僅當a₂~a_n全部相等時等號成立。
顯然a1的最大、小值一定是零點，也就是求方程(n-1)(y-a₁²)=(x-a₁)²的解的問題，若Δ<0則無解，否則求兩解之積，可用Vieta定理得出。

第三題：
先求出最短路圖（求出S到每個點的最短距離dist0[]和每個點到T的最短距離dist1[]，然后邊<i, j>屬于最短路圖當且僅當dist0[i]+<i, j>長度+dist1[j]等于S-T最短路長），然后那些能炸掉的點就是最短路圖的S-T割點（當然S、T本身不能算，另外，最短路圖其實應該是個有向圖，但這里當做無向圖處理），只要對S、T所在的連通塊做Tarjan即可。
注意這里最短路的求法：SPFA或許也能過，但由于其不穩定，在比賽的時候如果時間夠的話還是寫Dijk+heap吧囧……

【2】Nov.2 TYVJ 「Clover 10」杯HE兩校聯賽(第二輪Day1)
（這個也木有參加，是之后捉的……另外說一下，第二題的題目描述與數據不符）
第三題：
正解見This_poet神犇的空間。
這里說一下本沙茶的方法（70分）：
設F[i][s]表示對X[1..i]進行設置，范圍是[1..s]，且從1能夠“走出去”（走到大于i的結點）的方案總數，這里有s>i。
枚舉“指出去”（X值大于i）的最小的結點為j（1<=j<=i），則有
F[i][s]=∑(F[j-1][i] * (s-i) * s^i-j)，1<=j<=i。
邊界：F[0][i]=1（本身木有意義，在乘的時候作為單位元）
這很容易理解。j是要指出去的，因此i+1<=X[j]<=s，有(s-i)種；對于X[1..j-1]，由于j是指出去的最小結點，所以它們都不能指出去，X值范圍1..i，但是它們必須“指出j-1"，就是走到j及其后面的部分，否則就會被困住，自然也就走不出去了，所以是F[j-1][i]；對于j+1..i，它們可以隨便指，1<=X值<=S，因此是s^i-j。
但是，這個遞推式再也無法優化下去了，題目要求O(N²)顯然無法辦到。
而在正解中，我們關心的不是從1能不能走出i，而是從1最遠能走到哪里。這時列出來的遞推式就很容易優化到O(N²)。所以，在遞推和DP問題中，思路的不同，將會引發完全不同的結果，當一個遞推式/轉移方程無法優化下去的時候，可以換一個思路來求解。

【3】Nov.3 TYVJ 「Nescafé 29」杯HE兩校聯賽(第二輪Day2)
第一題：
二分r，求出每個半圓能覆蓋到的線段，再看這些線段的并是否為[0, x0]即可。問題就是求線段并的操作是比較易疵的。
首先將所有線段按照左端點遞增排序，然后掃描每條線段，并記錄目前線段達到的最右位置（就是右端點最大值）maxr，若某條線段的左端點大于前面的maxr則不能覆蓋，掃描完了以后，再看第一條線段的左端點和所有線段的maxr是否符合要求即可。
但是，對于本題要注意：（1）由于有可能相離，因此最后的線段數可能不足N條，尤其要注意一條線段都木有的情況；（2）（極其易疵）題目只要求覆蓋線段[0, x0]即可，因此，即使在x0右邊發現了中斷處（左端點大于前面maxr），也木有關系！！（本沙茶當時就在這里搞疵了，跪了2個點）；

第二題：
本沙茶當時使用搜索騙的……可是它的數據實在太弱，本該AC的（最后還是跪了一個點，原因是卡時：ZZZ = ?? / m0，忘了考慮m0=0的情況）；
首先求出圖的每個連通塊，如果某連通塊內的所有結點初始權值之和不為零，無解。否則求出這個圖的最小生成森林（用Kruskal），作為初始解（其實很多情況下這就是最優解囧）。
然后開始DFS，使用改變搜索順序優化：先考查兩端點權值都不為零且為相反數的邊（因為轉移之后可產生兩個0點），再考查兩端點權值都不為零且不為相反數的邊（轉移之后可產生一個0點，注意雙向轉移），最后考查兩端點權值有一個為零的邊（將0點轉移，不會產生新的零點），其它的決策顯然不明智。此外每條邊只能轉移一次。
當然直接這樣搜肯定是要T的，但最優解會很快求出，因此可以卡掉。這題可以加啟發函數，但本沙茶不加也木有事囧……

第三題：
遞推式不說了。注意滿足條件的樹的高度的范圍其實很小（<=16），所以在找到高度上下界之后是不會T的。注意對于結果小于10^8的處理（不需輸出多余的0），此時N<=34；

【4】Nov.5 VIJOS NOIP2012模擬賽第三彈
第一題：
容易證明，最優解中蟲洞的左端點一定是最左的點。
二分最大距離dist，然后離最左的點距離<=dist的顯然都能走到，>dist的則只能使用蟲洞。設離最左的點距離>dist的左起第一個點為S，則從S往右枚舉每個點為蟲洞右端點時，離S的距離和離最右點的距離是否都不大于dist，若都小于，則右端點可以在這里，dist符合條件。

【5】Nov.7 TYVJ NOIP2012提高組模擬賽day1
全是水題，不說了。注意第二題是保留整數而不是四舍五入，第三題的“差”不是“差的絕對值”！！！！！！！！！！！！！！！

【6】Nov.8 TYVJ 「Poetize 10」杯NOIP2012提高組模擬賽day2
第一題：
首先要模型轉化一下，題目就是：在一棵樹上，每個結點都有一個權值，除根結點外，每個結點都有一個容量（這個容量在題目中是體現在父邊上的），選定若干結點，使得樹中除根結點外的每個結點子樹中選定結點的權值之和都不大于其容量，問最多能選多少結點。
由于數據范圍小，本沙茶用類似樹形背包的DP硬搞掉了，其實是可以貪心的囧……將結點按權值遞增排序，每次選擇一個所有祖先容量全部足夠的權值最小的結點，最后得到的一定是最優解。
證明：由于決策之間不互相影響，最優子結構性質顯然滿足，下證貪心選擇性質。設目前所有祖先容量全部足夠的權值最小的結點為A，某方案中權值比A小的結點的選定情況（就是之前的狀態）與選A的方案相同，但木有選A。設該方案中選定的權值不小于A且與A的LCA深度最大的結點為B，LCA(A, B)=P，由于B的權值不小于A，所以若將B刪掉，A選上，其到根的路徑上P及其以上的部分顯然不會超過容量限制，對于P以下的部分，由于P是最深的LCA，因此P以下的部分根本木有被權值不小與A的結點所占用，因此肯定也不會有事，所以，將B刪掉、A選上，將得到一個不比原方案差的可行方案，所以貪心選擇性質滿足。綜上，貪心算法是正確的。

第二題：
先將區間按照右端點遞增排序，然后掃描：設目前區間的右端點為r，上一個區間的右端點為r0（這里忽略右端點相同的情況，即必有r>r0），則在[r0+1, r]這一段里的最優解有兩種可能：（1）若目前區間及其之后的區間內有左端點小于r的，則最優解為r；（2）若目前區間及其之后的區間的左端點全部不小于r，則[r0+1, r]這一段里各個值的能量總和均相同，為保證最小，最優解為r0+1。
接下來的問題是如何快速求出E=r或r0+1時的能量總和。顯然在之前的區間里都不能獲得能量，后面的區間內，左端點小于等于E的區間的能量為左端點的值，否則為E。由于前面的區間的右端點都小于E，左端點自然小于等于E，所以“后面的區間內，左端點小于等于E的區間個數”就是全部區間內左端點小于等于E的區間個數，這個可以在預處理中將所有左端點遞增排序之后用二分查找得出，這些區間的左端點和值也可以記錄一個S值來得出，而左端點不小于E的區間個數就是(該區間及其后面的區間總數-左端點小于等于E的區間個數)。
總時間復雜度O(NlogN)；

第三題：
這個題真是折騰死人了囧……其實做法很簡單，但巨難想到……
首先把待匹配字符串（設為A，匹配串設為B）展開成2倍的形式，所有的循環串就是所有長度為N的子串了囧……
設F[i][j]為A（展開后的）第i個字符往前，至少到哪才能與B[0..j]匹配（也就是所有能與B[0..j]匹配的A[k..i]中的k的最大值）。顯然這樣一說，轉移方程就出來了囧：
若B[j]="*"，則F[i][j]=max{F[k][j-1], k<=i}
若B[j]≠“*”，則F[i][j]=F[i-1][j-1]（當A[i]=B[j]時）或-INF（當A[i]≠B[j]時），注意邊界：j=0時，B[j]必為"*"（根據下面的假設），此時F[i][j]=i+1（不是i！！為了后面的決策），而i=0時，若B[0..j]均為“*”則為1（不是0，同理）否則為-INF。
對于max{F[k][j-1], k<=i}這里，顯然可以用輔助數組搞定，注意輔助數組是要滾動的，否則會MLE（其實F也可以滾動）；
接下來，若B[0]="*"，則求出F之后只需要看對于每個i（i>=N-1，N為原長），F[i][M-1]（M為B的長度）是否>=i-N+1即可，因為前面的部分都可以用這個*干掉。
若B[0]≠"*"，則將B最前面的不為"*"的部分拿出來，顯然這里是要硬性匹配的，因此先求出這里能匹配A的哪些位置（KMP用不用都可以），B剩下的部分按照B[0]="*"處理，只是最后在找的時候只能找原來B前面硬性匹配的部分可以配上的位置。
若B里面木有"*"，就是普通的字符串匹配的問題了，直接特判掉（同樣不必KMP）。這個比較容易漏掉。
總時間復雜度O(NM)。