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