简介 模拟退火是基于随机化的求多峰函数最值的算法，它虽然能以较高的概率求得最值，但是并不是 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。 状态表示 ...

简介 换根 DP 是解决当根节点变化时答案也发生变化的问题的题目，通常需要两遍 DFS，一遍先钦定一个点为根处理信息，第二遍是换根 DP。 [POI2008] STA-Station 给定一个 n≤106n\le 10^6n≤106 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。 题目链接：P3478。 当根节点通过边 (fa,u)(fa,u)(fa,u) 转移时： ...

搜索关键词 给定 n 个长度不超过 50 的由小写英文字母组成的单词，以及一篇长为 m 的文章。 请问，其中有多少个单词在文章中出现了。 注意：每个单词不论在文章中出现多少次，仅累计 1 次。 题目链接：AcWing 1282。 类似 KMP 算法中的 next 数组，AC 自动机是在一个 Trie 树上进行匹配，模板串由一个字符串变为一个字符串集，这样一来 next 表示的含义就是当前结点对 ...

简介 借助左旋和右旋操作，在保证 BST 性质的情况下尽可能地减少树的高度。 当结点 x→y→zx \to y \to zx→y→z 呈直线形的时候，rotate(y),rotate(x)rotate(y), rotate(x)rotate(y),rotate(x)；呈折线形时，rotate(x),rotate(x)rotate(x),rotate(x)rotate(x),rotate(x)。可以 ...

莫比乌斯函数 首先给出莫比乌斯函数 μ(n)\mu(n)μ(n) 的定义： n=∏i=1kpiciμ(n)={0,∃ci≥2(−1)k,∀ci<2n=\prod_{i=1}^k p_i^{c_i}\\ \mu(n)=\left \{ \begin{aligned} &0,\exist c_i\ge 2\\ &(-1)^k,\forall c_i<2\\ \end{ali ...

简介 ST 表是用来解决重复贡献问题的数据结构，相较于线段树，它的初始化复杂度 O(nlog⁡n)O(n\log n)O(nlogn)，查询复杂度 O(1)O(1)O(1)，常数也更小，但无法修改。 重复贡献问题是指具有性质 f(x,x)=xf(x,x)=xf(x,x)=x 并且具有结合律的运算，例如最大值、最小值、按位与、按位或、GCD 等。 关于预处理 ⌊log⁡2x⌋\lfloor\log_ ...