SDOI2008

【Sandy的卡片】

经典的最长不重子串。二分+后缀数组

【山贼集团】

树形DP
令F[i,j]表示第i个点在其子树中山贼选取的状态为j所能获得的最大收益。
这里有个求所有子集的trick就是
for (int k=j; k; k=(k-1)&j) balabala....
原理什么的推一下就可以了。很方便

【郁闷的小J】

offline 把相同种类的询问及修改按时间顺序排序,用树状数组维护即可。
online 线段树套平衡树

【烧水问题】

神题。找规律,最后发现时Catalan数列

【沙拉公主的困惑】

gcd(a,b)=gcd(a+b,a)
所以如果k与M!互质,那么k+M!与M!一定互质。那么在N!中共有(N!/M!)组不同的数。
每一组的个数是phi(M!)
所以最后结果是N!(小于M的素数减一之积)/(小于M的素数之积)

【Sue的小球】

F[i,j,0..1]表示目前已经扫荡了i到j的所有小球,目前在i(或者j)处能够获得的最大价值。
转移时将后面所有球的代价计算后提前减去即可。

【洞穴勘测】

裸动态树

【递归数列】

简单的构造矩阵,快速幂优化。
F[si,ai,ai-1,ai-2,...,ai-k+1]=balabala...

【石子合并】

神奇的贪心+数据结构
见楼教男人八题

【红黑树】

从dp角度上来看还是蛮简单的。
观察到红黑树有一个性质:最长路径至多是到前端节点最短路径的2倍,可以保证树高。
所以F[i,h,0..1]表示当前子树有i个节点树高为h且当前节点是红色(或黑色)的最大/最小红色节点数量。递推即可。

【棋盘控制】

见CQF Soldier解题报告
旋转后用线段树维护。

【立方体覆盖】

裸的矩形切割。

【校门外的区间】

裸的线段树。注意到所有操作均可以用取反或者置0/1表示。