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