本文移植自个人的原博客（原文）

BZOJ1023 SHOI2008 cactus仙人掌图

题意为求仙人掌图的直径。这题看起来完全没思路，最后看的题解。get了一种Tarjan的用法，先用其求出DFS树，用dp更新树边的直径最大值，考虑将其他非树边以环形dp更新，由于边的权值均为$1$，所以可以进行单调队列优化。其中利用到了仙人掌的一些性质。

BZOJ1024 SCOI2009 生日快乐

搜索，考虑切成$n$块后面积是一样的，那么实际上对于每一个切割后的蛋糕，需要继续处理的操作数的一定的，深搜即可。核心代码如下：

double work(double x,double y,int k)//x，y为长与宽，k为对于该块蛋糕剩余操作个数。
{
    if (k==1)return max(x,y)/min(x,y);
    double ans=inf;
    for(int i=1;i<k;++i)
    ans=min(ans,max(work(x,y/k*i,i),work(x,y/k*(k-i),k-i)));
    //取min是因为答案要求最小值，取max是因为属于同一块蛋糕。
    for(int i=1;i<k;++i)
    ans=min(ans,max(work(x/k*i,y,i),work(x/k*(k-i),y,k-i)));
    return ans;
}

BZOJ1025 SCOI2009 游戏

题意为给定$n$个元素，求在$n$的全排列的置换中的周期（即为各个循环节的公倍数），等价于$n$的整数拆分中的最小公倍数数量，直接枚举显然会超时，不妨用dp处理，枚举质因子以及幂即可。

BZOJ1026 SCOI2009 windy数

数位DP（一般是求在$[L,R]$之间有多少满足条件的数，然而并没有学过，膜的题解），先预处理有$k$位时，最高位为$i$时的答案，通过交集，并集的关系求一下即可。

BZOJ1027 JSOI2007 合金

构造题，已知$a+b+c=1$，可将第三维浓度去掉，那么目标浓度可由条件浓度转化而来，当且仅当

$$min(a_{condition}) < a_{target} < max(a_{condition})$$

$$min(b_{condition}) < b_{target} < max(b_{condition})$$

那么可以将其转化为二维平面的凸包问题，给定可选点，要求用最少的点使其凸包包含所有目标点。

BZOJ1028 JSOI2007 麻将

观察$n,m$的范围，可知贪心就能过。

BZOJ1029 JSOI2007 建筑抢修

还是贪心，涨自信题。

BZOJ1030 JSOI2007 文本生成器

AC自动机模板题，见博客DNA Sequence，不过这题$m$范围很小，而子串的长度更大，所以不需要矩阵快速幂（会TLE），直接DP即可。

BZOJ1031 JSOI2007 字符加密

后缀数组模板题，利用后缀的性质将条件串接到自己后面，这样就包换了所有情况，求sa即可。

BZOJ1032 JSOI2007 祖码

区间DP，标程没有考虑到连续消除的问题，导致数据都错了。

BZOJ1034 ZJOI2008 泡泡堂

贪心，对于最好情况，先将对手实力值与ZJ实力值排序，如果ZJ最低的实力值比对手最低的实力值大，那么为了战胜对手，将两者比试的代价最小，如果ZJ最高的实力值比对手最高的实力值大时，那么为了战胜对手，此时只要ZJ取一个比对手该实力值高的元素即可，为了方便，可以取最后一个。当两者均不满足时，则与对手实力值最高的元素比试总不能获胜，为了代价最小，将ZJ实力值最小的元素与其进行比试。