D.
题意:
给一个初值C,和两个迭代公式 fi(x)=a[i]*x/d[i]+b[i], 公式中1<=d<a<=20, 1<=b<=20,且都为整数. 除法为整型除法.
由初值C开始迭代, 计算出来的结果又可以任意代入公式继续迭代.
求能得到的所有数(包括C)中第N大的. 1<=N<=400000.
解:
一个队列,两个指针,不断分别将指向的两个值代入两个公式计算,取小的加入列尾.注意判重.

G.
题意:
无向图,顶点集为U, 给一个不包含源点v的子顶点集S, 问至少要在U-S-{v}中删掉多少个点,才能完全割断S与v的联系. S中没有点与v直接相邻.
解:
限制顶点流量,最大流(最小割),将点i0拆成i->i',所有入边指向i,出边从i'指出.对有可能损坏的点,边容量置1,不可能损坏的点置inf.其它边容量为inf.

I.
题意:
给一个颜色序列s, 序列长度<=40000, 其中包含的颜色种类<=40000. 可以将原序列任意分割, 分割后每一个子段的代价分别为f(k)=k*k,其中k为子段中包含的颜色种类数.
求一个分割方案,使sigma(f(k))最小.
解:
DP.关键的优化在于,转移dp[i]时,只用枚举计算min{dp[j]+cost(j+1,i)},其中子段[j+1,i]中至多有upbound=ceil(sqrt(i))种不同颜色.因为代价函数是k^2,而长度为k的子段代价上界是k,所以枚举的颜色数<=sqrt(k).
另显然,颜色数都为m的所有可能区间[j+1,i],选择最长的肯定最优.
因此维护pos[m],表示从当前扫描位置开始向左,颜色种类为m的最长区间的左端点.
为了更新pos[m],再设数组last[n],记录上一次出现颜色n的位置.
若color[i]==color[i-1],则不更新pos; 否则,所有pos[k]>=last[color[i]]的区间内颜色种类都变成k+1,因此将这段pos[1..m]右移,将pos[1]置为i.