典例
JZOJ 6433. 【NOIP2019提高组正式赛day2】Emiya 家今天的饭&题解
类型
- 若干种中每种选取若干个， 保证每种不超过总数的一半的方案数。
思路
- 如果直接考虑递推转移，需要实时维护每种选择的个数，才能保证满足条件。
- 但是可以想到，若有某种超过了一半，其它的则不可能超过一半，用总方案数减去不合法的，枚举哪一种超过了一半，需要记录当前选了多少个，以及不合法的这种选择了多少。
- 还可以继续优化，因为总数不确定，不妨不记录总数，而记录不合法减去合法的个数，最后大于 0 0 0的部分说明不合法的超过了一半。
典例
JZOJ 6439. 【GDOI2020模拟01.17】小 ω 数排列&题解
JZOJ 4345. 【WC2016模拟】Fountain
类型
- 求相邻两数之间满足某种条件的排列方案数。
思路
- 考虑用DP依次加入每个数，不需要管当前已经加入的数构成的排列如何，可以只记录当前状态下的构成的“段数”。（因为题目限制只和相邻两数有关，所以已经被包含在中间的部分对后面没有影响）
- 每次加入时考虑自成一段、加在某一段的某侧、加在某两段中间并将他们合并.
- 如果题目有需要，可能还需要考虑是否加在最后整段的边界上（边界个数只可能为 0 / 1 / 2 0/1/2 0/1/2）
典例
JZOJ 3583. 【GDOI2014模拟】小A的树
类型
- 若干区间中数的位运算，可以推广到树上路径中的位运算。
思路
- 如果是加法或乘法，那么可以直接维护前缀和/前缀积，位运算不像加法和乘法，可以通过逆运算减法和除法得到特定的值。
- 但是如果拆位来看，与运算一定是前面一段连续的 1 1 1和后面一段连续的 0 0 0，或运算反之，这样就很好维护，最后再把每一位的答案加起来。
典例
JZOJ 3457. 【NOIP2013模拟联考3】沙耶的玩偶(doll)
类型
- 某种连边方式下，最小的路径条数覆盖所有点，每个点只能被一条路径覆盖。
思路
- 这种题可以反着想，最初每个点自成一条路径，每连一次路径条数减少 1 1 1，那么合并的次数越多，路径条数越少。
- 把所有的点分成入和出两边，能连边的两点之间出入连上，跑一边二分图最大匹配，用总点数减去最大匹配即为答案。
典例
JZOJ 5963. 【NOIP2018提高组D1T3】赛道修建
类型
- 树上符合特定条件（如路径点数、边权和达到某个值）的最大路径条数，每个边只能被一条路径覆盖。
思路
- 从叶子节点往上做，到每个节点时，它的每个儿子会各自从下方延伸了一条尚不符合条件的路径到它（若符合条件，可以直接断开，答案加 1 1 1）。
- 尽管路径再多，能继续向上延伸的也只有一条，剩下的在当前节点处两两匹配从而使它们尽可能多的对答案有贡献。
- 以最优的方式匹配完，然后剩余的中选择最优的（如果没有则从该节点直接延伸）向上延伸。
- 同时要注意虽然是以最优的方式两两匹配，但不能保证向上延伸的方案一定最优，最后还要重新扫一遍判断是否能有更劣却同样满足条件的匹配，使得延伸上去的路径更优。
典例
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_j\leq y_i,...) fj(xj≤xi,yj≤yi,...)。
- 把终点也视为一个不可经过的点，最后答案就是终点的 f f f值。
典例
JZOJ 6808. 【2020.10.29提高组模拟】easy&题解
类型
- 序列上统计符合某条件的区间个数，条件与区间最大值和最小值有关。
思路
- 这种题没有特别固定的解法，但大致可以用这种套路做。
- 枚举区间左/右端点，顺着或倒着扫一遍，用数据结构实时修改，并查询答案。
- 最值的修改可以用单调栈，弹栈时在数据结构上修改。
典例
JZOJ 6813. 【2020.10.05提高组模拟】送信
JZOJ 6276. 【noip提高组模拟1】树 &题解
类型
- 树上路径与经过点对的统计。
思路
- 考虑经过一个点对的条件，分两点为祖先关系或无祖先关系套路，用dfs序来看则可以转化为二维/三维偏序问题。
