各种套路总结(不定期更新)

题解就咕了吧。

• 排列有关数数，有时顺序枚举数字插入很难转移，如果要求相对关系，尝试每次从未插入数字中选数插在末尾。[Similar Permutation]

• 网格图上 $1\times2$ 的长方形的长边平移及定点旋转相当于空位移动，且在对图黑白染色后空位的颜色不变，且黑白构成二分图。[The Beach](本题还能理解为二分图扩大匹配，是个费用流问题)

• 不连续子序列操作尝试转化为连续子段操作。[The Human Equation]

• 向区间连边可以为区间新建虚点。[Friendly Spiders]（当然也可以线段树优化）

• 过指定点的上升/下降子序列数量为 以该点为终点的升降序列数量 $\times$ 以该点为起点的升降序列数量。[CF1621G]

• 树上两条链有交的充要条件为：一条链的 LCA 在另一条链上。[清华集训2016] 数据交互