和以前的總結(jié)一樣，那些是人都會(huì)搞的水題就不寫了囧……
【1】 Sept.29
「Poetize」杯NOIP模擬賽 VI第一題（TYVJ P1962）：
枚舉及其優(yōu)化。
設(shè)F[i][S]為買的方案為S（用10位二進(jìn)制表示）時(shí)，能不能表示出整數(shù)i（1<=i<=100），這個(gè)顯然可以預(yù)處理出來，然后將所有的狀態(tài)S按照“第一關(guān)鍵字為買的個(gè)數(shù)遞增，第二關(guān)鍵字為題目中的T遞增“排序。枚舉時(shí)，只需要按照排序后的順序從前到后枚舉狀態(tài)，找到第一個(gè)能表示出所有給出的整數(shù)的狀態(tài)即可。最壞情況下是10000*1024*10，會(huì)T，但題目中木有這樣的數(shù)據(jù)囧……
第二題（TYVJ P1963）：
DP，思想非常另類的那種……
每秒只有三種可能狀態(tài)：不進(jìn)行(0)、準(zhǔn)備進(jìn)行(1)、進(jìn)行(2)，且0的下一個(gè)狀態(tài)是0或1，1的下一個(gè)是2，2的下一個(gè)是2或0，所以，假設(shè)時(shí)間是順序的，設(shè)F[i][j][x]表示前i秒中狀態(tài)1或2的有j秒，第i秒的狀態(tài)是x的最大值……（剩下的不說了，注意第一個(gè)狀態(tài)必須是0或1）
下面考慮時(shí)間是環(huán)形的情況?？梢园l(fā)現(xiàn)，只要每?jī)蓚€(gè)相鄰狀態(tài)都滿足“0的下一個(gè)是0或1，1的下一個(gè)是2，2的下一個(gè)是2或0”，就是合法的，不過，最后一個(gè)狀態(tài)也有下一個(gè)狀態(tài)：第一個(gè)（因?yàn)闀r(shí)間環(huán)形）。
如果N=B，則所有的狀態(tài)都可以為1或2，只需要找到U值最小的那一秒，將它的狀態(tài)設(shè)為1，其它狀態(tài)設(shè)為2即可；（特判掉）
如果N>B，則必然有狀態(tài)為0，也就是可以從它開始。所以，時(shí)間仍然可以按照順序的看待，只是注意若第一個(gè)狀態(tài)是2，則最后一個(gè)狀態(tài)不能是0——將第一個(gè)狀態(tài)為0、1的與為2的分開處理即可。
注意，N=0與N=1時(shí)需要特判。
第三題（TYVJ P1964）：
為了描述方便，可以將這個(gè)序列在格子中表示，如下圖，表示序列(3, 4, 5, 4, 6, 3)：
設(shè)最終的序列中每個(gè)數(shù)都為S。以下起第S行為界，上方的黑格需要消去，下方的白格需要補(bǔ)上。由于題目中只允許每次對(duì)連續(xù)的一段加1或減1，也就是消去同一行連續(xù)的一段黑格或補(bǔ)上同一行連續(xù)的一段白格，所以，容易證明，此時(shí)的最少操作次數(shù)就是（下起第S行上方各行的連續(xù)黑格段數(shù)之和+下起第S行下方各行的連續(xù)白格段數(shù)之和）。因此，問題就是枚舉S并維護(hù)這個(gè)和值。
首先，預(yù)處理算出S=0的和值。此時(shí)只有黑格段沒有白格段。雖然行數(shù)很多，但本質(zhì)不同的行最多只有N個(gè)，所以可以在O(N)時(shí)間內(nèi)求出（當(dāng)然先要進(jìn)行一個(gè)O(NlogN)的排序）。具體求法就不說了囧……
然后，考慮當(dāng)S從0開始增加時(shí)，和值如何變化。顯然，S從x增加到x+1，和值的增量是(第x行的白格段數(shù)-第(x+1)行的黑格段數(shù))。由于每一行都是白段與黑段交替的，所以，若第x行與第(x+1)行本質(zhì)相同，則和值增量只可能是1（第x行最左邊和最右邊的格子都是白的）或0（第x行最左邊和最右邊的格子一白一黑）或-1（第x行最左邊和最右邊的格子都是黑的）。第一個(gè)和最后一個(gè)格子的顏色只與最初序列中第一個(gè)和最后一個(gè)數(shù)有關(guān)，且必然下起一開始若干行都是-1，然后是0，再然后是1……也就是和值一開始不斷減少，然后不變，然后不斷增加，那么，不變階段的和值就是最小值，其長(zhǎng)度就是最小值的個(gè)數(shù)；
問題是如果第x行到第(x+1)行發(fā)生改變腫么辦。此時(shí)，必然在原序列中有元素值為x，只需要把它們所在的位置的顏色從黑的改為白的即可。注意，在維護(hù)段數(shù)的時(shí)候，需要考慮到該格的相鄰的格子的顏色，還需要注意邊界。這樣的操作有N次，所以，時(shí)間復(fù)雜度是O(N)的。
綜上，可以求出在每一個(gè)本質(zhì)不變的行段內(nèi)的最小值及其個(gè)數(shù)，取最小的即可?？倳r(shí)間復(fù)雜度為O(NlogN)（最初的排序）。
【2】Oct.4
「Poetize」杯NOIP模擬賽 VII第三題（TYVJ P1993）：
注意到任意一個(gè)數(shù)能一步變換到達(dá)的數(shù)最多9*10+C(10, 2)=135個(gè)，只需要枚舉一下，然后用二分查找找出這個(gè)數(shù)在不在（不能用Hash，會(huì)扎堆），若在就連一條邊，然后求這個(gè)圖的s-t最短路即可，需要使用Dijk_heap（SPFA估計(jì)會(huì)被卡，注意手寫堆，不要priority_queue）。這樣對(duì)于題目中的數(shù)據(jù)可以卡線通過（最壞情況下仍然會(huì)T，估計(jì)正解是某種設(shè)計(jì)比較好的Hash）。注意，使用DL邊表時(shí)，需要在空間上作一些優(yōu)化，否則可能MLE。
【3】Oct.20
Tyvj三周年邀請(qǐng)賽 第一題（TYVJ P2011）：
壓位即可。
第三題（TYVJ P2013）：
首先轉(zhuǎn)移方程是很好搞的……F[i]為前i個(gè)數(shù)的最大權(quán)值，則F[i]=max{F[i-1], F[j]+A[j+1]*B[i], 0<=j<=i-2}，邊界：F[0]=F[1]=0。問題是如何優(yōu)化。
首先，由于A、B序列木有單調(diào)性，一般的斜率優(yōu)化是不行的囧……
注意F[j]+A[j+1]*B[i]，當(dāng)F[j]求出來之后，這個(gè)其實(shí)是一個(gè)自變量為B[i]的一次函數(shù)，也就是一條直線（斜率A[j+1]，縱截距F[j]），而且，由于B非負(fù)，所以這其實(shí)只是這條直線在y軸右側(cè)的部分（射線！?。?br />本題需要維護(hù)的就是這些射線組成的下凸殼。注意，F(xiàn)數(shù)組是遞增的，也就是插入的射線的縱截距遞增。這樣，插入射線y=A[j+1]*x+F[j](x>=0)時(shí)，(0, F[j])這個(gè)點(diǎn)要么在原來的凸殼上（如果大于上一個(gè)F[j]），要么在原來的凸殼內(nèi)部。
如果在內(nèi)部，則這條射線與原來的凸殼最多只有一個(gè)交點(diǎn)，因此只需要從左到右掃描原來的凸殼的邊（這些邊除了最右一條是射線外，其余都是線段），將一開始的在待插入射線下方的邊都刪去，直到找到一條邊與該射線相交或者所有部分都刪去為止。若某條邊與待插入射線相交，則刪去它在待插入射線下方的部分，再插入新射線，否則直接插入新射線；
如果在凸殼上，那么新射線有兩種可能：一是斜率不大于上一條射線的斜率，此時(shí)該射線完全在凸殼外或凸殼上，直接舍棄；二是斜率大于上一條直線的斜率，此時(shí)，把原來凸殼上最左的那條邊刪掉，再按照內(nèi)部的情況處理即可；
求F[i]時(shí)，找到x=B[i]與凸殼的交點(diǎn)即可；
顯然，這些邊可以用一個(gè)棧來維護(hù)（本沙茶一開始以為是隊(duì)列，寫完了以后才發(fā)現(xiàn)是棧……于是代碼中按照隊(duì)列的格式來寫的囧……），每條射線最多進(jìn)棧一次，出棧一次，加上二分查找的時(shí)間，總時(shí)間復(fù)雜度O(NlogN)。
寫的時(shí)候注意一些細(xì)節(jié)，尤其要注意的是，算出F[i]后不能馬上插入射線i，而要在F[i+1]算出后才能插入，因?yàn)閖<=i-2?。。ㄍ瑯拥?，一開始也只能插入0，不能插入1）
代碼：
P1962 P1963 P1964 P1993 P2013