模型(套路)总结

1:序列部分

<1>:一个序列,有些位置确定,有些位置不确定。你要钦定未知位置的数,使得LIS最大。(bzoj5427)
solution:考虑普通的LIS,维护f[i]表示长度为i的LIS的最小值。直接维护dp数组,如果位置固定,直接转移。否则考虑任意一个位置都可以补充。f[i] = min(f[i], f[i - 1] + 1); 维护一个delta代表移动了多少位就行。

<2>:区间修改转差分。(ezoj1842)

<3>:区间内取最少数让他们和超过一个值。
显然尽量取大。二分选的最小值,然后就是区间>=最小值的和。主席树可以做。

<4>:静态区间不同数的个数。 离线,把询问按照R从小到大排序。树状数组维护相同的值的最后一次出现的位置。查询就是查询两个前缀和相减一下。

2:树上部分

<1>:子树修改子树询问:
①:搞出dfs序,变成序列问题
②:暴力树剖变成序列问题
③:考虑贡献和影响,也是序列问题

<2>:树链的问题
①:树上倍增+LCA
②:点分治
③:暴力树剖变成序列问题

<3>:异或相关
①:考虑任何一个环都可以通过一条路径异或上简单环得到。简单环可以钦定一个点为根,做出dfs树。返祖边就形成了环。把这些环拿出来求线性基。。。
②:求出树到根的路径异或和,那么任意两点间的路径就是这两个前缀和异或起来,然后就变成了点对问题。可以用树剖什么维护。
③:如果你之前已经确定了某些位,而且你期望当前这一位是什么。那么所期望的是一段连续区间,可以用主席树等维护这一段是否存在数值。(loj2016)

<4>:树剖
①:点有点权,直接剖。
②:边有边权,确定一个点为根。把一条边的边权下放到它的儿子上作为点权。

3:图上部分
<1>:网络流
①:最大流—最小割

  • 考虑你有一些限制,是要么这个一定选,要么那个一定选。这个可以转成最小割。
  • 考虑你如果选了A,就不能选B。可以一开始都选,然后放弃一个。也是最小割。(p2774)

②:最大权闭合子图(http://zhengruioi.com/contest/233/problem/603)
考虑有一些限制,选了这个另一个一定选。这个也可以转成最小割。
③:最小费用最大流(bzoj5222)
一个点加1,一个点减1。有一定的代价,你要花费最少的代价使得点全正。
(S向正点,负点向T。代价为0,流量为绝对值。中间能匹配的点连边,流量无穷,代价为真。最后跑MCMF,判断负点连起来的边是否满流。)
④:流量平衡限制出入平衡:
把一个点xxx拆成两个点x1,x2x1,x2x1,x2,x1&gt;x2x1-&gt;x2x1−>x2。如果x&gt;yx-&gt;yx−>y,那么连一条x1&gt;y2x1-&gt;y2x1−>y2的边。考虑如果xxx的入度是kkk的话,那么x2x2x2就少流出了kkk,y2y2y2就多流出了kkk。求最大流就可以保证入度等于出度。
⑤:网格图上一个选了行点另外一个列点必选。问最多选多少?
二分图最大匹配的模型。(p2825)

<2>:对偶图
咕咕咕

<3>:分层图
分层转移就好了。

<4>:拆点法
一个点拆成入点和出点,中间一条边。那么删除一个点就转化成删除一条边。

<5>:删边
①:对于删边操作支持离线。可以倒过来,就变成了只有加边;
②:线段树。线段树上每一个节点维护一个联通情况。同样是不考虑删边。
③:LCT
④:CDQ分治+可撤销并查集
⑤:线段树分治+可撤销并查集(loj121)

<6>:2-SAT
考虑你有若干个限制。形如A选B不选,A不选B选。AB选的情况一定不同,AB选的情况一定相同,A一定选,B一定不选。你要构造一种合法方案使得满足所有的限制。
sol:构造点表示选或者不选。按照逻辑推断关系建边,不允许出现矛盾的关系在一个scc里面。用tarjan求过之后,

4:数学部分

<1>博弈论
转化转化转化
①:考虑先手必胜的后手存在先手必败,先手必败的后手全是先手必胜。只要找到一个等价的关系就可以了

②:sg函数(dp)。依赖于①来进行转移。游戏的和的sg值是每个子游戏的sg值的xorxorxor和。游戏的sg值是它后继状态sg值的mex。

③:转化。如果奇/偶的情况比较好处理。可以考虑奇变偶或者偶变奇。

④:考虑写出把两个限制变成两个坐标轴上的点。考虑在二维平面上的移动。

⑤:dp出规律。大力打表。
经典模型:普通nim,阶梯nim,DAG上问题。

<2>如果模数比较大且可以分解,可以把模数分解成若干个因子的乘积。对每个因子分别取模之后再CRT合并。(古代猪文)

上一篇:WaWa的奇妙冒险(第七周集训自闭现场)


下一篇:HDU 3404 Switch light (Nim积)