一些自己看的的OI小知识

  1. 判断某个数能否由一些数组成可以先对数进行排序然后使用设 \(f_x\) 表示 \(x\) 是否能被组成,然后对于前 \(i\) 个数就有 \(f_x=f_x | f_{x-a_i}\) ,具体题目是 \(noip2018\) \(day1t2\)

  2. 你去删除一个元素的时候可以不用说去真正的移除,你可以用一个并查集来标记像后方,表示被移除。并查集进行打标记是一个很有用的思路。

  3. 实在遇到不会做的题,考虑一下 dp,即使不是正解也绝对没错,如果是在树上做 dp ,不要但考虑在链上的不如直接考虑树上 dp。

  4. 遇到要求问方案数,没事就容斥一下,说不定就弄出来了。

  5. 求某个节点在某个方向上的直接儿子,改为求方向上节点 \(v\) 的 \(dep_v-dep_u-1\) 级祖先

  6. \(\sum_{i=1}^n i^2 = \dfrac{n(n+1)(2n+1)}{6}\)

  7. 裴蜀定理同样适用于多元,\(ax+by+cd=t\) 要求 \(t|(a,b,c)\)

  8. 判断 \(x\) 是否为 \(y\) 的 祖先,可以记录 dfs 序进行判断,看一下对于 \(x\) 的 \(dfs\) 序区间是否包含 \(y\) 就行了。

  9. 二项式反演:考虑求恰好 \(k\) 个物品的时候,可以按下面两种方法来做。

    设 \(f_i\) 表示至少 \(i\) 个物品时的答案, \(g_i\) 为恰好 \(i\) 个物品时的答案。

    然后 \(f_k=\sum\limits_{i=k}^n\displaystyle\binom{i}{k}g_i\)

    紧接着 \(g_k=\sum\limits_{i=k}^n(-1)^{i-k}\displaystyle\binom{i}{k}f_i\)

    设 \(f_i\) 表示至多 \(i\) 个物品时的答案, \(g_i\) 为恰好 \(i\) 个物品时的答案。

    然后 \(f_k=\sum\limits_{i=0}^k\displaystyle\binom{k}{i}g_i\)

    紧接着 \(g_k=\sum_{i=0}^k(-1)^{k-i}\displaystyle\binom{k}{i}f_i\)

  10. 在使用全排列 \(\text{STL}\) 之前记得将序列从小到大排序。

  11. 对于树链剖分上的东西,一个点到他的父亲,最多只会经过 \(\text{log}\) 条轻边,有时可以根据这个,用数据结构维护重链的操作,轻链上的进行暴力,复杂度仍然是对的。

  12. 多测学会清空。

  13. 遇到区间整体加同一个数多次别去想着直接上数据结构,想想差分,如果差分后仍然数量比较多,不妨想想将差分后的序列再差分,最后只需要做两次前缀和就可以了。

  14. 将 \(1 \sim n\) 组成排列考虑分成 \(\sqrt{n}\) 块, 每一块分别输出,不断减小 \(m\) ,可以证明是对的,也就是 CF1017C 。

  15. 异或相关,考虑使用线性基或者 01 trie 。

  16. 树上限制构造次数或者明确遍历次数为 \(n \log n\) 的时候,考虑轻重链剖分,保留重儿子答案,单独处理轻儿子。

  17. 哈夫曼树可以用于平衡线段树分治中增添删除不为 \(O(1)\) 的复杂度平衡,这样复杂度为 \(n \log n\) 。

上一篇:053试题 29 - ADR


下一篇:iOS横屏重载