Tips && Reminders


CDQ

  • DEBUG时可以看看合并前是否前驱条件都满足了,例如单调性等等,是否已经提前合并好了。
  • 如果在分治的时候对原数组的关键字相对位置进行了改动,记得下一次cdq的时候改回来。
  • 如果在cdq内不选择归并而是选择sort(log方了),那重复元素要小心了,因为快排不是一个稳定的排序。2h惨案
  • 对于重复元素的答案统计要慎重
  • 为了使传递的参数更加简洁,尽量使分治的一维与数组下标的数据范围是同阶的,尽量选择归并排序,实在不行再sort
  • dp的时候注意l==r的时候若无值再去赋值。
  • 注意边界限制

SAM

  • 千万tmd不要再忘了把lst初始化成rt了(已经犯了两次了。。。)
  • SAM的一个节点维护的是它缩起来边上的所有的点的信息。
  • 一个状态如果被访问到,那么它的par也一定可以被访问到。
  • 对于长度排序其实和拓扑排序是一个意味的。
  • 打tag的技巧。
  • 一个点所带来的不同子串的贡献是u.l - tr[u.p].l + 1;。
  • SAM上一个状态路径和一个长度信息就可以确定一个唯一的子串。
  • SAM前序遍历可以构造出SA。
  • SAM考虑问题的时候可以从ST,SAM两个角度入手,ST是点与par的缩起来的边的关系,可以考虑树形dp或者类似的东西,SAM则是子串一位一位的转移。
  • 一个套路是考虑在SAM上跑当前状态可以匹配的最长路径,然后打tag更新它的par
  • SAM的一个节点实际上是精简出来的最具有代表性的子串。
  • 倍增。
  • 广义后缀自动机离线可以BFS做。

FHQTreap

  • build的时候不要忘了剩下的点也要upd,同时注意更新根的数值
  • 记得pd哦
  • merge和split时候的upd

Network Flow

  • 无向图最大流。正反边流量相同即可。
  • 拆点限流。
  • 经典的切糕模型。
  • 利用网络流的方向不确定性进行分配
  • 最大匹配和最大权匹配问题

    二分图最大独立集,最小覆盖集
    这两个问题是对称的。
    最小点覆盖等价于最大匹配数目,这个很显然,考虑最小割就行了。
    一个独立即是独立集当且仅当它的补集是一个点覆盖集。
    最小点覆盖可以用最小割求,最大点独立集可以用最小割的补集。
    图连通的情况下,最小边覆盖等于总顶点数目减去最大匹配,数量上等于最大点独立集。
    考虑一条匹配边干掉两个点,剩下的点一条边干掉一个。那么总点数就是2*最大匹配+一条边干掉的数量。那么总点数减去最大匹配就是最小边覆盖了。*

  • 混合图欧拉回路。每个点的供应==需求。
  • 竞赛图 SGU326Perspective
  • 二分
  • 网络流与线性规划问题
  • 行列拆点
  • 棋盘黑白染色
  • 费用和流量非线性关系的费用流。可以考虑差分。

    例如容量c均为整数,每条弧有一个费用系数a,表示该弧流量为x时费用为ax^2。
    建模:每条边按照容量大小x拆成x条,容量依次为a,3a,5a,7a......因为最小费用最大流每次一定是先走最小费用的边,所以走的一定是先选小的边,而前k小的边的权和正好是ak^2,和原题的要求等价。

  • Candy那个题的技巧。整体减k然后进行分配
  • 贪心的技巧。如PA那个题,还有餐巾计划这个题。
  • 动态流问题。常常与时间有关,考虑动态加边。
  • 平面图最小割
  • 利用ST割表示方案
  • 二者选其一式
  • 最大权闭合子图
  • 考虑残余网络上的内容
  • 分段线性的费用流和分段非线性的费用流
  • 霍尔定理&&K正则二分图

    若一个二分图是K- 正则二分图, 则该图存在K 个不相交的完备匹配。
    设M(U1)为与U1中的点相连的点集,一个二分图U,V(|U|<=|V|)存在完美匹配,满足对于任意点集x∈U都有|M(X)|>=|X|
    必要性非常好证,充分性想想应该是对的qaq

  • 一些区间问题中,流往往对应着一个区间

Fail

  • Fail图是一个很适合去dp的东西,由于我们dp往往是一位一位转移的,可以对应到ac自动机状态的转移。
  • 由于一个点的Fail较fa的变化较小,我们可以可持久化线段树。
  • 后缀自动机清晰的表示出了每一个子串,一个长度和一个节点就可以表示出它。与它不同的是,AC自动机对于每一个节点它能表示的东西没有后缀自动机这么丰富,一个长度和一个节点往往代表着一类字符串。
  • 对于一个串,它的子串一定是某个后缀的前缀,或者某个前缀的后缀。在处理子串问题的时候,后缀自动机对于某一个串插入了每个后缀,这就很好办。但AC自动机并没有,它自动机里的模式串往往只能代表完整的一个串。Endtag = true意味着它fail树上到根的这条路径上的Endpos也都出现过了,这些点是它的后缀。AC自动机里的“某个后缀的前缀”是以不同的串的fail链表达的。
  • fail树里一个节点的子树和表示它的总出现次数
  • fail图上对于当前节点和儿子节点的fail的变动是很少的,儿子节点的fail大部分和当前节点是一样的,这令我们可以联想到利用一些可持久化数据结构来维护fail,特别是当字符集巨大的时候。
  • AC自动机往往适配于各种dp和矩阵乘法
  • 对于AC自动机我们有的时候可以预处理出来每个点到达的地方,后缀自动机则更不用说了,我们甚至还可以倍增。

  1. 在启发式合并和线段树合并,cdq分治等这样的树状结构时,维护有序数组,可以使用归并排序
  2. 一些化式子的题,能考虑组合意义的东西,化式子的时候多考虑组合意义
  3. 快排不是一个稳定的排序,所以有重复元素的时候要慎重使用,尤其是在cdq分治的时候

    此外cdq分治的时候一定要注意边界,而且注意对于重复元素答案的统计。

  4. n个点的lca只有O(n)个(这个玩意儿明明当时学虚树的时候看着了。。结果比赛的时候楞没想着)。考虑按照dfn排序,可以从两个角度证明,一个是rmq,一个是lca的类型。

    有了这个性质,在树上覆盖若干个点到根路径的并就可以转化成点的修改和两两lca的修改(这个过程也可以理解为两个两个路径合并起来),询问时转子树求和。写的时候注意去重和排序。

  5. 听说求凸壳不用极角排序,只需要以y为第一关键字x为第二关键字排序然后扫一遍就行了。
  6. 如果询问的两个参数都是一个连续的区间,那么这个询问可以看做对一个矩形的询问。这个区间可以是dfs序等等。
  7. 看到参数少的题目先打表是一个好习惯。
  8. 曼哈顿距离与切比雪夫距离的转化。
  9. *均摊分析。 这个东西我貌似得稍微知道点儿。。。至今我都不知道为什么板哥哥那个线段树是对的QAQ,我觉得zht那个主席树做法十分地靠谱啊。。。
  10. lca以后再写tm一次倍增我就请机房所有人喝粥。我爱树剖,爱得深沉。
  11. 利用st表和线段树优化连边
  12. 网络流时最小割的那个技巧:CEIL与CEIL-x的边权的设立。
  13. min(a,b) 等价于$\sum _i[i\leqslant a]\times [i\leqslant b] $
  14. 开-Wall有助身心健康。Warning有的时候要看一看,序列点什么的要注意一下,不能胡乱压行
  15. 求lcp在rmq的时候不要忘了++l。
  16. rmq不要忘了是个闭区间。。和倍增lca不太一样
  17. 倍增lca注意根节点深度要为1
  18. 升降幂与通常幂利用斯特林数的转化
  19. SAM记得开两倍空间。
  20. 单调栈不一定要退栈的时候统计增加的贡献,也可以记录前缀和,退栈统计负贡献
  21. 新访问计划里面,考虑方案其实是不变的;以及最小方差生成树里,考虑排列变化的时间节点是什么。
  22. Coin的思路,Flow考虑一个边什么时候会被割QAQ
  23. 可持久化的思想
  24. 线段树其实就是某种意义上的一个分治的过程。

· EOF ·

Comments
Write a Comment
  • 876066505 reply

    <marquee>2333</marquee>