水題就不說了囧……

【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本身不能算，另外，最短路圖其實應(yīng)該是個有向圖，但這里當做無向圖處理），只要對S、T所在的連通塊做Tarjan即可。
注意這里最短路的求法：SPFA或許也能過，但由于其不穩(wěn)定，在比賽的時候如果時間夠的話還是寫Dijk+heap吧囧……

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

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

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

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

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

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

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

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

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