简介 Prufer 编码用长度为 n-2 的序列表示一个无根树，构造一个 Prufer 序列的方法是： 找到编号最小的叶节点，将它的父结点加入序列。 删除这个节点，如果这个操作使得父结点成为叶结点，并且父结点的编号更小，那么递归处理（如果更大的话会在之后枚举到）。 也就是说，某个点在 Prufer 序列中出现的次数等于它的出度，如果我们设每条边都是父结点指向子结点。 下面证明如果有第 n-1 ...

简介 SAT(Satisfiability) 问题是求使得形如 xi∨xj∨¬xkx_i\lor x_j\lor \neg x_kxi​∨xj​∨¬xk​ 的多个条件式同时成立的一组取值，当每个条件的变量个数大于 2 时已经被证明无法用多项式的复杂度求解，但是如果只有 2 个可以在线性时间内求出可行解。 模板 给定 nnn 个未赋值的布尔变量 x1∼xnx_1 \sim x_nx1​∼xn​，再 ...

流的定义 流网络 G=(V,E)G=(V,E)G=(V,E) 是一个有向图，每条边有一个非负的容量 c(u,v)≥0c(u,v)\ge 0c(u,v)≥0，其中源点为 sss 汇点为 ttt。 流是 fff 一个实值函数，它需要满足下列性质： 容量限制。对于所有的结点 u,v∈Vu,v\in Vu,v∈V 要求 0≤f(u,v)≤c(u,v)0\le f(u,v)\le c(u,v)0≤ ...

简介 树状数组可以看做简化版的线段树，它进行单点修改和区间查询的常数是比线段树更优的。 对于原数组 a[n]a[n]a[n]，树状数组 c[n]c[n]c[n] 是一个等长的数组，并且对于任意 c[i]c[i]c[i] 表示以 a[i]a[i]a[i] 结尾且长度为 lowbit(i)\text{lowbit}(i)lowbit(i) 的区间和。 下面用 f(x)f(x)f(x) 代表 lowbi ...

简介 Dancing Links 是用来解决精确覆盖问题和重复覆盖问题的一个数据结构，它的优势在于一旦问题被转化成精确覆盖或重复覆盖问题，那么就不需要自己想剪枝策略了，直接用 DLX 的剪枝就能达到一个优秀的效果。 DLX 使用十字双向循环链表存储，当然是用数组模拟的链表。 每列对应一个限制条件，每行对应一个选择方案，精确覆盖问题就是满足每个限制条件的同时每个限制条件只被一个选择方案满足，而重复覆 ...

简介 模拟退火是基于随机化的求多峰函数最值的算法，它虽然能以较高的概率求得最值，但是并不是 100%（那也比纯暴力拿个 10, 20 分要好） 一个题如果能够满足是要求一个区间最值，并且函数是具有连续性的，也就是当自变量变化小时函数值变化也很小，这样就可以用模拟退火去做。 费马点 在二维平面上有 n 个点，第 i 个点的坐标为 (xi,yi)(x_i,y_i)(xi​,yi​)。 请你找出一个点 ...

任务安排 有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。 机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。 从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。 另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。 一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。 ...

最大连续子序列和 输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。 注意： 子序列的长度至少是 1。 题目链接：AcWing 135。 本题可以用线段树做，但是既然是 DP 就从 DP 角度去思考。 状态表示 f(i)f(i)f(i)：以 iii 结尾长度为 mmm 的连续子序列和的最大值。 状态计算： f(i)=max⁡j=i−m ...

简介 数位 DP 是求一个区间内满足某个性质的数的个数，这个性质往往和每一位数字有关。 度的数量 求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。 例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意： 17=24+2017=2^4+2^017=24+20 18=24+2118=2^4+2^118=24+21 20=2 ...

石子合并 设有 N 堆石子排成一排，其编号为 1,2,3,…,N 每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。 找出一种合理的方法，使总的代价最小，输出最小代价。 题目链接：AcWing 282。 状态表示 ...