前言 RMQ 算法大概是这样的： 算法 预处理 查询 空间 码量 ST 表 O(nlog⁡n)O(n \log n)O(nlogn) O(1)O(1)O(1) O(nlog⁡n)O(n \log n)O(nlogn) 小 树状数组 O(n)O(n)O(n) O(log⁡2n)O(\log^2 n)O(log2n) O(n)O(n)O(n) 小 线段树 O(n)O(n)O(n)

之前打 ABC 发现自己背包掌握的不是很熟练，所以写这一篇复习笔记。 基本模型 有 nnn 种物品和一个容量为 mmm 的背包，每种物品有重量 wiw_iwi​ 与价值 viv_ivi​ 两种属性，要求选若干个物品，使它们的重量之和 ≤m\le m≤m 且 ∑v\sum v∑v 最大。 各种背包都是在这个模型下的。 01 背包 每种物品有且仅有一个。 设 dpi,jdp_{i, j}dpi,j​

前言 1 个月前打 abc404，G 题一眼差分约束 debug 1h，吃了 5 发罚时，喜提 0pts。故写一篇复习笔记。 模型 见 模板题 中所描述的形式。 原理 对于一个约束 xi−xj≤cx_i-x_j \le cxi​−xj​≤c，移项可得 xi≤xj+cx_i \le x_j+cxi​≤xj​+c，这类似于最短路中的三角不等式 disi≤disj+cdis_i \le dis_j+cd

引入 这是一道数据结构题。 维护一个数列，支持插入、删除、查排名、查数、前驱、后继。 以下，用 nnn 表示操作数，www 表示值域。 Subtask 1：n≤103n \le 10^3n≤103 暴力 O(n2)O(n^2)O(n2) 维护即可。 Subtask 2：n≤104n \le 10^4n≤104 采用 std::vector 和二分维护一个有序序列。由于 memmove 的小常数，可

定义 一般地，定义一个括号序列是仅由 ( 与 ) 组成的字符串。合法括号序列的定义为： 空串为一个合法括号序列； 若 s 为合法括号序列，则 (s) 也是合法括号序列； 若 s、t 均为合法括号序列，则 st 也是合法括号序列。 括号序列其实是一种模型，描述一类二元对应平衡关系。有时还会有 []、{}、<> 等不同的括号。 经典问题 合法性判断 栈的经典应用。令

更新 在一年前，我编写了 BigInteger2 项目。BigInteger3.0 对 BigInteger2 进行了重构，主要更新是将动态分配空间改为 std::vector 自动分配空间，并将实现精细化。 由于之后的更新不希望文章重新审核，因此可到 剪贴板 查看。 12345678910111213141516171819202122232425262728293031323334353637