sPERbEETLE

摘要： 连续段 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) 阅读全文

摘要： 其实没什么好说的，就是在棋盘上的。 题目 P2915 [USACO08NOV] Mixed Up Cows G(混入的) 这个应该算是旅行商问题。 解法 状态定义: \(dp_{i,state}\) 表示选择状态为 \(state\)，以第 \(i\) 头奶牛为结尾的方案数。 状态转移方程式 \[d 阅读全文

摘要： 什么是子集枚举？ 就是在状态压缩后，枚举该状态的子状态。 做法 1. 一个 \(4^n\) 做法，直接枚举所有情况，并判断两个集合 \(S\) 和 \(T\) 中 \(T \in S\)。 for (int s = 0; s < (1 << n); s++) { for (int t = 0; t 阅读全文

摘要： A - 最短 Hamilton 路径 具体做法见这里。戳我喵~ B - Barn Painting G 做法 一眼树形\(DP\) 首先，观察这个需不需要换根。 并没有求从每个点出发的答案，所以以任意一个点为起点即可。 \(dp_{u,c}\)表示以\(u\)为根的子树染成\(c\)颜色的方案数 初 阅读全文