备忘录

注意

例：指错误示例。
例题：指运用到那个思想或技巧的例题。

数学

  • 不要乱拆式子。
  • 如果题目上提到有关质因子的东西（如互质），那么正解大概率会与质因子的相关处理有关。
  • 单位矩阵中的东西必须是常量。
  • 单位矩阵中的东西如果不够，那就加。
  • 有时候矩阵乘法不一定是一般矩阵乘法的形式。
  • 如果一道题有些值特别小（\(\le 50\)）还有些值特别大（\(\ge10^9\)），那么可以想一下矩阵乘法。
  • 如果一道题可以推出一个暴力 dp 做法，dp 转移方程式与一般矩阵乘法形式相同，那么这很有可能就是道矩阵乘法题。

组合计数

概率论

  • 不要老盯着满足条件的概率，注意不满足条件的概率对答案的影响。

dp

常见状态设计
\(dp_i=\) 以第 \(i\) 个元素为结尾的最优值
\(dp_{i,j}=\) 前 \(i\) 个元素中有 \(j\) 个满足一定条件的最优解
\(dp_{i,j}=\) 前 \(i\) 个物品，容量为 \(j\) 时的最优值
\(dp_{i,j}=\) 区间 \([i,j]\) 上的最优值
\(dp_{i,j}=\) 第一个序列前 \(i\) 个，第二个序列前 \(j\) 个的最优值
\(dp_s=\) 当前状态为 \(s\) 时的最优值
  • 注意边界情况的特殊处理。
  • 要判断一种状态设计行不行，看看能不能写出转移方程式，不要感觉不行就放弃了。
  • 答案需要什么值就把该值压入状态，优化可以压完再想。
  • 最值类 dp 一定要初始化整个 dp 数组！
  • 有时没必要严格按照题目要求进行 dp，可以在答案方面上考虑 dp。
  • 奇怪的树上问题或许可以尝试下 dp（如树上背包、换根 dp）。
  • 若题目条件满足无后效性，那么正解基本上就是 dp 了。
  • 一定要想初始化！
    • 我的现状：一次 ABC D 题我没想初始化的事，导致浪费了大量时间才 A 掉。
  • 背包：体积一定时价值最大，体积和价值可以替换成其他东西。
  • 注意转移要从能转移的地方转移过来。
  • 树形 dp 注意别漏了父节点和父子节点之间的边。
  • 树形 dp 一般是从下而上，遇到树形 dp 转移尽量从下往上想。
  • 感觉做不了或感觉思路对但过不了就加状态或换状态。
  • 感觉答案（或其他需要的东西）不能直接求出就加入状态一步一步求。
  • 不优化做不了但只会暴力先写暴力（不管是 TLE 还是 MLE），再想优化。
  • dp 转移方程式如果正着不好推，可以尝试反着推。
  • 如果答案与某个值具体是什么没有关系，那么没必要把该值具体的值压入状态。
  • 各种优化：去掉不必要的循环（1）、状态（2）；用等效的枚举替代暴力枚举（3）；加状态（4）；数据结构优化（5）；双指针（6）。
  • some tricks：

贪心

分治

数据结构

  • 线段树 \(+\) 单调栈经典例题：k-d-sequence。
  • 与 BST 建树有关的题可以想想笛卡尔树。
  • 与区间最值有关的问题可以尝试一下笛卡尔树。
  • 如果我们需要求区间内的答案，并且维护的东西可以合并，那么线段树可以考虑一下；若维护的东西恒定不变，且询问次数过多，那么可以用猫树。
  • 把空 Trie 当非空 Trie 用是可能会出问题的。
  • 有一些互不相交的区间，如果相邻区间可以合并，那么可以试试栈。
  • 如果 FHQ-Treap 输出的答案出现了随机现象，不一定是操作不对，可能是代码写寄了。
  • 分块记得正确初始化。
  • 有时和 hash 一起有奇效。

二进制

  • 如果题目上出现了位运算或 \(2^x\)，那么正解很有可能与位运算有关，且大概率需要进行二进制拆分。
  • 对于一个用二进制数表示的集合 \(S\)，若要枚举它的所有非空子集 \(T\)，可用以下代码：for (int T=S;T;T=(T-1)&S) {/*do something ...*/}
  • 对于一个用二进制数表示的集合 \(S\)，若要枚举所有包含它的集合 \(T\)（设全集 \(U=2^n-1\)），可用以下代码：for (int T=S;T<=U;T=(T+1)|S) {/*do something ...*/}

时空复杂度优化

如果是 dp 的相关优化请去 dp 那一章节。

  • 如果某个东西能预处理并且预处理后时间复杂度更优，一定要预处理。
    • 例：我在某个比赛的现状：\(100pts \rightarrow 30pts\)。
  • 空间如果需要优化，想想滚动数组。
  • 尽量少用模运算，这玩意特别慢。

字符串

多测

  • 记得清空。
  • 小心卡常，不要滥用 memset。
  • 不要少输入了东西，也就是在输入时不要输一半就直接结束了。

找规律

  • 打表是个好方法。
  • 斐波那契数列。
  • 杨辉三角。
  • 通过各种加减乘除模等组成的规律。

精度

  • double 只能保证约前 \(15\) 位有效数字是准确的（多了会产生误差）。
  • 由于浮点数可能存在误差，所以要设一个极小数 \(eps\)（通常为 \(10^{-8}\) 左右），表示误差允许的范围。
    • For example，判断 \(x\) 与 \(y\) 是否相等不能写成 x==y，必须写成 fabs(x-y)<eps。

数据范围

y 总 yyds！！！

  • 如果遇到一道题某个数极其大（令其为 \(x\)，且 \(10^7\le x\le 10^{18}\)），并且暴力是执行某个事件 \(x\) 次，那么可以想想一些 \(\log\) 级做法。
  • 如果某个数的范围比其他数明显要小，那么正解很有可能和这个数有关。
  • 注意爆 int 或爆 long long。

搜索

  • 如果边权是 \(1\)，并且是求最短路径，可以考虑一下 bfs。
  • bfs 记得别走重了。

树论

  • 自下而上处理 和 自上而下处理 效果通常不一样。
  • 边权转点权，点权转边权。
  • 如果要查询 包含指定的多个节点的最小的树 的某个值（跟路径有关），可以尝试以下经典方法：我们把这些节点按照 DFS 序进行排序，然后分别查询排序后的相邻两个节点之间的答案（认为首尾相邻），这些小的答案累加起来后进行处理得到最终答案。

图论

  • 线段树优化建图。
  • 注意重边和自环，有时还得考虑孤立点。别判错了
  • 稠密图要用朴素 Prim 算法，稀疏图要用堆优化 Prim 算法。
  • 注意图的连通性对答案的影响。
  • 做缩点类的题时要注意原图直接被缩成一个点的情况。
  • 对于边双类的题，我们可以尝试把原图缩成树或 DAG；对于点双类的题，我们可以尝试把原图处理成圆方树。
  • 若直接建边不好建，可以换一个角度来建边。
  • 做 Tarjan 类题时，Tarjan 完了再进行各种处理，不然容易出现各种奇葩的错误。
  • 试试建个超级源点看看对解题是否有帮助。
  • 差分约束经典形式变形：\(sum_r-sum_{l-1}=S\Rightarrow sum_r-sum_{l-1}\le S\verb! and !sum_r-sum_{l-1}\ge S\)。
  • 如果一道题可以转化为最短路问题并且边权只有 \(0\) 和 \(1\)，那么可以用 01bfs 做这道题。
  • 遇到瓶颈路问题、受限连通性问题可以尝试 Kruskal 重构树。

图论建模

  • 题中的条件是否可以转化为图论中的边。
  • 可以将有一定联系的东西之间建边。
  • 如果一个东西可以通过一些方式解除另一些东西部分或全部的限制（限制数不限，可以有 \(0\) 个），那么可以试试拓扑排序。

其他技巧

其他

  • 永远不要相信样例！！！
  • 边界一定要考虑周全！！！
  • 各种各样的特殊情况和细节多想想，尽量想全。
  • 记得删完调试语句。
  • 要一边敲代码一边想敲下的每一个字符、每一个变量名都是什么含义、有什么用，以降低犯唐概率。
  • 记得通过举反例来验证你的思路，有几率帮你步入正轨。
    • 例：我在一场模拟赛上 \(40\) 多人 T1 就我爆 \(0\)。
  • 注意边界处理，不要草草写几下就以为行了。
  • 两个东西合并时，要注意它们自己内部和它们合并后之间的影响对它们这个整体的影响。
  • 注意一个地方的修改对其他地方的影响。
  • INF 尽量开大（如 0x3f3f3f3f），直接算可能的最大值可能会犯唐算错。（我的经历：100pts \(\rightarrow\) 80pts）
  • 注意对特殊情况的处理，如果有无解情况一定要判。
  • 注意各种奇葩的判重。
  • 注意思考对每一种情况的处理。
  • 写代码时要注意确保万无一失！
  • 认真分析所有可能对答案产生影响的东西。
  • 做题一定要看数据范围，看看是否需要开 long long 或用高精等。
  • 一定要认真地看数据范围啊！！！！！
    • 例：我少看了个 \(a_i\ge 1\) 导致 100pts \(\rightarrow\) 0pts。
  • 一定不要心急！不然容易犯低级错误。
  • 不要心存侥幸，一定要用最稳妥的写法！
  • 用局部变量时一定要想有没有赋值。

思路引导

  • 有时一个错解经过改动是可能成为正解的。
    • Example：我模拟赛 T4 想法和题解已经约有 \(50\%\) 重合，但是我放弃了那个错解……
  • 可以考虑对每一个（有时不必拆得太细）会对答案造成贡献的东西独立计算贡献。
  • 一道题看上去是用知识点 \(A\)，但它有可能用的是知识点 \(B\)。
  • 一些似乎无法避免的枚举没必要回避，可以通过一些技巧减少枚举量，或不枚举绝对没用的东西。
  • 对于询问区间内二元组的信息时，可以考虑只保留有用的二元组。
  • 只是想是不行的，需要画图，有时可以试着通过坐标系上的点、线表示一些值之间的关系，从而想出正解。
  • 完成一个暴力后，可以针对复杂度最大的地方进行优化，这有可能推出正解。
  • 由离线做法推出在线做法。
  • 如果同时维护多个值很难，那么可以试试一个一个分开解决。
  • 没思路时，可以先一个一个想部分分，最终推出正解，就算没有推出正解拿满暴力和部分分也挺不错的。
  • 代数推导大法好。
  • 究极钩史分类讨论。
  • 如果答案由几个值（如范围、起终点等）决定且这几个值只知道范围，我们可以枚举其中的部分值（一个的比较常见），这样确定一个或几个值后处理其他的会轻松些。
  • 可以通过一些奇妙的赋值方式使题目变得简单或更易实现。
  • 如果要求出答案需要某些值，我们可以尝试先求出所有这些值，看看这些值能否通过某些方式求出答案。
  • 把相同的值看做一个整体（也就是分成若干块）或许会让题目更好做。
  • 遇到对一段连续的值（例如树上的路径、数列上的一段区间）进行修改的时候，想想差分。
  • 不要轻易否定你的每一个想法，否则正解思路可能会与你失之交臂。
    • 我的现状：\(100pts \rightarrow 20pts\)。
  • 对题目进行灵活转化。
  • 如果可能有多种情况，分类讨论，讨不出来可以试着加条件等。
  • 不要把题目想难了，不然简单题都做不出来。
  • 正难则反。
  • 时光倒流。
  • 对于需要求出所有区间的某个值，可以考虑先枚举一个 \(r\)，利用数据结构等维护出每个 \(l\in[1,r]\) 到 \(r\) 的值。
  • 对于求三角形内部的东西（包括面积），可以让每个边向 \(x\) 轴投影，这样可以形成三个直角梯形，然后用上面两条边形成的梯形的贡献减去下面一条边形成的梯形的贡献即可得出此三角形内部的贡献。
  • 不要把题目复杂化了。
  • 认真分析，不要“感觉是对的”。
  • 注意审题。
  • 看到区间和想想是否可以转化成两个前缀和的差。
  • 如果某种特殊的处理方式对某种特殊的数据来说是正确的，那么正解可能是这种处理方式的普遍化。
    • Example：树上问题先想菊花图、链的情况，再由这种特殊情况推向一般情况。
    • 例题：一棵树
  • 如果某个东西最后处理来处理去都一定会被几个独立的处理影响且不管怎么搞影响总是一定的，那么不如先进行那几个处理。
  • 如果遇到不等式链，可以尝试把不等式链拆成若干个不等式。
  • 若一道题有多个限制，且直接做难以满足每个限制时，可以通过一些特殊的枚举方式来满足一些限制，然后再通过其他方法维护其他限制。
  • 如果题目限制仅有一些大小关系，那么可以试试 CDQ 分治。
  • 如果题目中的限制看上去特别难搞，可以先尝试想想没有限制时怎么做，再由没有限制的做法推出有限制的做法。

一些结论

\(\verb!2025.11.07!\)，文章《一些结论》正式合并进《备忘录》。

\(\verb!I!\)

两个不同的点 \(A(x_1,y_1)\) 和 \(B(x_2,y_2)\)，其中 \(x_1,y_1,x_2,y_2\in\mathbb{Z}\)，令 \(l_1=|x_1-x_2|,l_2=|y_1-y_2|\)，那么 \(AB\) 这条线段上的整点个数为 \(\gcd(l_1,l_2)+1\) 个（含点 \(A,B\)）。

\(\verb!II!\)

令 \(V\) 表示一个连通图的边集、\(V^\prime\) 表示该图最小生成树（任意一种情况）的边集、\(w(u,v)\) 表示 \((u,v)\) 这条边的边权，如果 \((x,y)\in\complement_V V^\prime\)，那么最小生成树上的路径 \(x\rightarrow y\) 上的边的边权一定都小于或等于 \(w(x,y)\)。

\(\verb!III!\)

一棵树如果想变成一个边双连通的图，那么至少需要加 \(\lfloor\dfrac{cnt+1}{2}\rfloor\) 条边，其中 \(cnt\) 表示度数为 \(1\) 的点的数量。

例题：[USACO06JAN] Redundant Paths G

\(\verb!IV!\)

如果一个点双连通分量中有一个奇环，那么这个点双连通分量上的所有点都在某个奇环上。

例题：KNIGHTS - Knights of the Round Table

\(\verb!V!\)

令 \(F_n\) 表示斐波那契数列的第 \(n\) 项，那么 \(\gcd(F_x,F_y)=F_{\gcd(x,y)}\)。

\(\verb!VI!\)

如果一个有向图中的所有的点的出度均为 \(1\)，那么该图上所有的点都在一个环上或从该点开始能够到达某个环。

例题：星战

\(\verb!VII!\)

康威生命游戏弱化。

将一个圆环分为 \(N\) 段，将这 \(N\) 段顺时针依次编为 \(1,\dots,N\) 号。每一段要么是活的，要么是死的。

游戏进行的每轮变化如下：
如果一个方格恰好有一个相邻的方格在这次变化中存活，那么该方格会在下次变化中存活；否则，该方格会死亡。

游戏进行 \(2^k\)（\(k\in\mathbb{N}\)）轮后，第 \(x\) 个位置的方格活着的条件：向左数第 \(2^k\) 个方格的状态与向右数第 \(2^k\) 个方格的状态不同。

例题：生命中的圆

\(\verb!VIII!\)

对于任意一个所有边权均为正数的图 \(G\) 和任意一个源点 \(S\)，最短路图 \(G^\prime\) 不存在环，即图 \(G^\prime\) 是一个 DAG。

例题：道路

比赛做题策略

  • 如果一场比赛题目不按难度升序排序（乱序），那么要先把所有题看一遍再做题。
  • 一道题如果想了 20min 都没有什么思路，建议先打暴力和拿部分分，一定要记住不要死磕！
    • Origination：此策略来源于一离省队很近的大佬。
    • Explain：你不知道你的暴力需要写多长时间，别因为死磕一道题导致其他题没时间拿暴力和部分分！
  • 吾赛时 \(N\) 省吾身：
    • 上述各条熟记于心乎？
    • 思路考虑周全乎？可行乎？实现前检查其正确性乎？
    • 此题可用数据结构、二分、贪心、dp、折半搜索乎？
    • 此做法可用 bitset 优化乎？
    • 输出格式正确乎？
    • pushdown 写全乎？
    • freopen 写对乎？long long 开全乎？数组大小合适乎？
    • 时空复杂度可过乎？
    • 能拿到的分拿全乎？

记忆

哈希常用质数
233 13331
12255871 19260817 998244353
1e9+7 1e9+9
X 无向图（连通） 有向图（连通）
存在欧拉路径的充要条件 度数为奇数的点只有 \(0\) 或 \(2\) 个 所有点的出度均等于入度；除了两点之外，其余点的出度均等于入度，剩余的两点：一个出度比入度多 \(1\)（起点），另一个入度比出度多 \(1\)（终点）
存在欧拉回路的充要条件 度数为奇数的点只有 \(0\) 个 所有点的出度均等于入度

一些运算符优先级从高到低如下表所示：

加减 移位 比较大小 位与 异或 位或
+ - << >> < > == != & ^ |
算法 复杂度
朴素 \(\verb!Dijkstra!\) \(\mathcal{O}(n^2)\)
优先队列优化 \(\verb!Dijkstra!\) \(\mathcal{O}((n+m)\log n)\)
斐波那契堆优化 \(\verb!Dijkstra!\) \(\mathcal{O}(m+n\log n)\)
辗转相除法求 \(\verb!gcd!\) \(\mathcal{O}(\log n)\)
  • 补码：一个二进制数 \(n\)，它的补码 \(\sim n=-1-n\)。
  • 子串是连续的，子序列是不一定连续的。
posted @ 2025-03-28 13:55  lyas145  阅读(38)  评论(1)    收藏  举报