动态规划相关
典例
2019 CSP-S Day2-T1 Emiya 家今天的饭&题解
类型
- 若干种中每种选取若干个， 保证每种不超过总数的一半的方案数。
思路
- 如果直接考虑递推转移，需要实时维护每种选择的个数，才能保证满足条件。
- 但是可以想到，若有某种超过了一半，其它的则不可能超过一半，用总方案数减去不合法的，枚举哪一种超过了一半，需要记录当前选了多少个，以及不合法的这种选择了多少。
- 还可以继续优化，因为总数不确定，不妨不记录总数，而记录不合法减去合法的个数，最后大于 0 0 0的部分说明不合法的超过了一半。
典例
JZOJ 6439. 【GDOI2020模拟01.17】小 ω 数排列&题解
JZOJ 4345. 【WC2016模拟】Fountain
类型
- 求相邻两数之间满足某种条件的排列方案数。
思路
- 考虑用DP依次加入每个数，不需要管当前已经加入的数构成的排列如何，可以只记录当前状态下的构成的“段数”。（因为题目限制只和相邻两数有关，所以已经被包含在中间的部分对后面没有影响）
- 每次加入时考虑自成一段、加在某一段的某侧、加在某两段中间并将他们合并。
- 如果题目需要，还要加入一维状态表示是否加在最后整段的左/右边界上（边界个数只可能为 0 / 1 / 2 0/1/2 0/1/2）。
典例
JZOJ 6809. 【2020.10.29提高组模拟】不难题&题解
类型
- 二维或多维空间中每个维度只能向某个方向走，其中若干点不能经过，求到达某个点的方案数。
思路
- 容斥，设 f i f_i fi表示只经过了第 i i i个不能经过的点的方案数，用到达它的总方案减去其它 f j ( x j ≤ x i , y j ≤ y i , . . . ) f_j(x_j leq x_i,y_jleq y_i,...) fj(xj≤xi,yj≤yi,...)。
- 把终点也视为一个不可经过的点，最后答案就是终点的 f f f值。
树相关
典例
类型
- 树上符合特定条件（如路径点数、边权和达到某个值）的最大路径条数，每个边只能被一条路径覆盖。
思路
- 从叶子节点往上做，到每个节点时，它的每个儿子会各自从下方延伸了一条尚不符合条件的路径到它（若符合条件，可以直接断开，答案加 1 1 1）。
- 尽管路径再多，能继续向上延伸的也只有一条，剩下的在当前节点处两两匹配从而使它们尽可能多的对答案有贡献。
- 以最优的方式匹配完，然后剩余的中选择最优的（如果没有则从该节点直接延伸）向上延伸。
- 同时要注意虽然是以最优的方式两两匹配，但不能保证向上延伸的方案一定最优，最后还要重新扫一遍判断是否能有更劣却同样满足条件的匹配，使得延伸上去的路径更优。
典例
JZOJ 6813. 【2020.10.05提高组模拟】送信
JZOJ 6276. 【noip提高组模拟1】树 &题解
JZOJ 6874. 【2020.11.19提高组模拟】ZYT的答案
类型
- 树上有限制的路径计数或最优路径方案，限制与路径经过点对有关。
思路
- 考虑经过一个点对的条件，分两点为祖先关系或无祖先关系讨论，用dfs序来看则可以转化为二维/三维偏序问题。
- 其中要特别注意的是，当点对互为祖先关系时，不妨设 ( x , y ) (x,y) (x,y)中 x x x是 y y y的祖先，并不是只有 y y y子树内连接 x x x子树外的路径能经过点对 ( x , y ) (x,y) (x,y)，而是 y y y子树内连接 x x x的到 y y y路径上的那个儿子子树外的路径能经过点对 ( x , y ) (x,y) (x,y)。
典例
JZOJ 1166. 树中点对距离
JZOJ 6866. 【2020.11.16提高组模拟】路径大小差&题解
类型
- 树上符合某条件的路径计数，路径条件的判断能由子路径合并判断。
思路
- 点分治，过程中可能会算重同一棵子树内的两条路径组合，需要减去。
计数相关
- 动态规划相关、树相关中也有部分该类型的题，在此分类下便不再提及。
典例
JZOJ 6808. 【2020.10.29提高组模拟】easy&题解
类型
- 序列上统计符合某条件的区间个数，条件与区间最大值和最小值有关。
思路
- 这种题没有特别固定的解法，但大致可以用这种套路做。
- 枚举区间左/右端点，顺着或倒着扫一遍，用数据结构实时修改，并查询答案。
- 最值的修改可以用单调栈，弹栈时在数据结构上修改。
杂类
典例
类型
- 若干区间中数的位运算，可以推广到树上路径中的位运算。
思路
- 如果是加法或乘法，那么可以直接维护前缀和/前缀积，位运算不像加法和乘法，可以通过逆运算减法和除法得到特定的值。
- 但是如果拆位来看，与运算一定是前面一段连续的 1 1 1和后面一段连续的 0 0 0，或运算反之，这样就很好维护，最后再把每一位的答案加起来。
典例
JZOJ 3457. 【NOIP2013模拟联考3】沙耶的玩偶(doll)
类型
- 某种连边方式下，最小的路径条数覆盖所有点，每个点只能被一条路径覆盖。
思路
- 这种题可以反着想，最初每个点自成一条路径，每连一次路径条数减少 1 1 1，那么合并的次数越多，路径条数越少。
- 把所有的点分成入和出两边，能连边的两点之间出入连上，跑一边二分图最大匹配，用总点数减去最大匹配即为答案。
典例
类型
- 矩阵乘法快速维护DP，但转移矩阵过大。
思路
- 情况一：转移矩阵过大，但矩阵中会有一大部分为 0 0 0的的不合法状态，可以直接把有用的状态记下来直接转移有用的地方。
- 情况二：对于若干对不同的转移，从题目本身的意义上它们矩阵中对应的数相同，则可以只记录每种真正不同转移之间的答案。