组合计数
「THUPC2018」好图计数 / Count
- 挖掘"好图"所具有的性质——连通好图数等于非连通好图数
- 转化所求，所有好图 = 2 * 连通好图数
- 列出递推式，应用无标号计数的套路，方案数出现在指数上
- 搞出生成函数，应用多项式技巧，求对数后求导，再拆开观察每一项
- 简化式子
- 观察式子的卷积形式，一般可能会用到分治NTT
多项式
「PKUSC2018」神仙的游戏
- 观察性质和部分分，推出几个结论，给出一些启发性做法
- 考虑枚举border的长度，列出贡献式子
- 发现可以用卷积来优化一下
- 直接上NTT
「PKUSC2018」真实排名
- 观察性质，推出几个naive的结论
- 分类讨论，利用小结论可以直接做
- 不需要优化
数据结构
计算几何
「PKUSC2018」PKUSC
- 转化题意——根据期望的线性性，转为求每个点的贡献区间
- 考虑一般情况的贡献区间，找到关键——以原点为圆心过该点的圆和多边形的交
- 深入一般性做法，找到圆与多边形的所有交点，极角排序后去重
- 统计贡献，关键是判断每两个相邻点之间的线段在多边形内/外——一般简单多边形，射线法解决（不能用叉积）
- 考虑特殊情况，圆与多边形无交点，一种贡献为0，一种贡献为1。
- 更特殊的情况，点(0, 0)需要特殊考虑（有关题意中边界的开闭问题）
动态规划
「NOI2017」泳池
- 打出暴力（指数级/劣一点的dp）
- 定义一个优良的dp状态，列出dp式子
- 观察dp转移/bm打表找规律/猜测
- 发现是一个低次多项式，用Cayley-Hamilton解决
- 注意一些边界情况/简单情况
注意板子的鲁棒性考场上是否能快速准确实现
「PKUSC2018」星际穿越
- 打出暴力
- 观察该图论模型，发现一些性质以及走法的最优性
- 观察部分分，思考合理做法——预处理出一个可能有用的dp转移数组
- 通过转化简化询问，讨论一些情况，将询问与预处理的dp联系起来
- 发现优化途径——倍增
- 用相似的思想优化询问，省掉一个二分——直接二进制拆分
「PKUWC2018」随机算法
- 打出暴力并优化，期望得到不错的分数
- 找到一个优良的dp状态，列出转移方程
- 对于复杂的转移考虑是否不重不漏且合法转移（至少要是个DAG）
- 注意枚举顺序和方向
review
原文：https://www.cnblogs.com/psimonw/p/12052407.html
