感觉自己变弱了,想卷,但是显然是完全卷不起来的。所以考虑写博客,当作一种软颓废(不想打题,而是写博客寻找自信)。
动态规划
暑假写的。StaroForgin 老师讲得很好啊,非常有启发意义。我感觉之前做的都不算动态规划。但是现在做的还不多,于是没有办法写具体的题解。
-
费用提前计算。我们只要改变定义,并说明其结果的等价性就可以说明其正确性。e.g.P5785
-
对于求最优方案的动态规划,我们不一定要满足每一步的转移都是完全符合数量关系的。我们只需要保证最优解一定能通过某种方式计算出来且不符合数量关系的转移不会使得答案比最优解更优。(抽象的,没有关系,我认为这个做一些题就可以领悟)e.g.P3959
-
如何阐述一类删去无用状态的做法的正确性?说明一定有另一个有用状态不劣于这个状态。e.g.P5504
-
数轴上的移动,一般具有贪心的性质,可以转化为区间动态规划的模型。e.g.ABC291H
-
树上动态规划的一个通用方法,将当前枚举到的根和子树看作一个整体,与一棵新的子树进行合并。e.g.ARC142D
-
对于一类双向覆盖的动态规划,不妨定义两个动态规划数组互相转移。e.g.P6246
-
对于一类求最小字典序合法解的问题,可以考虑求一组状态的最小字典序的排名来转移。
-
直接利用决策单调性得出决策上下界枚举的 2D1D 动态规划真的是 \(O(nk)\) 的吗?错了,全名是 \(O(n^2+nk)\)。
-
对于操作顺序混乱的题目,可以贪心地将其转化为操作有序的题目,进行动态规划。e.g.CF1854B
-
对于无根树的计数,不妨选定一个根,转化为有根树计数,最后除以点数。这样方便转移。
-
对于一类合并若干状态的计数动态规划,直接挨个合并可能会算重,这时需要强制钦定合并顺序。
数据结构
-
超级钢琴 trick。用于求贡献前 \(k\) 大的区间。
-
线段树的标记永久化。一种做法是标记后不再访问其字子树,以保证复杂度。
-
标记永久化,好用。要满足交换律,这种基本的运算律。(而如果是直接下传标记,则只需要满足结合律)
数学
-
一个可以求奇怪模数组合数的 trick:\(\dfrac{a}{b}\equiv \dfrac{a\bmod {(p\times b)}}{b}\pmod{p}\)。e.g.P6078
-
对于求期望的题,大概率直接大力拆贡献。
-
考虑 \(f_i\) 为操作 \(i\) 次恰好合法的方案数,求操作 \(i\) 次仍不合法的方案数不妨考虑 \(f_{i+1}\)。
图论
- 多个源点,求某一点到源点最短路的最小值,仍然可以直接使用一遍最短路求解。