D.
題意:
給一個初值C,和兩個迭代公式 fi(x)=a[i]*x/d[i]+b[i], 公式中1<=d<a<=20, 1<=b<=20,且都為整數(shù). 除法為整型除法.
由初值C開始迭代, 計算出來的結果又可以任意代入公式繼續(xù)迭代.
求能得到的所有數(shù)(包括C)中第N大的. 1<=N<=400000.
解:
一個隊列,兩個指針,不斷分別將指向的兩個值代入兩個公式計算,取小的加入列尾.注意判重.

G.
題意:
無向圖,頂點集為U, 給一個不包含源點v的子頂點集S, 問至少要在U-S-{v}中刪掉多少個點,才能完全割斷S與v的聯(lián)系. S中沒有點與v直接相鄰.
解:
限制頂點流量,最大流(最小割),將點i0拆成i->i',所有入邊指向i,出邊從i'指出.對有可能損壞的點,邊容量置1,不可能損壞的點置inf.其它邊容量為inf.

I.
題意:
給一個顏色序列s, 序列長度<=40000, 其中包含的顏色種類<=40000. 可以將原序列任意分割, 分割后每一個子段的代價分別為f(k)=k*k,其中k為子段中包含的顏色種類數(shù).
求一個分割方案,使sigma(f(k))最小.
解:
DP.關鍵的優(yōu)化在于,轉移dp[i]時,只用枚舉計算min{dp[j]+cost(j+1,i)},其中子段[j+1,i]中至多有upbound=ceil(sqrt(i))種不同顏色.因為代價函數(shù)是k^2,而長度為k的子段代價上界是k,所以枚舉的顏色數(shù)<=sqrt(k).
另顯然,顏色數(shù)都為m的所有可能區(qū)間[j+1,i],選擇最長的肯定最優(yōu).
因此維護pos[m],表示從當前掃描位置開始向左,顏色種類為m的最長區(qū)間的左端點.
為了更新pos[m],再設數(shù)組last[n],記錄上一次出現(xiàn)顏色n的位置.
若color[i]==color[i-1],則不更新pos; 否則,所有pos[k]>=last[color[i]]的區(qū)間內(nèi)顏色種類都變成k+1,因此將這段pos[1..m]右移,將pos[1]置為i.