多谢梅花，伴我微吟。

杂项

0. 永远不要放弃。无论何时。

1. 在开场的时候，应先用 30 min 以内的时间读完所有题目，对每个题有一个初步的认知。

2. 优先找出签到题以及自己最有感觉的题，首先先用 40 min 以内时间搞定签到题并拍上。根据另外一题难度决定策略。尽量不要写太复杂 有更简单的做法就冲

3. 如果另一题较简单，那么考虑在 1 h 30 min 内切掉并拍上这个题。一个做法只有在过拍的情况下才可以无脑交上去。否则必须数据分治

4. 暴力分数+特殊性质=部分分 启发正解思考。

5. 打暴力 尽量选择常数更优秀（比如 nq 可以变成 n2 + q 的这种确定性的东西）的做法

6. 对于自己码力应当有b数 遇到“我要冲这个题”之前应该先打完确定性很强的暴力

7. 二叉树别用 vector 存，直接 son[N][2]

8. 观察答案是否超出了 int 范围，如果超出了记得只对需要的数组开 ll，禁 define int long long

9. n \leq 10,\mathcal{O}(n!)

   n \leq 20,\mathcal{O}(2^n)

   n \leq 500,\mathcal{O}(n^3)

   n \leq 5000,\mathcal{O}(n^2)/\mathcal{O}(n^2\log n)

   n \leq 10^5,\mathcal{O}(n\log ^2 n)/\mathcal{O}(n\log n)

   n \leq 5\times 10^5,\mathcal{O}(n\log n)/\mathcal{O}(n \log^2 n) （小常数）

   n \leq 10^7,\mathcal{O}(n)

   n \leq 10^{12},\mathcal{O}(\sqrt n)

   n \leq 10^{18},\mathcal{O}(1)/\mathcal{O}(\log n)

10. 一定要保证思考的做法写的出来。

11. 在 7 的前提下，如果碰到一个思维难度高的题，想想能不能通过上数据结构优化掉一部分思考量。但是同样需要注意数据结构的常数。

12. 关于优先队列的重载运算符问题： 注意优先队列是一个大根堆，因此重载小于号的时候如果重载函数里面写的是 fir.a < sec.a，这表示 fir 比 sec 小，因此 sec 要排到前面。 就像这样：

    struct cmp {
        int x, y;
        bool operator <(const cmp &fir) const {
            return y > fir.y;
        }
    };

13. 别忘记三分。虽然三分性质不是很显然，但是有的题用一下就无敌！当然大部分用三分的题往往都会通过奇怪的方法优化掉一些查找次数（比如观察性质，发现只需要一两次调整即可）

14. 从根本性质开始考虑，冷静下来挖掘性质。

15. 不要过度泛化问题，有时候一个正常的问题做着做着就变成 NPC 了（

DS

1. 根号分治是一个重要的技巧，常需要考虑！！！

2. 树上问题不是所有都需要树剖，但是树剖很好写。不会写树上差分的时候直接剖，期望还是能拿到很多分的！

3. 2D/1D 子序列问题直接考虑扫描线，比如22 AB 联考 Day2 序列

4. 点集 LCA = dfs 序最大最小两个点的 LCA

5. 不要忘记 bitset!bitset 在一些区间 xor/and/or 操作里巨无敌

6. 子树求和可以转化为DFS序上区间求和

7. 注意预处理一些东西可以优化很多复杂度

图论

1. 树上边权转点权转移到儿子节点，但是特别注意多余信息处理（尤其是树剖的时候）
2. 看到图论题先想一下这几个问题：图是否连通？有向图还是无向图？是否带权？有没有重边与自环？
3. 排列置换的题可以尝试考虑 i\rightarrow p_i 连边，这样会形成一张全是环的图，就可以做很多事情了
4. 树的直径的性质： 如果一棵树的直径长度为偶数，那么这棵树的所有直径一定交于一点，并且这个点是直径的中点； 如果一棵树的直径长度为奇数，那么这棵树的所有直径一定交于一边，并且这条边的中点是直径的中点。
5. 矩阵问题可以采用经典转化，每个点代表一列/行/单纯一个元素，都有可能
6. 和无向图上找生成树的问题相关的，常先把 MST 求出来之后在上边开始思考
7. 树剖 LCA 比倍增 LCA 来的快，写暴力时候注意下
8. 倍增倍增倍增！一定不要忘记倍增，好写！。
9. 图的核心思维就是把图问题转化为树问题求解。

数学

1. 推出了前边的公式，但是这个公式需要 \mathcal{O}(n) 递推，但是 n 特别大（比如 10^{10} 级别）考虑拉插。拉插好用，先背一个。
2. 求 \sum x^i 是经典拉插。

DP

1. 树上背包复杂度一定不要退化了！！！\mathcal{O}(n^2) 跑不了

2. 树形DP思考方式一般是

   考虑叶子向其父亲的贡献（一片两片三片地递增地考虑）然后再逐层往上考虑，总结性质

3. 先考虑暴力 DP，然后前缀和/线段树/单调队列之类的套一下，NOIP的套路 DP 应该不会超过这个。