提高课第六单元学习笔记

作者：

c-y-m , 2025-06-07 22:41:49 · 黑龙江 , 所有人可见 , 阅读 1

1、龟速乘

主要用于乘法时取模（$当a <= 1e18, b <= 1e18时，直接取模会爆long long$）

思想和快速幂一致

快速幂 -> 二进制拆分 + 乘法 = 乘方
龟速乘 -> 二进制拆分 + 加法 = 乘法

2、递推

很多递推都是DP, 下面的例子中介绍了一种不一般的递推

3、递归

递归也是分治，就是分而治之，把问题一点点转化成更小的问题

一个东西能不能递归，取决于是否可以转化成更小的子问题

下面第一个代码是通用求等比数列和

4、前缀和与差分

5、二分

在实数二分时能写r尽量写r否则会出现精度问题，具体见下面第一道题目

6、排序

对顶堆：用途是动态维护第k小，他是主席树的子集

所以一般第k小都用主席树，只有中位数一般习惯用对顶堆，中位数问题具体见下面代码

7、$RMQ$

解决不带修改的区间最值问题，本质上是一个DP

f[i, j]：从i开始，长度是$2^j$的区间中，最大值是多少

预处理类似于LCA ：

f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

查询[l, r], 先算出长度Len, 然后找最大的K，并且$2^k <= len$（用log函数找）

然后用$2 * 2^k$就可以完全包含这个区间

return max(f[l][k], f[r - (1 << k) + 1][k]);