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

BZOJ1001 BeiJing2006 狼抓兔子

网络流裸题，考虑到边为双向边，建图时应同样将反向边赋值。同时也应加上反向弧优化（当流量为零时直接将点标记为不可达到即可）

BZOJ1002 FJOI2007 轮状病毒

最简单的方法是打表找规律，进阶一点是动态规划。其实这题跟基尔霍夫矩阵有关，然而还是找规律。（要加上高精度）

BZOJ1003 ZJOI2006 物流运输

一道DP题，转移方程为

$$f[i]=min(f[i],f[j]+k+t[j+1][i] * (i−j))$$

BZOJ1004 HNOI2008 Cards

Burnside引理裸题，题目中给定的限制满足将洗牌看作置换的条件。只要递推加DP求出每种置换下不变方案数即可。考虑到当两张牌在该置换下属于同一循环节时，不变方案要求两者颜色相同，做一下三维背包即可。

BZOJ1005 HNOI2008 明明的烦恼

purfer序列裸题，根据确定purfer序列的规则将度数的限制转化为在序列中的限制，求排列总数即可，对于分母需要求逆元，可以上高精度也可以分解质因数。

BZOJ1006 HNOI2008 神奇的国度

弦图裸题,见上篇博客。

BZOJ1007 HNOI2008 水平可见直线

以斜率维护双端队列，当两端元素被覆盖时出队，在将当前直线加入队列，最后剩下的即为答案。

BZOJ1008 HNOI2008 越狱

简单的快速幂，稍微推一下即可得到答案为

$$qpow(m,n)−(qpow(m−1,n−1)∗m)$$

BZOJ1009 HNOI2008 GT考试

用KMP和AC自动机皆可，KMP需要DP一下，AC自动机上模板就行。

BZOJ1011 HNOI2008 遥远的行星

简单的递推，考虑到题目中所说的限制和误差的条件，不妨在$j$大于一个限制时，将求$j$的受力公式化中的分母化为近似的$(A*j)/2j$即可。

BZOJ1012 JSOI2008 最大数

各种数据结构的裸题。

BZOJ1013 JSOI2008 球形空间产生器

高斯消元，提示中给出了两点间坐标公式，可以将每个给定的点与圆心坐标通过公式建立联系，再消掉公式右项中的半径，即可套用高斯消元算法。

BZOJ4801 BZOJ4月月赛打牌

考验基础的编程能力，每一轮的优先权是解题的关键，不妨将两人有牌权值相同时特殊处理一下，注意思路要清晰，最后注意下$A$的权值与价值不同，优先出牌的人可能故意输掉一局使得分尽可能大。

BZOJ4810 YNOI2017 由乃的玉米田

主要考察bitset的运用，但直接套用会明显会超时，需要莫队算法优化时间复杂度。

Luogu3708 洛谷四月月赛 koishi的数学题

设$g(x,i)=g(modi)$，则可以先打表算出$g(1,1)$到$g(n,n)$的值。观察矩阵可知，考虑$f(x−1)$对$f(x)$的贡献，可知两者的区别主要的不同取决于因子的不同，预处理一下即可。

BZOJ1015 JSOI2008 星球大战

考察并查集的应用，由于问题可以离线，可以将操作逆处理，将问题转变为熟悉的集合合并问题，再注意一下剪枝即可。

BZOJ1018 SHOI2008 堵塞的交通

分块+并查集，思想很简单(分块优化的暴力)，第一次实现这种数据结构，调了好久。正解是线段树维护每一列自身以及与相邻两列的连通性。考虑两点之间可能的联通方式，枚举所有可能的情况，完成所有操作。（比暴力还难写）

BZOJ1019 SHOI2008汉诺塔

第一眼看题先打表找了个规律，可知，$f[i]$（当前优先级下有$i$层时的答案）与$f[i−1]$线性相关，于是模拟出来前$20$项，递推出后十项。（正解为DP，严格遵循题目所给的要求（汉诺塔问题均有$f[i]=f[i−1]∗k+b$的递推式））

BZOJ1020 SHOI2008 安全的航线

典型的计算几何，可以二分可以迭代，具体按照莫涛的论文《迭代思想的应用》实现，但是还是TLE了。后来看题解get了求垂足的姿势，复习了一下求点与多边形包含关系的方法。（mark一下，复习时再敲一遍）

BZOJ1021 SHOI2008 循环的债务

题目可以进一步简化，即已知每个人初始金钱和构成。

Luogu3704 SDOI2017 数字表格

莫比乌斯反演的常见应用，见下篇博客。

BZOJ1049 HAOI2006 数字序列

很像暴力的动规，对于第一问，需要用到补集转化的思想，设 $f[i]$ 为前 $i$ 位的最多不变元素，那么 $f[i]$ 能由 $f[j]$ 转化而来当且仅当 $a[i]-a[j]>=i-j$, 即修改两者之间的 $i-j-1$ 个数使其严格递增，即两者之间只有$1$个元素不变，那么有

$$f[i]=\max (f[i], f[j]+1)(a[i]-a[j]>=i-j)$$

时间复杂度为 $O\left(n^{2}\right)$, 无法通过全部数据点，考虑进行优化，观察状态转移方程，易知可以通过减标号的方法转化成LIS问题，即可在 $O(n \log n)$ 的时间内求解。

对于第二问，为了简化问题，可以先设 $w(i, j)$ 为将从 $i$ 到 $j$ 的所有元素进行修改的最小代价，设 $g[i]$ 为前 $i$ 位的最小答案。那么根据第一问有

$$g[i]=\min (g[i], g[j]+w(j+1, i))(f[i]=f[j]+1)$$

对于 $w$ 的求解，可以记录每一个需要修改的元素的下一个和上一个不需要修改元素的位置，模拟即可。

Codefores286E Ladies’ Shop

根据题目所给条件，可知要求的 $p$ 个数一定在给定的 $n$ 个数中。

那么可以根据多项式乘法系数相乘，指数相加的特点，构造生成函数，并求出这 $n$ 个数可以组成的所有情况。已知某个 $n$ 集合中数 $a$ 可以由 $b+c+d$ 生成，那么根据题目中所给条件，可知一定有 $e$ 由 $c+d$ 生成，那么可以将 $a$ 看作由 $b+e$ 生成。

根据数学归纳法，易证

$p$ 个数可以选出一些集合（相同的数可重复选），其和可以组成所有给定的 $n$ 个数。（一）

与以下结论等价:

$p$ 个数可以选出任何两个元素（相同的数可重复选），其和可以组成所有给定的 $n$ 个数。（二）

那么生成函数的构造就显而易见了。（将幂作为权值，系数作为出现的次数，并将该生成函数与自身相乘，可以通过FFT优化)

对于第三个条件 (满足 $|p|$ 的阶最小)，可以结合以贪心的策略。如果生成函数中某项系数大于$1$且在给定集合 $|n|$ 中，则该元素一定可以由另外两个元素组成，那么就不将其加入集合 $|p|$ 中，否则将其加入集合 $|p|$ 中。

至于无解的判断，易知其等价于:

生成函数中某项系数不为零且该元素不在给定集合中。