sPERbEETLE

摘要： 再唱歌给你分开在拼起来，等着吧！哈哈哈哈！！！！！！！！！！！！！！！！！！！！ 合并 顾名思义，将两颗线段树合并起来。 两种做法： 1.暴力 很简单，枚举每个节点，两个节点的值按需要 pushup 即可 2.优雅的枚举 我们假设现在有两棵线段树 \(a\) 和 \(b\) 如果当前枚举到的节点如果 阅读全文

摘要： 图论那些事 存图那些事 由于vector会自带24字节的空间大小，导致了有一些毒瘤出题人喜欢卡空间。 怎么办啊？？？？？？？ 这时候，我们就要找东西替代了。 既然动态数组不行，那就用静态数组！ 链式前向星闪耀登场！ 听这名字不难想出这是用链表模拟。 标准的链式前向星一般有三个数组。 head、to和 阅读全文

摘要： 1. 基础定义 在 KMP 算法中，通常约定字符串下标从 1 开始，这在逻辑处理上比 0 下标更方便。 子串：字符串 \(S\) 中从 \(i\) 到 \(j\) 这一段顺次排列形成的字符串，记作 \(S[i..j]\)。 子序列：从 \(S\) 中提取若干元素且不改变相对位置形成的序列。 真前缀： 阅读全文

摘要： 连续段 DP 总结 一、核心思想 连续段 DP 是一种按元素放置顺序进行 DP 的技巧，常用于处理“序列中元素形成若干连续段”的问题。其核心特点是： 脱离数组构造：先不考虑具体序列位置，只维护“连续段”的数量与状态。 状态设计：通常设 \(dp_{i,j}\) 表示已处理 \(i\) 个元素，形成 阅读全文

摘要： 前置芝士：矩阵乘法，快速幂。 运算律 矩阵乘法不满足交换律，满足结合律。 所以用来加速递推的时候，我们就运用的是结合律。 以下公式 \(A\) 为 \(x \times y\) 矩阵，\(M\) 为构造出来的大小为 \(y \times z\) 矩阵，即： \[\begin{split} A \ti 阅读全文

摘要： 今天我们来讲讲排列组合。 基础公式 这个就不讲了，直接列出来吧。 排列：\(A_n^m = \frac{n!}{(n-m)!}\) 组合：$C_n^m = \frac{n!}{m!(n-m)!} $ 一些类型 圆排列 从 \(n\) 个元素的序列 \(A\) 中，取出 \(k\) 个元素排列成一个圆 阅读全文

摘要： 扫描线优化 \(DP\) 扫描线的功能其实就是可以二维数点。 例题：P3431 [POI 2005] AUT-The Bus 这道题其实有两种做法，一种是树状数组维护\(x\)或\(y\)，另一种是cdq分治。 树状数组 这种方法是最简单的，因为我们按照\(x\)或\(y\)排序之后，就可以用树状数 阅读全文

摘要： 这个怎么说呢？就是状压\(DP\)优化，直接在例题里讲吧。 例题：P5005 中国象棋 - 摆上马 我们把题目的规则改一下。 删去马蹩脚的规则，变成国际象棋的规则。 更改数据范围，\(1 \le X \le 100,1 \le Y \le 8\) 这种数据范围就不能使用常规的状压DP了，这个时候，轮 阅读全文

摘要： 不会线段树的，出门左转oi-wiki 正如标题，利用了线段树的区间查询的特点，可以将区间查询优化到 \(log\) 级别。 例题：P3970 [TJOI2014] 上升子序列 总感觉这道题有点似曾相识。。。 解法 如果是只要下标不同，就很好做了。 先想一下不管如果两个上升子序列相同，那么只需要计算一 阅读全文

摘要： 知周所众，\(DP\) 有一大堆杂七杂八的优化，例如线段树优化\(DP\)、斜率优化、单调队列优化等等等等一大坨。 本篇博客，就来讲一讲。 一般形式（可用范围） 对于和 当你的 \(DP\) 式子里有以下两种形式就可以使用。 形式1： \[dp_i = \sum_{j=L_i}^{R_i} f(j) 阅读全文