首先感谢大家的点赞和支持
created: 10/17/2021
updated: 10/20/2021, 10/27/2021, 11/20/2021, 11/22/2021, 12/07/2021, 12/12/2021, 12/20/2021, 2/14/2022, 3/01/2022 4/02/2022
AcWing上不是最新版本,最新版本请移至博客园
博客园—更好的阅读体验
Gitee—下载.md文件
更新分割线
memset也会卡时间
$(x\mod a) \mod ba = (x \mod ba )\mod a$
求 $1~n$ 中有多少数是 $i$ 的倍数,就是 $n / i$
数组非全局变量要初始化
多动手推一推
复杂变量学会适当引用
[toc]
STL
vector, 变长数组,倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算,按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字(字典序)
string,字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标,(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列,默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式:priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树(红黑树),动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继,时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x,删除所有x O(k + logn)
(2) 输入一个迭代器,删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似,增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound(), 迭代器的++,--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
lower_bound
搜索数组中第一个大于等于 ≥ x的数,返回迭代器
不存在返回end
#include<algorithm>
vector<int> a;
int pos = lower_bound(a.begin(), a.end(), x) - a.begin(); // pos便是目标下标
int pos = lower_bound(a.begin(), a.end(), x, greater<int>() ) - a.begin() // 找到第一个小于等于x的数
upper_bound
与lower_bound用法相似,搜索数组中第一个大于 > x的数,返回迭代器
不存在返回end
#include<algorithm>
vector<int> a;
// pos便是目标下标
int pos = upper_bound(a.begin(), a.end(), x) - a.begin();
// 找到第一个小于x的数
int pos = upper_bound(a.begin(), a.end(), x, greater<int>() ) - a.begin();
基础算法
分治
分治法把一个问题划分为若干个规模更小的同类子问题,对这些子问题递归求解,然后再回溯时通过它们推导出原问题的解。
分治求等比数列和
用到了快速幂,求 $1+p+\cdots+p^k$ 的和
// 分治求等比数列和复杂度(log k)
ll sum(int p, int k){
if(!k) return 1;
if(k & 1)
return (1 + qmi(p, (k + 1) / 2)) % mod * sum(p, (k - 1) / 2) % mod;
return ((1 + qmi(p, k / 2)) * sum(p, k / 2 - 1) + qmi(p, k)) % mod;
}
基础排序算法
归并排序
递归分成相等的子段,子段内部排序后,回溯时合并再排序
const int N = 1e6 + 10;
int q[N],tmp[N];
void mergesort(int a[],int l,int r){
if(l >= r) return;
int mid = (l + r) / 2;
mergesort(q,l,mid);
mergesort(q,mid+1,r);
int k = 0,i = l,j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++]; // 求逆序对,在后面加一个 ans += mid - i + 1;
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];
}
int main(){
int n;
scanf("%d",&n);
for(int i = 0;i < n;i++){
scanf("%d",&q[i]);
}
mergesort(q,0,n-1);
for(int i = 0;i < n;i++){
printf("%d ",q[i]);
}
return 0;
}
二分
整数二分
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点数二分
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
前缀和、差分
核心思想
前缀和将查询区间和变为 $O(1)$
差分将区间修改变为 $O(1)$ , $O(n)$ 得到原数组
一维前缀和
for(int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i];
二维前缀和
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
s[i] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
一维差分
b[i] = a[i] - a[i - 1]
// 对 [l, r] 区间 + c: b[l] += c, b[r + 1] -= c;
// 对 [l, r] 区间 - c: b[l] -= c, b[r + 1] += c;
二维差分
// b[x1][y1] += c 是对顶点到右下角的子矩阵的值增加 c
void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= c;
b[x2 + 1][y2 + 1] += c;
b[x1][y1] += c;
}
双指针
核心思想
省掉重复性的动作,进行优化,能达到 $O(n)$ 复杂度
区间离散化
unique() + erase() 函数
vector<int> v;
sort(v.begin(), v.end()); // unique仅对相邻元素处理,需要排序
v.erase(unique(v.begin(), b.end()), v.end()); // unique返回末尾重复元素开头位置
数据结构及字符串算法
STL基础
队列
滑动窗口
滑动窗口本质是一个单调的双端队列
#include<deque>
using namespace std;
const int N = 1e6 + 10;
deque<int> q;
int a[N];
int n, k;
// 滑动窗口要用双端队列
int main(){
cin >> n >> k; // k 为滑动窗口大小
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){ // 获取滑动窗口最小值
int x = a[i];
while(!q.empty() && i - q.front() > k - 1)
q.pop_front();
while(!q.empty() && a[q.back()] >= a[i]){ // 队尾大于等于 x 就 pop_back
q.pop_back();
}
q.push_back(i);
if(i >= k)
printf("%d ", a[q.front()]);
}
printf("\n");
q.clear();
for(int i = 1; i <= n; i++){ // 获取滑动窗口最大值
int x = a[i];
while(!q.empty() && i - q.front() > k - 1)
q.pop_front();
while(!q.empty() && a[q.back()] <= a[i]){ // 队尾小于 x 就 pop_back
q.pop_back();
}
q.push_back(i);
if(i >= k)
printf("%d ", a[q.front()]);
}
return 0;
}
数组模拟队列
int q[N];
int main(){
int T;
cin >> T;
int hh = 0, tt = -1;
while(T--){
string op;
cin >> op;
if(op == "push"){ // 加入元素到队尾
int x;
cin >> x;
q[++tt] = x;
}
else if(op == "pop") // 弹出队头
hh++;
else if(op == "empty"){ // 查询是否为空
if(hh <= tt)
puts("NO");
else
puts("YES");
}
else // 查询队头
printf("%d\n", q[hh]);
}
return 0;
}
栈
数组模拟栈
int s[N];
int main(){
int T;
cin >> T;
int tt = 0; // tt 表示栈顶
while(T--){
string op;
cin >> op;
if(op == "push"){ // 入栈
int x;
cin >> x;
s[++tt] = x;
}
if(op == "pop") // 弹出栈顶
tt--;
if(op == "empty"){ // 查询栈是否为空
if(tt > 0)
puts("NO");
else
puts("YES");
}
if(op == "query") // 查询栈顶
printf("%d\n", s[tt]);
}
return 0;
}
单调栈
int s[N];
int main(){
int n;
cin >> n;
int tt = 0;
for(int i = 0; i < n; i++){
int x;
cin >> x;
while(tt > 0 && s[tt] >= x) // 栈不为空,栈顶大于等于 x
tt--;
if(!tt)
printf("-1 ");
else
printf("%d ", s[tt]);
s[++tt] = x; // 将 x 入栈
}
return 0;
}
KMP
using namespace std;
const int M = 1e6 + 10,N = 1e5 + 10;
char p[N],s[M];
int n,m;
int ne[M];
int main(){
cin >> m >> p+1 >> n >> s+1;
// 预处理next数组
ne[1] = 0; // 第一个元素无后缀
for(int i = 2,j = 0;i <= m;i++){
while(j && p[i] != p[j+1]) j = ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
// 匹配过程
for(int i = 1,j = 0;i <= n;i++){
while(j && s[i] != p[j+1]) j = ne[j];
if(s[i] == p[j+1]) j++;
if(j == m){
cout << i - m << " ";
j = ne[j]; // 优化速度
}
}
return 0;
}
Trie 树
开 $son$ 数组的大小要根据题目而定,一般为 $元素个数 \times 存储每个元素最多需要的节点数$
int son[N][26], idx; // idx存放节点编号, 0号节点既是根也是空节点
int cnt[N];
void insert(char str[]){ // 插入
int p = 0;
for(int i = 0; str[i]; i++){
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++ idx; // 节点不存在则新建一个
p = son[p][u];
}
cnt[p] ++; // 对末尾节点做标记
}
int query(char str[]){ // 查询
int p = 0;
for(int i = 0; str[i]; i++){
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
可持久化Trie
- 空间不够,用最大空间倒退,能开多大开多大
例题: 最大异或和
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 6e5 + 10, M = N * 24; // 原来要3e5, 3e5次查询 序列长度最多有6e5,每个数最多24位,历史版本Trie所有加起来最多需要 6e5 * 24 个节点
int n, m;
int tr[M][2], root[N], max_id[M], s[N], idx;
// 可持久化Trie思想:与前一个版本的trie不同的路径上的点都要重新建立
// 题目思路:转换异或前缀和,s[p - 1] ^ s[n] ^ x 最大,在[l - 1, r - 1]找一个 p 使得 s[p - 1] ^ (s[n] ^ x) 最大
// 因为需要先知道子节点下标来确定父节点下标,用递归的写法
void insert(int i, int k, int p, int q){ // 在前缀和中的下标,插入了第几位(从左到右),旧版本对应节点,新版本对应节点
if(k <= -1){
max_id[q] = i;
return ;
}
int v = (s[i] >> k) & 1; // 取出该位
tr[q][v] = ++ idx; // 与原来不同的路径要新开点
if(p)
tr[q][v ^ 1] = tr[p][v ^ 1]; // 与原来相同的路径直接复制
insert(i, k - 1, tr[p][v], tr[q][v]); // 递归插入
max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]); // 回溯更新子树最大下标
}
int query(int root, int C, int l){ // 根节点编号,待异或的值,下标限制
int p = root;
for(int i = 23; i >= 0; i--){
int v = (C >> i) & 1;
if(max_id[tr[p][v ^ 1]] >= l) // 贪心寻找01相反的节点,且下标符合要求
p = tr[p][v ^ 1];
else
p = tr[p][v];
}
return C ^ s[max_id[p]];
}
int main(){
cin >> n >> m;
max_id[0] = -1; // 空节点下标无穷小
root[0] = ++ idx; // 一定为根开辟新节点
insert(0, 23, 0, root[0]); // 插入,s[0]也算前缀和
int x;
for(int i = 1; i <= n; i++){
cin >> x;
s[i] = s[i - 1] ^ x;
root[i] = ++ idx; // 为新根开辟新节点
insert(i, 23, root[i - 1], root[i]);
}
while(m--){
string op;
cin >> op;
if(op == "A"){
++n;
cin >> x;
root[n] = ++ idx; // 为新根开辟新节点
s[n] = s[n - 1] ^ x;
insert(n, 23, root[n - 1], root[n]);
}
else{
int l, r;
cin >> l >> r >> x;
cout << query(root[r - 1], s[n] ^ x, l - 1) << endl; // 区间[l, r],转换后找 p 属于 [l - 1, r - 1], 在root[r - 1]中寻找,下标限制 >= l - 1;
}
}
return 0;
}
并查集
并查集初始化
for(int i = 1; i <= n; i++){
p[i] = i;
Size[i] = 1; // 维护以i为根的连通块大小
}
查询+路径压缩
int find(int x){
if(x != p[x]) return p[x] = find(p[x]);
return p[x];
}
查询+维护点到根节点距离
int find(int x){
if(x != p[x]){
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
合并并查集
p[find(a)] = find(b);
sz[b] += sz[a]; // 维护的并查集大小合并
查询两点是否在同一集合
if(find(a) == find(b))
哈希表
存储结构
开放寻址法
$N$ 取输入规模的 $2~3$ 倍,$null$ 为初始化值
const int N = 2e5 + 5, null = 0x3f3f3f3f;
int h[N];
void insert(int x){ // 插入
int k = (x % N + N) % N;
while(h[k] != null){
k++;
if(k == N)
k = 0;
}
h[k] = x;
}
int find(int x){ // 查找
int k = (x % N + N) % N;
while(h[k] != null){
if(h[k] == x)
break;
if(k == N)
k = 0;
k++;
}
return h[k];
}
拉链法
类似邻接表
const int N = 1e5 + 3; // 大于输入数据规模的第一个质数
int e[N], ne[N], h[N], idx;
void insert(int x){ // 插入
int k = (x % N + N) % N;
e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}
bool find(int x){ // 查找
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i]){
if(e[i] == x)
return true;
}
return false;
}
字符串哈希
对字符串前缀进行哈希映射,从左到右,高位到低位,映射成 $P$ 进制数。
+ 通常 $P = 131$ 或者 $P = 13331$
+ 数组写成 unsigned long long
达到自动取模的目的
+ 得到 $[l,r]$ 字串哈希值,$value=h_r-h_{l-1}\times p^{r-l+1}$
typedef unsigned long long ull; // unsigned long long 最大值为 2^64 -1, 可以实现自动取模
using namespace std;
const int N = 1e5 + 10, P = 131; // P = 13331
ull p[N], h[N];
char str[N];
int n, m;
void init(){ // 预处理p进制
p[0] = 1;
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i]; // str[i] 不为0即可
}
}
ull get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1]; // 前缀和+进制对齐
}
ST表(RMQ算法)
与线段树区别:区间最值静态查询,不支持修改
ST表初始化
void init(){
for(int i = 0; i < M; i++) // 类似区间DP,先枚举区间长度,再枚举起点
for(int j = 1; j + (1 << i) - 1 <= n; j++){
if(!i)
st[j][0] = a[j];
else
st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
ST表查询
int query(int l, int r){
int len = r - l + 1;
int k = log(len) / log(2); // 小于区间长度的最大2的幂次
return max(st[l][k], st[r - (1 << k) + 1][k]); // 前后两段最大值的最大值就是区间的最大值
}
树状树组
本质功能及扩展
+ 区间查询,查询前缀和复杂度 $O(logn)$ (可与差分结合)
+ 单点修改,修改数组元素复杂度 $O(logn)$。
+ 可以以数值出现次数作为维护对象,解决逆序对问题
+ 在差分基础上可从单点查询改为区间和查询,方法是采用补集的思想:
+ 区间内每个元素是差分数组的前缀和,区间和就是两层循环的差分数组元素加和
+ 用补集,补出一个 (x + 1, x) 的矩阵,原来要求的区间和 = 矩阵和((x + 1) * 差分数组前缀和[x]) - i * a[i] 为元素数组的前缀和[x];
+ 处理数组第 $k$ 小问题(数组为一个排列):
+ 树状树组维护一个元素值为1的数组,代表这个数出现了一次
+ 删除这个数便是,add(x, -1)
,找到第 k 小采用二分的方法,由于数组只有 0 和 1 ,前缀和有单调性,找到最小的 x,ask(x) = k
,就是第 $k$ 小的数
三个基础函数
int lowbit(int x){
return x & -x;
}
void add(int x, int c){ // 单点修改
for(int i = x; i <= n; i += lowbit(i))
tr[i] += c;
}
int ask(int x){ // 查询区间 [1, x]
int res = 0;
for(int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
线段树
五个函数: pushup pushdown build query modify
普通线段树:支持区间查询,单点修改
带有 $lazy$ 标记线段树:同时支持区间修改需要pushdown
操作
使用要点及扩展
+ 线段树维护属性根据题意来获取,现有属性不足就补充新的属性直到可以顺利更新为止
+ 维护区间最大公约数问题:
+ 区间加转化为单点修改(维护差分数组)
+ 区间最大公约数 $gcd(a_1, a_2, … , a_n) <=> gcd(a_1, a_2 - a_1, a_3 - a_2, … , a_n - a_{n-1})$ 的最大公约数
+ 其中 $a_1$ 用差分前缀和求出(需要维护区间和)
+ 同时维护区间加和区间乘的懒标记问题,先乘后加
线段树模板
模板一. 动态查找区间最大值(无pushdown)
#include<iostream>
#include<cstring>
#include<algorithm>
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 2e5 + 10;
int n, m, p;
struct T{
int l, r, v;
}tr[N << 2];
void pushup(int u){ // pushup: 子节点更新父节点信息
tr[u].v = max(tr[ls].v, tr[rs].v);
}
void build(int u, int l, int r){ // 建立线段树,(节点编号,节点区间左端点,节点区间右端点)
tr[u] = {l, r}; // 先赋值节点区间
if(l == r) // 到叶子节点就return
return;
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r); // 在(l, mid) (mid + 1, r) 两个区间上继续递归
}
int query(int u, int l, int r){ // 查询操作,(节点编号,查询区间左端点,查询区间右端点)
if(tr[u].l >= l && tr[u].r <= r) // 查询区间完全包含节点区间,返回节点值
return tr[u].v;
int mid = (tr[u].l + tr[u].r) >> 1;
int res = 0;
if(l <= mid) res = query(ls, l, r); // 查询区间在节点区间左边有交集
if(r > mid) res = max(res, query(rs, l, r)); // 在节点区间右边右交集,结果取最大值(节点值属性定义)
return res;
}
void modify(int u, int pos, int v){ // 单点修改, (节点编号,查询点下标,更改值)
if(tr[u].l == pos && tr[u].r == pos) // 到了查询点,返回节点值
tr[u].v = v;
else{
int mid = (tr[u].l + tr[u].r) >> 1;
if(pos <= mid) modify(ls, pos, v); // 查询点在节点区间左边,往左子树查询
else modify(rs, pos, v); // 否则,往右子树查询
pushup(u); // 子节点变化,pushup往父节点更新信息
}
}
int main(){
cin >> m >> p;
build(1, 1, m); // 长度最多为m
int last = 0;
while(m --){
string op;
long long d;
cin >> op >> d;
if(op == "Q"){
last = query(1, n - d + 1, n);
cout << last << endl;
}
else{
d = (d + last) % p;
modify(1, n++ + 1, d);
}
}
return 0;
}
模板二. 区间修改问题(有pushdown)
#include<iostream>
#include<cstring>
#include<algorithm>
#define ls u << 1
#define rs u << 1 | 1
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
int n, m;
ll a[N];
struct T{
int l, r;
ll sum, add; // add 即 lazy 标记,子区间需要修改
}tr[N << 2];
void pushup(int u){
tr[u].sum = tr[ls].sum + tr[rs].sum;
}
void pushdown(int u){ // lazy 标记下放
tr[ls].sum += (tr[ls].r - tr[ls].l + 1) * tr[u].add, tr[ls].add += tr[u].add; // 父节点更新子区间,子区间 lazy 标记要加上父节点 lazy 标记
tr[rs].sum += (tr[rs].r - tr[rs].l + 1) * tr[u].add, tr[rs].add += tr[u].add;
tr[u].add = 0; // 父节点 lazy 标记晴空,保证查询和修改时,父节点的lazy标记均被清楚
}
void build(int u, int l, int r){
if(l == r)
tr[u] = {l, l, a[l], 0};
else{
tr[u].l = l, tr[u].r = r;
int mid = (tr[u].l + tr[u].r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, ll v){
if(tr[u].l >= l && tr[u].r <= r){ // 注意区间修改的递归出口
tr[u].sum += (tr[u].r - tr[u].l + 1) * v;
tr[u].add += v; // lazy标记加 v
}
else{
pushdown(u); // 递归分裂前 pushdown
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) modify(ls, l, r, v);
if(r > mid) modify(rs, l, r, v);
pushup(u);
}
}
ll query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
else{
pushdown(u); // 递归分裂前pushdown
int mid = (tr[u].l + tr[u].r) >> 1;
ll res = 0;
if(l <= mid) res = query(ls, l, r);
if(r > mid) res += query(rs, l, r);
return res;
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while(m--){
string op;
ll l, r, d;
cin >> op >> l >> r;
if(op == "Q")
cout << query(1, l, r) << endl;
else{
cin >> d;
modify(1, l, r, d);
}
}
return 0;
}
模板三. 亚特兰蒂斯(扫描线算法)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#define ls u << 1
#define rs u << 1 | 1
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
int n;
vector<double> ys;
// 多复习扫描线的做法,扩展性不强
struct Seg{
double x, y1, y2;
int k;
bool operator < (const Seg& s) const{
return x < s.x;
}
}seg[N << 1];
struct T{
int l, r, cnt;
double len;
}tr[N << 3]; // 线段树空间是线段树维护的序列的 4 倍
int find(double y){
return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}
void pushup(int u){
if(tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l]; // 节点有被覆盖,ys 内元素代表区间, 要表达 tr[u].r 所想要的元素要 + 1
else if(tr[u].l != tr[u].r) // 节点未被覆盖,但是不是叶子节点可以从子节点求出len
tr[u].len = tr[ls].len + tr[rs].len;
else
tr[u].len = 0; // 节点未被覆盖, 有可能是被更新cnt = 0, 需要将节点的 len 置为 0
}
void build(int u, int l, int r){
if(l == r)
tr[u] = {l, r, 0, 0};
else{
tr[u] = {l, r, 0 ,0};
int mid = (tr[u].l + tr[u].r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
}
}
void modify(int u, int l, int r, int k){ // 扫描线不需要pushdown
if(tr[u].l >= l && tr[u].r <= r){
tr[u].cnt += k;
pushup(u); // 该节点有更新,需要 pushup 更新父节点
}
else{
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) modify(ls, l, r, k);
if(r > mid) modify(rs, l, r, k);
pushup(u);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 0;
while(cin >> n, n){
ys.clear();
for(int i = 0, j = 0; i < n; i++){
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
seg[j++] = {x1, y1, y2, 1};
seg[j++] = {x2, y1, y2, -1};
ys.pb(y1), ys.pb(y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
sort(seg, seg + 2 * n);
build(1, 0, ys.size() - 2); // 下标为长度 -1, 记录元素表示区间还要-1
double res = 0<F8>;
for(int i = 0; i < 2 * n; i++){
if(i > 0)
res += tr[1].len * (seg[i].x - seg[i - 1].x);
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k); // 单个元素代表以该下标值为左端点的节点, 转换到线段树维护的区间右端点要 -1
}
cout << "Test case #" << ++T << endl;
cout << "Total explored area: " << fixed << setprecision(2) << res << endl << endl;
}
return 0;
}
平衡树
Treap
原理
1. 以 BST(二叉搜索树)为前导,右子树节点 key > 父节点 key > 左子树节点 key
2. 通过加入 val 使 BST 有了大根堆的性质约束,相对平衡,演变为 Treap 平衡树
Treap模板
模板一
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 1e8;
int idx, root;
struct Node{
int l, r;
int key, val;
int cnt, size;
}tr[N];
void pushup(int p){ // 与线段树pushup同理,子节点更新父节点
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key){ // 创建节点,传入key
tr[++idx].key = key;
tr[idx].val = rand(); // 随机 val
tr[idx].cnt = tr[idx].size = 1;
return idx; // 返回节点编号
}
void zig(int& p){ // 右旋
int q = tr[p].l; // 右旋取左儿子
tr[p].l = tr[q].r, tr[q].r = p, p = q; // 父节点跑到左儿子右边,左儿子右边变成父节点,指针调整到左儿子上
pushup(tr[p].r), pushup(p); // pushup更改了的两个点
}
void zag(int& p){ // 左旋
int q = tr[p].r;
tr[p].r = tr[q].l, tr[q].l = p, p = q; // 父节点跑到右儿子的左边,右儿子的左儿子变成父节点,指针调整到右儿子上
pushup(tr[p].l), pushup(p); // pushup更改了的两个点
}
void build(){ // 建树
get_node(-INF), get_node(INF); // 建立哨兵节点,有利于处理边界
root = 1, tr[1].r = 2;
pushup(root);
if(tr[1].val < tr[2].val) zag(root);
}
void insert(int &p, int key){ // 插入节点
if(!p) p = get_node(key); // 不存在这个节点,直接创建
else if(tr[p].key == key) tr[p].cnt++; // 节点已经存在就 cnt++
else if(tr[p].key > key){ // 要往左边插
insert(tr[p].l, key);
if(tr[tr[p].l].val > tr[p].val) zig(p); // 左儿子值比当前节点大,插入后左儿子需要调整到父节点,进行右旋
}
else{ // 往右边插
insert(tr[p].r, key);
if(tr[tr[p].r].val > tr[p].val) zag(p); // 右儿子值比当前节点大,插入后右儿子需要调整到父节点,进行左旋
}
pushup(p); /// 将下面的信息更新到 p 指针所指节点,由于是回溯,有自下向上的作用
}
void rm(int& p, int key){ // 删除节点
if(!p) return;
if(tr[p].key == key){ // 节点存在
if(tr[p].cnt > 1) tr[p].cnt--; // cnt > 1,cnt--即可
else if(tr[p].l || tr[p].r){ // 不是叶子节点
if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val){ // 右子树不存在或者左边的值大于右边,左儿子充当父节点,进行右旋
zig(p);
rm(tr[p].r, key); // 右旋后,原来父节点在 p 指针右儿子上
}
else{ // 否则,右儿子充当父节点,进行左旋
zag(p);
rm(tr[p].l, key); // 左旋后,原来父节点在 p 指针左儿子上
}
}
else p = 0; // 叶子节点直接删掉
}
else if(tr[p].key > key) rm(tr[p].l, key);
else rm(tr[p].r, key);
pushup(p); // 将下面的信息更新到 p 指针所指节点,由于是回溯,有自下向上的作用
}
int get_rank_by_key(int p, int key){ // 通过 key 找节点排名(第几小)
if(!p) return 0;
if(tr[p].key == key)
return tr[tr[p].l].size + 1; // 由于是最小排名,所以是左边子树大小 + 1
else if(tr[p].key < key) // 找排名往右边找
return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key); // 返回结果要加上左边子树和节点大小
else // 往左边找
return get_rank_by_key(tr[p].l, key);
}
int get_key_by_rank(int p, int rank){ // 通过节点排名找到节点的 key
if(!p) return 0;
if(tr[tr[p].l].size >= rank) // 左边大小已经大于rank,去左边找
return get_key_by_rank(tr[p].l, rank);
else if(tr[tr[p].l].size + tr[p].cnt >= rank) // 加上自己就大于rank,就在p处
return tr[p].key;
else // 否则在右边,排名要减去左边比他小的数目
return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int get_prev(int p, int key){ // 查找小于 key 的最大数
if(!p) return -INF;
if(tr[p].key >= key) return get_prev(tr[p].l, key); // 当前 key >= 目标 key, 往左边找
else return max(tr[p].key, get_prev(tr[p].r, key)); // 当前 key < 目标 key,答案在当前 key 或者右边的子树中
}
int get_next(int p, int key){ // 查找大于 key 的最小数
if(!p) return INF;
if(tr[p].key <= key) return get_next(tr[p].r, key); // 当前 key <= 目标 key, 往右边找
else return min(tr[p].key, get_next(tr[p].l, key)); // 当前 key > 目标 key, 答案在当前 key 或者左边的子树中
}
int main(){
int m;
cin >> m;
build(); // 建立平衡树
while(m--){
int op, x;
cin >> op >> x;
if(op == 1) insert(root, x);
else if(op == 2) rm(root, x);
else if(op == 3) cout << get_rank_by_key(root, x) - 1 << endl;
else if(op == 4) cout << get_key_by_rank(root, x + 1) << endl;
else if(op == 5) cout << get_prev(root, x) << endl;
else if(op == 6) cout << get_next(root, x) << endl;
}
return 0;
}
Splay
平衡原理: 每次操作将节点旋转到根, splay(x, k)
将 $x$ 旋转到 $k$ 的下方
核心: Splay时刻保证中序遍历不变,第 $k$ 个数实际维护中序遍历的第 $k$ 个数
例题:维护数列(NOI 2005)
- 插入序列
- 删除区间
- 将连续区间修改为同一个数
- 翻转区间
- 对区间求和
- 求和区间最大子序列
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10, INF = 1e9 + 10;
struct Node{
int s[2], v, p; // p 父节点 v 值
int sum, ms, ls, rs, size; // 这里所有值的含义是,做完lazy标记操作后的值
int same, rev;
void init(int v_, int p_){
v = v_, p = p_;
s[0] = s[1] = rev = same = 0, size = 1; // 有重复利用,子树也要初始化
sum = ms = v;
ls = rs = max(v, 0); // ls和rs可以为0,但根据题意ms不能为0
}
}tr[N];
int nodes[N], root, idx, n, m, w[N], tt; // nodes[] 类似一个栈,不过里面存储了可以使用的节点编号
// 子节点更新父节点,有修改后pushup
void pushup(int u){
auto& t = tr[u], &l = tr[tr[u].s[0]], &r = tr[tr[u].s[1]];
t.size = l.size + r.size + 1;
t.sum = l.sum + r.sum + t.v; // 不同于线段树,这里要加上节点的值 t.v
t.ms = max(max(l.ms, r.ms), l.rs + r.ls + t.v);
t.ls = max(l.ls, l.sum + r.ls + t.v);
t.rs = max(r.rs, r.sum + l.rs + t.v);
}
// 父节点更新子节点lazy标记,递归前加入
void pushdown(int u){
auto& t = tr[u], &l = tr[tr[u].s[0]], &r = tr[tr[u].s[1]];
if(t.same){
t.rev = t.same = 0;
if(t.s[0]) l.v = t.v, l.same = 1, l.sum = t.v * l.size; // 左右子树存在才能更新
if(t.s[1]) r.v = t.v, r.same = 1, r.sum = t.v * r.size;
if(t.v > 0){
if(t.s[0]) l.ls = l.rs = l.ms = l.sum;
if(t.s[1]) r.ls = r.rs = r.ms = r.sum;
}
else{
if(t.s[0]) l.ls = l.rs = 0, l.ms = t.v;
if(t.s[1]) r.ls = r.rs = 0, r.ms = t.v;
}
}
else if(t.rev){
t.rev = 0, l.rev ^= 1, r.rev ^= 1;
swap(l.ls, l.rs), swap(r.ls, r.rs);
swap(l.s[0], l.s[1]), swap(r.s[0], r.s[1]);
}
}
// 旋转(左右合并)
void rotate(int x){
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
// 将节点 x 旋转到节点 k 下方(k 为 0,代表将 x 置为根)
void splay(int x, int k){
while(tr[x].p != k){
int y = tr[x].p, z = tr[y].p;
if(z != k){ // 如果 z 是 k,x 只用旋转一次
if(tr[z].s[0] == y != tr[y].s[0] == x) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root = x;
}
// 找到中序遍历序列中第 k 个数
int get_k(int k){
int u = root;
while(1){
pushdown(u);
int ls_sum = tr[tr[u].s[0]].size; // 左子树节点个数(不含节点本身)
if(ls_sum >= k) u = tr[u].s[0]; // ls_sum >= k,说明要找的点在左子树(中序遍历性质)
else if(ls_sum + 1 == k) return u; // ls_sum+1==k,说明要找的点是u
else k -= ls_sum + 1, u = tr[u].s[1]; // 否则k-=ls_sum+1,前往右子树查找
}
return -1;
}
// 插入节点,在此题使用递归建树build
void insert(int v){
int u = root, p = 0; // u 代表该结点,p 代表父节点
while(u) p = u, u = tr[u].s[v > tr[u].v]; // 从上往下根据 v 搜索到要插入的结点
u = ++idx;
if(p) tr[p].s[v > tr[p].v] = u; // 如果父节点不是空,根据 v 将父节点与该节点绑定
tr[u].init(v, p); // 初始化
splay(u, 0); // 操作完之后,将 u 旋转到根节点
}
// 在w[l, r] 上建立一课完全二叉树
int build(int l, int r, int p){
int mid = (l + r) >> 1;
int u = nodes[tt--];
tr[u].init(w[mid], p);
if(l < mid) tr[u].s[0] = build(l, mid - 1, u);
if(r > mid) tr[u].s[1] = build(mid + 1, r, u);
pushup(u); // 建完要pushup
return u;
}
// 中序遍历输出子树,在此题无用
void output(int u){
pushdown(u);
if(tr[u].s[0]) output(tr[u].s[0]);
if(tr[u].v >= 1 && tr[u].v <= n) cout << tr[u].v << " "; // 判断节点是不是哨兵
if(tr[u].s[1]) output(tr[u].s[1]);
}
// 遍历子树,将节点放入回收数组
void dfs(int u){
if(tr[u].s[0]) dfs(tr[u].s[0]);
if(tr[u].s[1]) dfs(tr[u].s[1]);
nodes[++tt] = u;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
tr[0].ms = w[0] = w[n + 1] = -INF; // 0 和 n + 1 为两个哨兵,因为要进行区间操作,需要哨兵
for(int i = 1; i < N; i++) nodes[++tt] = i;
for(int i = 1; i <= n; i++) cin >> w[i];
root = build(0, n + 1, 0); // 赋值根节点
while(m--){
string op;
int posi, tot, c;
cin >> op;
if(op == "INSERT"){
cin >> posi >> tot;
for(int i = 0; i < tot; i++) cin >> w[i];
int l = get_k(posi + 1), r = get_k(posi + 2); // 本来要找[posi,posi+1],由于有哨兵所以是[posi+1,posi+2];
splay(l, 0), splay(r, l); // 操作时,splay(l, 0), splay(r, l); r 的左子树就是[l,r]的区间
int u = build(0, tot - 1, r); // 将序列转换为平衡二叉树
tr[r].s[0] = u; // 接到区间上
pushup(r), pushup(l);
}
else if(op == "DELETE"){
cin >> posi >> tot;
int l = get_k(posi), r = get_k(posi + tot + 1);
splay(l, 0), splay(r, l);
dfs(tr[r].s[0]); // 遍历[l,r]子树,放入回收数组
tr[r].s[0] = 0; // 删除子树
pushup(r), pushup(l);
}
else if(op == "MAKE-SAME"){
cin >> posi >> tot >> c;
int l = get_k(posi), r = get_k(posi + tot + 1);
splay(l, 0), splay(r, l);
auto& son = tr[tr[r].s[0]];
son.same = 1; // 子树根节点same=1,然后更新根节点上的值
son.v = c, son.sum = son.size * c;
if(c > 0) son.ls = son.rs = son.ms = son.sum;
else son.ls = son.rs = 0, son.ms = c;
pushup(r), pushup(l);
}
else if(op == "REVERSE"){
cin >> posi >> tot;
int l = get_k(posi), r = get_k(posi + tot + 1);
splay(l, 0), splay(r, l);
auto& son = tr[tr[r].s[0]];
swap(son.ls, son.rs); // 前缀和后缀、左右子树都要翻转
swap(son.s[0], son.s[1]);
son.rev ^= 1;
pushup(r), pushup(l);
}
else if(op == "GET-SUM"){
cin >> posi >> tot;
int l = get_k(posi), r = get_k(posi + tot + 1);
splay(l, 0), splay(r, l);
cout << tr[tr[r].s[0]].sum << endl;
}
else cout << tr[root].ms << endl;
}
return 0;
}
树套树
线段树套平衡树
原理: 线段树维护整个区间,平衡树维护线段树节点区间内的有序序列
+ 仅涉及单点修改、区间前驱后继时,可以在线段树节点内设立 multiset
来替代平衡树
例题:树套树
l r x
,查询整数 $x$ 在区间 $[l,r]$ 内的排名。l r k
,查询区间 $[l,r]$ 内排名为 $k$ 的值。pos x
,将 $pos$ 位置的数修改为 $x$。l r x
,查询整数 $x$ 在区间 $[l,r]$ 内的前驱(前驱定义为小于 $x$,且最大的数)。l r x
, 查询整数 $x$ 在区间 $[l,r]$ 内的后继(后继定义为大于 $x$,且最小的数)。
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 5e4 + 10, M = 1500010, INF = 1e9;
// 空间计算:线段树节点4*n,每个节点固定2个哨兵等于 4 * n * 2,总共logn层每层长度为n
// 平衡树节点n * logn,最后空间 8 * n + logn * n <=> 1200000,开大点就1500010
struct Splay{
int v, p, s[2];
int size;
void init(int v_, int p_){
v = v_, p = p_;
size = 1;
}
}spl[M];
int idx, w[N], n, m;
void pushup(int u){
spl[u].size = spl[spl[u].s[0]].size + spl[spl[u].s[1]].size + 1;
}
void rotate(int x){
int y = spl[x].p, z = spl[y].p;
int k = spl[y].s[1] == x;
spl[z].s[spl[z].s[1] == y] = x, spl[x].p = z;
spl[y].s[k] = spl[x].s[k ^ 1], spl[spl[x].s[k ^ 1]].p = y;
spl[x].s[k ^ 1] = y, spl[y].p = x;
pushup(y), pushup(x);
}
void splay(int x, int k, int& root){
while(spl[x].p != k){
int y = spl[x].p, z = spl[y].p;
if(z != k){
if(spl[y].s[0] == x != spl[z].s[0] == y) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root = x;
}
int get_less(int v, int root){ // 找到比数值v小的数有多少个
int u = root, res = 0;
while(u){
if(v > spl[u].v) res += spl[spl[u].s[0]].size + 1, u = spl[u].s[1];
else u = spl[u].s[0];
}
return res;
}
int get_pre(int v, int& root){ // 获取v的前缀
int u = root, res = -INF;
while(u){
if(v > spl[u].v) res = max(res, spl[u].v), u = spl[u].s[1];
else u = spl[u].s[0];
}
return res;
}
int get_next(int v, int root){ // 获取v的后缀
int u = root, res = INF;
while(u){
if(v < spl[u].v) res = min(res, spl[u].v), u = spl[u].s[0];
else u = spl[u].s[1];
}
return res;
}
void insert(int v, int& root){
int u = root, p = 0;
while(u) p = u, u = spl[u].s[v > spl[u].v];
u = ++idx;
if(p) spl[p].s[v > spl[p].v] = u;
spl[u].init(v, p);
splay(u, 0, root);
}
struct T{
int l, r, u;
}tr[N << 2];
void update(int x, int y, int& root){ // 在splay中找到值为x的点并更新为y
int u = root;
while(u){
if(spl[u].v == x) break;
else if(spl[u].v < x) u = spl[u].s[1];
else u = spl[u].s[0];
}
splay(u, 0, root); // 节点x旋转到根
int l = spl[u].s[0], r = spl[u].s[1];
while(spl[l].s[1]) l = spl[l].s[1];
while(spl[r].s[0]) r = spl[r].s[0];
splay(l, 0, root), splay(r, l, root); // 找到x在序列中前一个节点和后一个节点,并splay到根
spl[r].s[0] = 0; // 删除节点x
pushup(r), pushup(l); // 删除(修改)后要pushup(r), pushup(l)
insert(y, root); // 将y插入,insert会嵌套splay嵌套rotate带有pushup
}
void change(int u, int pos, int x){
update(w[pos], x, tr[u].u); // 只要线段树节点维护的区间包含pos就需要update
if(tr[u].l == tr[u].r) return;
int mid = (tr[u].l + tr[u].r) >> 1;
if(pos <= mid) change(ls, pos, x);
else change(rs, pos, x);
}
int query(int u, int l, int r, int x){ // 查询x的排名
if(tr[u].l >= l && tr[u].r <= r){
return get_less(x, tr[u].u) - 1; // 查找的是小于x的数有多少个,因为包含哨兵需要-1
}
int mid = (tr[u].l + tr[u].r) >> 1, res = 0;
if(l <= mid) res += query(ls, l, r, x); // 整个区间小于x的数=左右区间小于x的数之和
if(r > mid) res += query(rs, l, r, x);
return res;
}
int query_pre(int u, int l, int r, int x){
if(tr[u].l >= l && tr[u].r <= r)
return get_pre(x, tr[u].u);
int mid = (tr[u].l + tr[u].r) >> 1, res = -INF;
if(l <= mid) res = max(res, query_pre(ls, l, r, x)); // 在区间中小于x的最大数是,左右区间小于x的数的max
if(r > mid) res = max(res, query_pre(rs, l, r, x));
return res;
}
int query_next(int u, int l, int r, int x){
if(tr[u].l >= l && tr[u].r <= r)
return get_next(x, tr[u].u);
int mid = (tr[u].l + tr[u].r) >> 1, res = INF;
if(l <= mid) res = min(res, query_next(ls, l, r, x)); // 与上同理
if(r > mid) res = min(res, query_next(rs, l, r, x));
return res;
}
void build(int u, int l, int r){
tr[u].l = l, tr[u].r = r; // tr[u].u会随着函数引用而改变
insert(-INF, tr[u].u), insert(INF, tr[u].u); // 每个平衡树都要加入哨兵
for(int i = l; i <= r; i++) insert(w[i], tr[u].u);
if(tr[u].l == tr[u].r) return;
int mid = (tr[u].l + tr[u].r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> w[i];
build(1, 1, n);
for(int i = 1; i <= m; i++){
int op, l, r, x, pos, k;
cin >> op;
if(op == 1){ // x 在[l,r]中排名
cin >> l >> r >> x;
cout << query(1, l, r, x) + 1 << endl; // query查询小于x的个数,成为x的排名需要+1
}
else if(op == 2){ // [l,r]中排名k的值
cin >> l >> r >> k;
int a = 0, b = 1e8;
while(a < b){ // 由于排名与值具有单调性,可以二分大小来找到排名为k的数
int mid = (a + b + 1) >> 1;
if(query(1, l, r, mid) + 1 <= k) a = mid; // query查询小于x的个数,成为x的排名需要+1
else b = mid - 1;
}
cout << b << endl;
}
else if(op == 3){
cin >> pos >> x;
change(1, pos, x);
w[pos] = x;
}
else if(op == 4){
cin >> l >> r >> x;
cout << query_pre(1, l, r, x) << endl;
}
else{
cin >> l >> r >> x;
cout << query_next(1, l, r, x) << endl;
}
}
return 0;
}
AC自动机
原理
1. 很多都类比 KMP 算法,但有自己的优化(Trie图优化)
应用及扩展
+ 运用ne[]数组特性,同时cnt[]记录所有单词前缀的出现次数,从后向前累加所有cnt,记录单词节点位置,可以统计字符串中所有单词的出现次数
Trie图优化模板
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e4 + 10, S = 55; // 节点数 = 单词数 * 单词最大长度
int son[N * S][26], idx, ne[N * S];
int cnt[N * S], n;
string str;
void insert(string s){ // Trie 插入
int len = s.size(), p = 0;
for(int i = 0; i < len; i++){
int t = s[i] - 'a';
if(!son[p][t]) son[p][t] = ++idx;
p = son[p][t];
}
cnt[p]++;
}
void build(){ // 类似kmp,二维就进行宽搜,一层一层搜索
int len = str.size();
queue<int> q;
for(int i = 0; i < 26; i++) // 把第一层子节点先全放进去,kmp中i从2开始循环
if(son[0][i])
q.push(son[0][i]);
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0; i < 26; i++){ // 循环所有可能的子节点
int& p = son[t][i];
if(!p) p = son[ne[t]][i]; // 子节点不存在就跳往父节点ne指针指向的节点
else{
ne[p] = son[n[t]][i]; // if(p[i] == p[j + 1]) ne[i] = ++j;
q.push(p);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T;
cin >> T;
while(T--){
memset(son, 0, sizeof son);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
cin >> n;
for(int i = 0; i < n; i++){
cin >> str;
insert(str);
}
cin >> str;
build();
int len = str.size();
long long res = 0;
for(int i = 0, j = 0; i < len; i++){
int t = str[i] - 'a';
j = son[j][t]; // 由于末尾节点指向空节点即根,相当于遍历了整个trie
int p = j;
while(p){
res += cnt[p];
cnt[p] = 0; // 访问过的节点 cnt 要清零,避免重复计算
p = ne[p]; // 指向ne指针指向的节点
}
}
cout << res << endl;
}
return 0;
}
搜索与图论
DFS 深搜
枚举
指数型枚举
选与不选
// 指数型枚举
void dfs(int u){
if(u > n){
for(auto t: v)
printf("%d ", t);
printf("\n");
return ;
}
v.pb(u); // 选
dfs(u + 1);
v.pob();
dfs(u + 1); // 不选
}
$n$ 皇后枚举示例
两者区别主要在dfs参数所维护的信息导致搜索的顺序不同
按每一个格子选与不选进行枚举
void dfs(int x, int y, int s){
if(y == n){ // 超出横轴,换到下一层继续枚举
y = 0;
x++;
}
if(x == n){
if(s == n){
for(int i = 0; i < n; i++)
puts(g[i]);
puts("");
}
return; // 要return防止爆栈
}
// 不选当前格子
dfs(x, y + 1, s);
// 选当前格子
if(!dg[x + y] && !udg[x - y + n] && !row[x] && !col[y]){
g[x][y] = 'Q';
dg[x + y] = udg[x - y + n] = row[x] = col[y] = true;
dfs(x, y + 1, s + 1);
dg[x + y] = udg[x - y + n] = row[x] = col[y] = false;
g[x][y] = '.';
}
}
按列进行枚举
// 按行枚举
void dfs(int u){
if(u == n){
for(int i = 0; i < n; i++)
puts(g[i]);
puts("");
}
for(int i = 0; i < n; i++){ // 枚举列
if(!col[i] && !udg[u - i + n] && !dg[u + i]){
g[u][i] = 'Q';
col[i] = udg[u - i + n] = dg[u + i] = true;
dfs(u+1);
col[i] = udg[u - i + n] = dg[u + i] = false;
g[u][i] = '.';
}
}
}
组合型枚举
// 组合型枚举
void dfs(int u){
if(ans.size() > m || ans.size() + (n - u + 1) < m) // 指数型枚举剪枝
return;
if(ans.size() == m){
for(auto t: ans)
printf("%d ", t);
printf("\n");
return;
}
ans.pb(u);
dfs(u + 1);
ans.pob();
dfs(u + 1);
}
排列型枚举
// 排列型枚举
void dfs(int u){ // u 记录当前枚举到哪个位置了
if(u > n){ // 枚举完了所有就输出然后return
for(auto t : ans)
printf("%d ", t);
printf("\n");
return;
}
for(int i = 1; i <= n; i++){
if(!st[i]){
st[i] = true;
ans.pb(i);
dfs(u + 1);
ans.pob(); // 回溯
st[i] = false;
}
}
}
BFS 宽搜
bfs 一圈一圈地慢慢进行搜索。
解题考虑以下两点:
1. 队列中节点维护的信息是什么
2. 如何解决bfs中距离的表示
通用模板
BFS一定注意进入队列中的单个节点维护的信息,这很重要。
int bfs(){
queue<PII> q;
q.push({1,1});
d[1][1] = 0; // 标记距离左上角的距离,同时初始化为-1,不为-1则代表已访问
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int x= t.first + dx[i], y = t.second + dy[i];
if(x < 1 || x > n || y < 1 || y > m || d[x][y] != -1 || g[x][y] == 1)
continue;
d[x][y] = d[t.first][t.second] + 1;
q.push({x,y});
}
}
return d[n][m];
}
八数码例题
- 队列节点为 $string$
- 哈希表映射每个字符串状态的距离
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
unordered_map<string, int> d;
string ed = "12345678x";
int bfs(string st){
queue<string> q;
q.push(st);
d[st] = 0;
while(q.size()){
auto t = q.front();
q.pop();
int dist = d[t];
if(t == ed) return dist;
int k = t.find('x');
for(int i = 0; i < 4; i++){
int x = k / 3 + dx[i], y = k % 3 + dy[i];
if(x < 0 || x > 2 || y < 0 || y > 2) continue;
swap(t[k], t[x * 3 + y]);
if(!d.count(t)){
d[t] = dist + 1;
q.push(t);
}
swap(t[k], t[x * 3 + y]);
}
}
return -1;
}
树与图的存储
- 树是一种特殊的图,与图的存储方式相同
- 对于无向图存储 $ab$ ,存储两条有向边, $a->b$, $b->a$
邻接矩阵存储
g[a][b] = a->b
邻接表存储
int h[N], e[N], ne[N], w[N], idx;
// 添加边a->b
void add(int a, int b, int c){
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int main(){
memset(h, -1, sizeof h);
...
return 0;
}
树与图的遍历
时间复杂度
$O(n + m)$, $n$ 表示点数, $m$ 表示边数
dfs 深度优先遍历
例题
AcWing 846. 树的重心
dfs返回int,可以维护子树中节点数量
void dfs(int u){
st[u] = true;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(!st[j])
dfs(j);
}
}
bfs 宽度优先遍历
有时可以用一个数组同时维护标记和距离功能
#include<queue>
void bfs(){
queue<int> q;
q.push(1); // 首元素入列
st[1] = true; // 入列就标记
while(q.size()){ // 队列不为空
int t = q.front(); // 取队首
q.pop(); // 记得pop
for(int i = h[t]; ~i; i = ne[i]){ // 遍历所有方向
int j = e[i];
if(!st[j]){ // 没到过或符合遍历条件
q.push(j)
st[j] = true; // 入队并标记
}
}
}
}
拓扑排序
拓扑图又称有向无环图,拓扑序列中左右顺序一定满足边的起点到终点。
void topo(){
queue<int> q;
for(int i = 1; i <= n; i++){
if(!indegree[i]){
q.push(i);
ans.pb(i);
}
}
while(q.size()){
auto t = q.front();
q.pop();
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
indegree[j]--;
if(!indegree[j]){
q.push(j);
ans.pb(j);
}
}
}
}
最短路问题
$n$ 表示点数, $m$ 表示边数。
+ 单源最短路
+ 所有边权都是正数
+ 朴素 dijkstra 算法 $O(n^2)$ (适合稠密图)
+ 堆优化 dijkstra 算法 $O(m*logn)$ (适合稀疏图,$m$ 和 $n$ 一个数量级)
+ 存在负权边
+ Bellman-Ford 算法 $O(n*m)$ (不超过 $k$ 条边可以使用)
+ SPFA 算法 一般 $O(m)$, $O(n*m)$
+ 多源汇最短路
+ Floyd 算法 $O(n^3)$
Dijkstra 算法
朴素Dijkstra $O(n^2)$
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510; // 点数
int g[N][N],dist[N]; // g[][]以邻接矩阵形式存取点和边,dist[]存各点到第一个点的最短距离
bool st[N]; // 记录每个点是否已经确定最短路
int n,m;
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
// 循环n次
for(int i = 1;i <= n;i++){
int t = -1;
// 找出未确定最短路的点中,距第一个点距离最短的点 (贪心证明,硬记即可)
for(int j = 1;j <= n;j++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true; // 标记
for(int j = 1;j <= n;j++)
dist[j] = min(dist[j],g[t][j] + dist[t]);
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
// 自环自动忽略,重边取最短
g[x][y] = min(g[x][y],z);
}
cout << dijkstra() << endl;
return 0;
}
堆优化Dijkstra $O(m*logm = m *logn)$
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 150010;
// 代表一个点,first 表示 点到根节点最短距离,second 表示 点的编号
typedef pair<int,int> PII;
int e[N],ne[N],h[N],w[N],idx; // 稀疏图,采用邻接表的形式存储
int n,m,dist[N]; // dist[] 记录各点到根节点的最短距离
bool st[N]; // 标记点是否已更新出最小值
void add(int a,int b,int c){
w[idx] = c; e[idx] = b; ne[idx] = h[a];h[a] = idx++;
}
int dijkstra(){
// 优先队列,递增存储建立小根堆,存储最短边,此种堆不能删除修改指定元素
priority_queue <PII, vector<PII>, greater<PII>> heap;
memset(dist,0x3f,sizeof dist); // 初始化dist[]为无穷大
// 第一个节点到自己距离为0
dist[1] = 0;
heap.push({0,1});
while(heap.size()){
PII t = heap.top(); // 取出最短距离的点
heap.pop();
int distance = t.first, ver = t.second; // 提取最短距离的编号
if(st[ver]) continue; // 若该点已更新了到根节点最短距离,continue
st[ver] = true; // 未更新,标记为true
// 用该点更新其他点的距离
for(int i = h[ver];i != -1;i = ne[i]){
int j = e[i];
// 如果(j 到原点的距离) > (原点到 t 的距离 + t 到 j 的距离) ,更新j的最短距离
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
heap.push({dist[j],j}); // 将j点更新的信息加入堆中
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1; // 表明n的距离未被更新,不存在连通的边从原点到n
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h); // 邻接表初始化表头为-1
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); // 后续函数自动使用最短边,可以不考虑重边问题
}
cout << dijkstra() << endl;
return 0;
}
Bellman-Ford 算法
const int N = 510,M = 10010, INF = 0x3f3f3f3f;
int dist[N],last[N]; // dist[]记录到原点的距离,last[]做备份,因为负权边的存在防止串联
int n,m,k;
// 结构体数组存 点和边
struct Edge{
int a,b,w;
}edges[M];
int bellman_ford(){
memset(dist, 0x3f,sizeof dist);
dist[1] = 0;
for(int i = 0;i < k;i++){ // 最多走 k 条边的最短距离
memcpy(last,dist,sizeof dist); // 拷贝
for(int j = 0;j < m;j++){ // 更新最短距离
auto e = edges[j];
// 与dijkstra相似,注意后者距离为备份距离last[e.a]
dist[e.b] = min(dist[e.b], last[e.a] + e.w);
}
}
return dist[n]; // 存在负权边,判断dist[n] > INF / 2 就输出 impossible,具体值根据题目范围
}
spfa 算法
spfa求最短路
$spfa$ 与 $dijkstra$ 代码相似,与 $bellman_ford$ 算法主要在于:
+ 用 $dist$ 值变小的点来更新其他的点,而不是遍历了所有的边
int spfa(){
memset(dist,0x3f,sizeof dist); // 初始化距离
dist[1] = 0;
queue<int> q; // 建立队列,并放入第一个点,队列存取的是点的编号
q.push(1);
st[1] = true; // 标记第1个点已经放入队列
// 队列不空
while(q.size()){
int t = q.front(); // 取队头
q.pop();
st[t] = false; // 标记队头已不在队列中
for(int i = h[t];i != -1;i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i]; // 更新距离
// 如果j未在队列中,则将其放入队列来更新其他点
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
spfa 判断负环
- 不用初始化 $dist$ 数组
- 要把每个点都预先加入队列中
int ne[N],e[N],w[N],dist[N],h[N],idx,n,m;
bool st[N];
int cnt[N]; // 记录到某一点所需要经历的边数
// 代码主体与spfa相同,区别点主要有两处: 无距离dist的初始化,每个点都预先放入队列之中
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
bool spfa(){
queue<int> q;
for(int i = 1;i <= n;i++){
q.push(i);
st[i] = true;
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t];i != -1;i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1; // 在前一个点的cnt的基础上+1
// cnt大于n说明其中至少有n+1个点,由抽屉原理可知,其中一定有环并且是负环
if(cnt[j] >= n) return true;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false; // 无异常返回false
}
Floyd 算法
- 基于 $DP$, $f[k][i][j]$ 表示从 $i$ 出发经过 $k$ 点到 $j$ 的最短路
- 处理自环就是把 $g[i][i] = 0$
状态转移方程:
$$g[k][i][j] = min(g[k][i][j], g[k-1][i][k] + g[k-1][k][j])$$
void init(){
memset(g, 0x3f, sizeof g);
for(int i = 1; i <= n; i++)
g[i][i] = 0; // 自环为0
}
void floyd(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]); // 优化掉了第一维空间
}
最小生成树
$n$ 代表点数, $m$ 代表边数
+ $Prim$ 算法
+ 朴素版 $Prim$ $O(n^2)$ (稠密图)
+ 堆优化 $Prim$ $O(m*logn)$ (不常用)
+ $Kruskal$ 算法 $O(m*logm)$ (稀疏图)
朴素版 Prim 算法 $O(n^2)$
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
int g[N][N],dist[N]; // 邻接矩阵存图中点和边,dist[]存取某点到集合的距离(到集合中所有点的最短距离)
int n,m;
bool st[N]; // 标记数组
int prim(){
memset(dist,INF,sizeof dist);
int res = 0;
for(int i = 0;i < n;i++){
int t = -1; // t在for循环里面
for(int j = 1;j <= n;j++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if(i && dist[t] == INF) return INF; // 表明图未连通
if(i) res += dist[t]; // 先写res后更新dist,排除自环
// 注意dist[j] 和 g[t][j] 取最小,和dijkstra加以区分
for(int j = 1;j <= n;j++) dist[j] = min(dist[j],g[t][j]);
// 标记
st[t] = true;
}
return res;
}
int main(){
cin >> n >> m;
memset(g,INF,sizeof g); // 初始化边为无穷大
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u][v] = g[v][u] = min(g[u][v],w); // 无向图
}
int t = prim();
if(t == INF) puts("impossible");
else printf("%d",t);
return 0;
}
堆优化版 Prim 算法 $O(m * logn)$
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 510, MAXM = 2 * 1e5 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[MAXM], e[MAXM], w[MAXM], ne[MAXM], idx;
bool vis[MAXN];
int n, m;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int Prim()
{
memset(vis, false, sizeof vis);
int sum = 0, cnt = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, 1});
while (!q.empty())
{
auto t = q.top();
q.pop();
int ver = t.second, dst = t.first;
if (vis[ver]) continue;
vis[ver] = true, sum += dst, ++cnt;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (!vis[j]) {
q.push({w[i], j});
}
}
}
if (cnt != n) return INF;
return sum;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; ++i)
{
int a, b, w;
cin >> a >> b >> w;
add(a, b, w);
add(b, a, w);
}
int t = Prim();
if (t == INF) cout << "impossible" << endl;
else cout << t << endl;
}
Kruskal 算法 $O(m*logn)$
- 从小到大对所有边排序
- 枚举所有边,端点不在同一个连通块内就连起来,只到连完所有点
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m, p[N];
void init(){ // 初始化并查集
for(int i = 1; i <= n; i++)
p[i] = i;
}
int find(int x){ // 查找操作
if(x != p[x]) return p[x] = find(p[x]);
return p[x];
}
struct Edge{ // 结构体存边
int a, b, w;
bool operator < (const Edge& W) const{
return w < W.w;
}
}edges[N];
int kruskal(){
int cnt = 0, res = 0;;
for(int i = 0; i < m; i++){
if(cnt >= n - 1) break;
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if(a != b){ // a 和 b 不在一个连通块内
p[b] = a;
cnt++;
res += w;
}
}
if(cnt < n - 1) // 连接的边数小于 n - 1 表明没有最小生成树
return INF;
return res;
}
int main(){
cin >> n >> m;
init();
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
sort(edges, edges + m); // 从小到大排序所有边
int ans = kruskal();
if(ans == INF)
puts("impossible");
else
printf("%d", ans);
return 0;
}
次小生成树
次小生成数是最小生成树的邻集,仅有一条边与最小生成树不同。
两种方式求次小生成树:
+ 求最小生成树,枚举删去最小生成树的每条边,再求依次最小生成树(不能保证得到严格此小生成树) $O(mlogm + nm)$
+ 求最小生成树,标记每条边是否在最小生成树中,预处理树中点到点之间路径中边权最大值和次大值,枚举非树边,将该边添加到树中,并删去最大边权或者次大边权(枚举边长度与最大边权相等时)的树边,最后得到此小生成树(可以得到严格此小生成树)$O(mlogm + n^2)$
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 510, M = 1e4 + 10;
int h[N], e[2 * N], ne[2 * N], w[2 * N], idx;
int dist1[N][N], dist2[N][N], n, m, p[N]; // dist1[][] 存点到点最大边权,dist[][] 存次大边权
// 求次小生成树
struct Edge{
int a, b, w;
bool f;
bool operator < (const Edge & W) const{
return w < W.w;
}
}edges[M];
void init(){
for(int i = 1; i <= n; i++)
p[i] = i;
}
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[]){
d1[u] = maxd1; // 根据最小生成树的特性,可以直接update
d2[u] = maxd2;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j != fa){
int t1 = maxd1, t2 = maxd2; // 一定用临时变量存储,后续还要用到maxd1, maxd2;
if(w[i] > t1){ // 更新最大边和次大边
t2 = t1;
t1 = w[i];
}
else if(w[i] > t2 && w[i] < t1) // 更新次大边
t2 = w[i];
dfs(j, u, t1, t2, d1, d2);
}
}
}
int main(){
cin >> n >> m;
init();
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++)
cin >> edges[i].a >> edges[i].b >> edges[i].w;
sort(edges, edges + m);
ll sum = 0, res = 1e18;
for(int i = 0; i < m; i++){
auto t = edges[i];
int a = t.a, b = t.b, w = t.w;
int pa = find(a), pb = find(b);
if(pa != pb){
p[pa] = pb;
sum += w;
edges[i].f = true; // 标记为树边
add(a, b, w), add(b, a, w); // 建树
}
}
for(int i = 1; i <= n; i++) // 预处理点到点之间的最大边权和次大边权
dfs(i, -1, 0, 0, dist1[i], dist2[i]);
for(int i = 0; i < m; i++){
if(!edges[i].f){
auto t = edges[i];
int a = t.a, b = t.b, w = t.w;
if(w > dist1[a][b]) // 大于最大边
res = min(res, sum + w - dist1[a][b]);
else if(w > dist2[a][b]) // 小于等于最大边权,大于次大边权
res = min(res, sum + w - dist2[a][b]);
}
}
cout << res << endl;
return 0;
}
二分图
-
染色法 $O(n + m)$
-
匈牙利算法 $O(m*n)$,实际小于 $O(m*n)$
二分图无奇数环,分成的两部分中无边,即原图中一条边的两端点不能是同色,否则不是二分图
染色法判断是否二分图
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
// 模板思路:二分图无奇数环,分成的两部分中无边,即原图中一条边的两端点不能是同色,否则不是二分图
int n,m;
int e[N],ne[N],h[N],idx; // 邻接表存图
int color[N]; // 色彩数组,分两个颜色,1和2
void add(int a, int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
bool dfs(int u,int c){
color[u] = c;
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(!color[j]){
if(!dfs(j,3 - c)) return false; // 染成 3-c 的颜色,原1则染2,原2则染1
}
else if(color[j] == c) return false; // 和另一点颜色相同,非二分图
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
bool flag = true;
for(int i = 1;i <= n;i++){
if(!color[i])
if(!dfs(i,1)){ // 染色出问题
flag = false;
break;
}
}
if(flag) puts("Yes");
else puts("No");
}
二分图的最大匹配数
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510,M = 1e5 + 10;
int ne[M],e[M],h[N],idx; // 邻接表存图
int n1,n2,m;
int match[N]; // 存每个女生对应的是哪个男生
bool st[N]; // 标记对于某个男生来说,女生是否已经匹配过
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
bool find(int x){
for(int i = h[x];i != -1;i = ne[i]){
int j = e[i];
if(!st[j]){
st[j] = true;
// 女生还没有匹配过,或已经匹配的男生可以再找另一个合适的
if(match[j] == 0 || find(match[j])){
match[j] = x;
return true;
}
}
}
return false; // 都不行就返回false
}
int main(){
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof h); // 初始化表头
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
int res = 0;
for(int i = 1;i <= n1;i++){
memset(st,false,sizeof st); // 对于每个男生要从前向后匹配,需要memset
if(find(i)) res++;
}
printf("%d\n",res);
return 0;
}
数论
快速幂&高精度
快速幂
typedef long long ll;
// solution1
ll qmi(ll a, ll k, ll p){ // a^k mod p
ll res = 1;
while(k){
if(k & 1)
res = res * a % p; // int res = 1LL * res * a % p
k >>= 1;
a = a * a % p; // int a = 1LL * a * a % p;
}
return res;
}
// solution 2
int qmi(int a, long long b){
int res = 1;
for(; b; b >>= 1){
if(b & 1)
res = (long long) res * a % mod;
a = (long long) a * a % mod;
}
return res;
}
// solution 3
long long quick_pow(long long x,long long y, ll p)
{
if(y==1) return x;
if(y==0) return 1; //1,2两种情况的代码一定要放在第3种情况之前
if(y%2==0) return quick_pow(x*x%p,y/2);
if(y%2!=0) return x*quick_pow(x*x%p,y/2)%p;
}
快速加(高精度乘)
有模数,$a*b\mod p$
// solution1 类似于快速幂思想,将k拆为二进制数
typedef long long ll;
ll qmult(ll a, ll k, ll p){
ll res = 0;
while(k){
if(k & 1)
res = (res + a) % p;
k >>= 1;
a = (a * 2) % p;
}
return res;
}
// solution2 源自进阶指南,利用ull自动取模,和long double的保留整数
ull mul(ull a, ull b, ull p){
a %= p, b %= p;
ull c = (long double) a * b / p;
ull x = a * b, y = c * p;
ull res = x - y;
if(res < 0) res += p;
return res;
}
无模数,$a*b$
vector<int> mul(vector<int> a, int b)
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i ++ )
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
// while(C.size()>1 && C.back()==0) C.pop_back();//考虑b==0时才有pop多余的0 b!=0不需要这行
return c;
}
质数
试除法判定质数
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
试除法分解质因数
无论怎么分解,循环范围一定在 $sqrt(n)$ 之内,大于 $sqrt(n)$ 的质数单独判断。
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0) // i是x的因数,并且一定是质数,如果是合数,x一定早就被i因数整除。所以不是合数
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl; // i位因数 s为指数
}
if (x > 1) cout << x << ' ' << 1 << endl; // 注意会剩最大因数
cout << endl;
}
// another version
int p[N], c[N], cnt; // p[]存所有的质因数, c[]存对应质因数的指数, cnt存质因数个数
void divide(int n) {
cnt = 0;
for(int i = 2; i <= n / i; i++){
if(n % i == 0){
p[++cnt] = i, c[cnt] = 1;
while(n % i == 0) n /= i, c[cnt]++;
}
}
if(n > 1)
p[++cnt] = n, c[cnt] = 1;
}
朴素筛 $O(nloglogn)$
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
线性筛(欧拉筛)$O(n)$
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
约数
gcd最大公约数
typedef long long ll;
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
约数个数及约数之和
-
$对a\subset Z进行质因数分解:\bf{a=\Pi_{i=1}^kp_i^{n_i}},k是质因数个数,n_i是一个质因数指数$
-
$求对\forall a\subset N^+的约数个数:$
$\quad \because对于每个p_i指数取0,1\dots n有n+1种选法,不同的p_i相乘可得到不同的约数。$
$\quad \therefore故由乘法原理得,约数个数为 \prod_{i=1}^k(n_i + 1)$
-
$求对\forall a\subset N^+的所有约数之和:$
$\because \forall m是a的约数,m由每个质因数取其不同的指数相乘而得$
$\therefore 约数之和=(p_1^0+p_1^1+\dots+p_1^{n_0})\times\dots\times()(p_k^0+p_k^1+\dots+p_k^{n_k})$
$将上述式子简化得:$
$约数之和=\Pi_{j=1}^k(\sum_{i=0}^np_j^i)$
unordered_map<int, int> primes;
const int p = 1e9 + 7;
typedef long long ll;
// 约数个数定理:质因数分解a= π(pi^(ai^n)),在每个pi部分有0~ai^n共 n + 1种取法,乘法原理可得结论
// 约数之和定理: a = π(∑pi^a(ij)) (i外,j内)
int main(){
int n;
scanf("%d", &n);
while(n --){
int x;
scanf("%d", &x);
for(int i = 2; i <= x / i; i++){
while(x % i == 0){ // while
primes[i] ++;
x /= i;
}
}
if(x > 1)
primes[x]++;
}
// 约数个数
ll ans = 1;
for(auto t: primes){
ans = ans * (t.second + 1) % p;
}
printf("%lld\n", ans);
// 约数之和
ll ans = 1;
for(auto t: primes){
ll k = 1;
while(t.second--){
k = (k * t.first + 1) % p;
}
ans = (ans * k) % p;
}
printf("%lld\n", ans);
return 0;
}
欧拉函数
欧拉函数公式实现
$\phi(n)=n\times\Pi_{i=1}^k(1-\frac{1}{p_i})\color{black},p_i是n的质因子,k是质因数个数$
$\phi(n)$ 大小为小于 $n$ 与 $n$ 互质整数个数。
typedef long long ll;
// 欧拉函数:对n而言 = n * π(1 - 1/pi), pi为其每一个质因数
ll ans = a;
for(int i = 2; i <= a / i; i++){
if(a % i == 0){
ans = ans / i * (i - 1); // 先除i,防小数,防溢出
while(a % i == 0) a /= i;
}
}
if(a > 1) ans = ans / a * (a - 1);
printf("%lld\n", ans);
筛法求欧拉函数 $O(nloglogn)$
求 $n$ 的欧拉函数前缀和
typedef long long ll;
// 欧拉函数: f(n) = n * π(1 - 1÷pi)
int primes[N];
bool st[N];
int phi[N];
int cnt = 0;
ll get_eulers(int n){
phi[1] = 1; // 1的欧拉函数是1
for(int i = 2; i <= n; i++){
if(!st[i]){
primes[cnt++] = i;
phi[i] = i - 1;
}
for(int j = 0; primes[j] <= n / i; j++){
st[primes[j] * i] = true;
if(i % primes[j] == 0){
phi[i * primes[j]] = phi[i] * primes[j];
// primes[j]在phi[i]中出现过,只乘primes[j]就行
break;
}
// primes[j]是i * primes[j] 最小质因子,且不是i的质因子
phi[i * primes[j]] = phi[i] * (primes[j] - 1); // = phi[i] * (phi[primes[j])
}
}
ll ans = 0; // longlong防爆int
for(int i = 1; i <= n; i++)
ans += phi[i];
return ans;
}
扩展欧几里得算法(exgcd)
exgcd
$对于一堆整数,求出\color{navy}{\exists x,y\subset Z}\color{black},使得\color{navy}{a\times x+b\times y=gcd(a,b)}$
// 通过 d = gcd(a, b) = gcd(b, a % b) = ax + by = ax + b(y - b * (a / b))建立等式
void exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return;
}
// printf("before:a=%d b=%d x=%d y=%d\n", a, b, x, y);
exgcd(b, a % b, y, x); // 一直递归到边界,x,y具体值不会变
// printf("after:a=%d b=%d x=%d y=%d\n", a, b, x, y);
y -= a / b * x; // 回溯更新x和y的值
}
解线性同余方程
$\color{black}对每组数求出一个x_i使\color{purple}{a_i\times x_i\equiv b_i (mod\space m_i)},\color{black}无解输出 \color{red}{impossible}$
$方程转化为ax + my = b, 有解则一定有 gcd(a, m) | b$
int main(){
int n;
scanf("%d", &n);
while(n--){
int a, b, m;
scanf("%d%d%d", &a, &b, &m);
int d = gcd(a, m);
if(b % d){ // 有解 一定有 gcd(a, m) | b
puts("impossible");
continue;
}
int x = 0, y = 0;
exgcd(a, m, x, y);
printf("%d\n", (ll)x * b / d % m); // x 乘 b / d 就行,要开开ll,并且%m
}
return 0;
}
中国剩余定理
高斯消元
组合数
$$C_a^b=\frac{a!}{b! * (a - b)!}$$
$$C_a^b = \frac{a*(a-1)*\cdots*(a-b+1)}{b!}$$
基础模型
隔板法
AcWing基础课讲到了 $4$ 种求组合数的方法,分别应对不同的数据范围
组合数 $I$
题意
求 $C_a^b \mod (10^9 + 7)$
数据范围
$1≤n≤10000, 1≤b≤a≤2000$
思路
$C_a^b = C_{a-1}^{b-1} + C_{a-1}^{b}$
const int N = 2010, mod = 1e9 + 7;
int c[N][N]; // c[a][b] -> C_a^b
void init(){
for(int i = 0; i < N; i++)
for(int j = 0; j <= i; j++) // b <= a
if(!j)
c[i][j] = 1;
else
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; // % mod
}
int main(){
int T;
cin >> T;
init();
while(T--){
int a, b;
cin >> a >> b;
cout << c[a][b] << endl;
}
return 0;
}
组合数 $II$
题意
求 $C_a^b \mod (10^9 + 7)$
数据范围
$1≤n≤10000, 1≤b≤a≤10^5$
思路
- 预处理出分子分母的阶乘
- $a/b \equiv a *b^{-1} \mod p$, $b^{-1}$ 为 $b$ 模 $p$ 的乘法逆元
const int N = 100010, mod = 1e9 + 7;
typedef long long ll;
int fact[N], infact[N];
// 预处理阶乘(n * logn)
int qmi(int a, int k){
int res = 1;
while(k){
if(k & 1)
res = 1LL * res * a % mod;
a = 1LL * a * a % mod;
k >>= 1;
}
return res;
}
int main(){
fact[0] = 1, infact[0] = 1;
for(int i = 1; i < N; i++){
fact[i] = 1LL * fact[i - 1] * i % mod;
// a / b 同余 a * b^{-1} % mod -> a * b^{mod - 2}; 费马小定理
infact[i] = 1LL * infact[i - 1] * qmi(i, mod - 2) % mod;
}
int T;
cin >> T;
while(T--){
int a, b;
cin >> a >> b;
// 中间 % mod 防溢出long long
cout << 1LL * fact[a] * infact[b] % mod * infact[a - b] % mod << endl;
}
return 0;
}
组合数 $III$ ( $Lucas$ 定理)
题意
输入 $a,b,p$ ,求 $C_a^b\mod p$ 的值
数据范围
$1≤n≤20$
$1≤b≤a≤10^{18}$
$1≤p≤10^5$
思路
+ 运用 $Lucas$ 定理:
$$C_a^b\equiv C_{a \% p}^{b \% p} * C_{a / p}^{b / p}\mod p$$
int qmi(int a, int k, int p){
int res = 1;
while(k){
if(k & 1)
res = 1ll * res * a % p;
a = 1ll * a * a % p;
k >>= 1;
}
return res;
}
int C(int a, int b, int p){
if(b > a) return 0;
int res = 1;
// C_a^b = \frac{a*(a-1)*\cdots *(a - b + 1)}{b!};
for(int i = 1, j = a; i <= b; i++, j--){
res = 1ll * res * j % p;
// 费马小定理,a / b 同余 a * b^{-1} 模 p, b^{-1} = b^{p-2}
res = 1ll * res * qmi(i, p - 2, p) % p;
}
return res;
}
// Lucas定理:
int lucas(ll a, ll b, int p){ // 参数 a,b 取 long long
if(a < p && b < p) return C(a, b, p);
return 1ll * C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main(){
int T;
cin >> T;
while(T--){
ll a, b, p;
cin >> a >> b >> p;
cout << lucas(a, b, p) << endl;
}
return 0; // 21
}
组合数 $IV$
题意
输入 $a,b$ ,求 $C_a^b$ 的值
结果很大需要高精度计算(没有 $\%$ 运算)
数据范围
$1\leq b\leq a\leq 5000$
思路
- 筛质数
- 求出每个质数在阶乘中出现的次数
- 遍历质数们,高精度乘法
int primes[N], cnt;
int sum[N];
bool st[N];
int a, b;
// 线性筛
void get_primes(int n){
for(int i = 2; i <= n; i++){
if(!st[i])
primes[cnt++] = i;
for(int j = 0; primes[j] <= n / i; j++){
st[i * primes[j]] = true;
if(i % primes[j] == 0)
break;
}
}
}
// 获取n!含p的指数
int get(int n, int p){
int res = 0;
while(n){
res += n / p;
n /= p;
}
return res;
}
// 高精度乘
vector<int> mult(vector<int> a, int b){
vector<int> c;
int t = 0;
for(int i = 0; i < a.size(); i++){
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while(t){
c.push_back(t % 10);
t /= 10;
}
return c;
}
int main(){
cin >> a >> b;
get_primes(a);
for(int i = 0; i < cnt; i++){
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector<int> res;
res.push_back(1);
for(int i = 0; i < cnt; i++){
int p = primes[i];
for(int j = 0; j < sum[i]; j++){
res = mult(res, p);
}
}
// 倒序输出
for(int i = res.size() - 1; i >= 0; i--)
cout << res[i];
return 0;
}
卡特兰数
$$方案数=C_{2n}^n - C_{2n}^{n - 1}=\frac{1}{n+1}*C_{2n}^n$$
例题
容斥原理
时间复杂度
通常来说为 $O(2^n)$
$$\bigcup_{i=1}^nS_i=\sum_{i=1}^{n}S_i-(S_1\bigcap S_2+S_1\bigcap S_3+\cdots+S_{n-1}\bigcap S_n)+\cdots+(-1)^{n-1}\bigcap_{i=1}^nS_i$$
例题
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 20;
int p[N];
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++)
cin >> p[i];
ll res = 0;
for(int i = 1; i < 1 << m; i++){ // 二进制枚举思想
ll t = 1, cnt = 0;
for(int j = 0; j < m; j++){
if(i >> j & 1){
t *= p[j]; // 此处可能溢出,开longlong
if(t > n){
t = -1;
break;
}
cnt ++;
}
}
if(t != -1){
if(cnt & 1) // 根据集合数量来决定加还是减
res += n / t;
else
res -= n / t;
}
}
cout << res << endl;
return 0;
}
博弈论
性质
+ 有限性: 无论两人怎样决策,都会在有限步后决出胜负。
+ 公平性: 即两人进行决策所遵循的规则相同。
P/N状态
P-position: P代表Previous,上一次行动的人有必胜策略的局面是P-position,也就是“先手必败”
N-position: N代表Next,当前行动的人有必胜策略的局面是N-position,也就是“先手可保证必胜”
P点: 即必败点,在双方都在最优策略下,玩家位于此点必败
N点: 即必胜点,在双方都在最优策略下,玩家位于此点必胜
胜态与必败态
+ 若面临末状态者为获胜则末状态为胜态,否则末状态为必败态
+ 一个局面是胜态的充要条件是该局面进行某种决策后成为必胜态
+ 一个局面是必败态的充要条件是该局面无论进行哪种决策均会成为胜态
nim游戏
每堆石子数异或和不为0,则先手必赢,否则输。
SG函数
SG定理
$$SG(b1,b2) = SG(b1)\oplus SG(b2)$$
#include<unordered_set>
// SG定理:sg(b1, b2) = sg(b1) ^ sg(b2)
// SG函数
int sg(int x){
if(f[x] != -1) return f[x];
unordered_set<int> S;
for(int i = 0; i < x; i++){
for(int j = 0; j <= i; j++)
S.insert(sg(i) ^ sg(j));
}
for(int i = 0; ; i++) // sg函数异或值可能大于x, 不要写条件
if(!S.count(i))
return f[x] = i;
}
动态规划
$dp$ 核心思想
一个集合代表了多种状态,形成优化
数字三角形模型
例题:传纸条
#include<iostream>
#include<cstring>
using namespace std;
const int N = 55;
int w[N][N];
int f[N + N][N][N]; // 与取方格状态相同,不再重复
// 状态表示:f[k][i1][i2]表示走到(i1, k-i1)(i2, k-i2)取到最大数
// 当i1 + j1 == i2 + j2时,两条路径可能重合,终点取f[2n][n][n];
// 状态转移:f[k][i1][i2] = max(f[k-1][i1-1][i2],..[i1][i2-1],...[i1][i2],...[i1-1][i2-1]) + w;
// w取值重合时取w[i1][k - i1],不重合再加上w[i2][k - i2];
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &w[i][j]);
for(int k = 2; k <= n + m; k++){
for(int i1 = 1; i1 <= n; i1++){
for(int i2 = 1; i2 <= n; i2++){
int j1 = k - i1, j2 = k - i2;
if(j1 < 1 || j1 > m || j2 < 1 || j2 > m) continue;
int t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];
int &x = f[k][i1][i2];
x = max(x, f[k - 1][i1][i2] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
// cout << x << " " << endl;
}
}
}
printf("%d", f[n + m][n][n]); // 两个坐标都要取到n,因为i1 i2都是横坐标
return 0;
}
LIS模型
背包模型
// 01背包:
// 完全背包: 532.货币系统
// 多重背包:
// 分组背包: 487.金明的预算方案 1020.潜水员 1013.机器分配
// 求具体方案: 1013.机器分配
输入统一 $n$ 表示物品个数, $m$ 表示背包体积大小
滚动数组优化:
- 用到$f[i-1]$ 的状态,将体积从大到小枚举
- 用到 $f[i]$ 的状态,将体积从小到大枚举
注意⚠️:需要求具体方案不能进行滚动数组优化
01背包
核心:选与不选
一般题意:
给定 $n$ 个物品,每个物品价值为 $w_i$ 且只有一个,背包容积为 $v$ ,求出所有方案的最大价值
状态表示: $f[i][j]$ 表示前 $i$ 个物品中,体积不超过 $j$ 的所有方案的最大价值
状态计算: $f[i][j]=max(f[i-1][j],f[i -1][j - v_i] + w_i)$
// 滚动数组(一维空间优化)
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
完全背包
状态转移证明:
- 用一个值 $f[i][j -v] + w$ 代表了前缀所有最大值,递推优化
$\because f[i][j] = max(f[i-1][j], f[i-1][j-v]+w,f[i-1][j-2v]+2w,\dots )$
$\& f[i][j-v] = max(f[i-1][j-v], f[i-1][j-v]+w, …)$
$\therefore f[i][j] = max(f[i][j], f[i][j-v_i] + w_i)$
一般题意:
有 $N$ 种物品和一个容量是 $V$ 的背包,每种物品都有无限件可用。第 $i$ 种物品的体积是 $v_i$ ,价值是 $w_i$ 。
求解选哪些物品进入背包,可使背包在不超容的情况下总价值最大。
状态表示: $f[i][j]$ 表示在前 $i$ 个物品中选取总体积不超过 $j$ 的所有方案的最大价值
状态计算: $f[i][j]=max(f[i-1][j],f[i][j - v_i] + w_i)$
// 滚动数组(一维空间优化)
for(int i = 1; i <= n; i++){ // 枚举每个物品组
for(int j = v; j <= m; j++) // 和01背包不同的是状态有从f[i][j-v[i]]转移,所以j从小到大枚举
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
多重背包
核心: 针对不同的数据范围,掌握 $2$ 种对多重背包的优化方法(二进制优化 & 单调队列优化)
一般题意:
有 $N$ 种物品和一个容量是 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件,每件体积是 $v_i$ ,价值是 $w_i$。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
多重背包 $I$
数据范围:
$0<N,V≤100$
$0<v_i,w_i,s_i≤100$ (不绝对大概这个量级)
状态表示: $f[i][j] $ 表示前 $i$ 个物品总体积不超过 $j$ 的最大价值
状态计算: $f[i][j] = max(f[i][j], f[i-1][j - k * v_i + k * w_i])$
把这种多重背包看成特殊的完全背包,或者完全背包看成特殊的多重背包都可以。堆循环即可
(代码略)
多重背包 $II$ (二进制优化)
时间复杂度:$O(n\times m\times \log{s})$
数据范围:
$0<N≤1000$
$0<V≤2000$
$0<v_i,w_i,s_i≤2000$
二进制优化转化为01背包证明:
$\because 每一个s_i都可以以二进制表示表示成s_i=1+2+4+8+\dots+2^{k-1}+c\quad(c可以不是2的幂)$
$设对于每个s_i,c<2^k,拆成k个物品,则每个物品的体积是2^{k_i}\times w$
$\therefore 所有物品被拆分成了cnt个物品(cnt=\sum_{j=1}^{n}{k_j}),对每个物品的选择决策就是一个01背包问题$
const int N = 25000; // 2000 * 1000 * log2000
int n,m;
int f[N];
int v[N], w[N], s[N];
int main(){
scanf("%d%d", &n, &m);
int cnt = 0; // 记录总共分成了多少件物品
for(int i = 1; i <= n; i++){
int a, b, s;
scanf("%d%d%d", &a, &b, &s); // 体积 质量 个数
int k = 1;
while(k <= s){ // s = 1 + 2 + 4 +...+ 2^k + c;
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s > 0){ // 剩余常数c
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for(int i = 1; i <= n; i++){ // 循环部分与01背包相同
for(int j = m; j >= v[i]; j--){
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
printf("%d\n", f[m]);
return 0;
}
多重背包 $III$ (单调队列优化)
时间复杂度:$O(n\times m)$
数据范围:
$0<N≤1000$
$0<V≤20000$
$0<v_i,w_i,s_i≤20000$
单调队列优化证明:
详情参考此篇题解
每次枚举物品组开始时,备份数组保存 $f[i-1]$ 的信息,进而使用一维状态
把 $m$ 表示成 $k*v + j$ $(j=m\%v)$ , $f[j+k*v]=max(f[j+k_i*v]+(k-k_i)*w)\quad while(k_i≤k)$
因为想用单调队列维护最大值,所以队头的数不能发生变化,故转化为:
$f[j+k*v]=max(f[j+k_i*v-k_i*w])+k*w$
单调队列维护问题,重要的两点:
1. 维护队列元素的个数,如果不能继续入队,弹出队头元素
2. 维护队列的单调性,即:$尾值 >= dp[j + k*v] - k*w$
// 队列元素维护的是f[]的下标
int main(){
int n, V;
cin >> n >> V;
while(n--){
int v, w, s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f); // 用g[]备份dp[i-1][]的状态
for(int j = 0; j < v; j++){
int hh = 0, tt = -1; // 每次枚举j的时候重置队列
for(int k = j; k <= V; k += v){
if(hh <= tt && q[hh] < k - v * s) // 窗口元素过多
hh++;
if(hh <= tt) // 队列存在,更新f[k], g[q[hh]]本身包含+(q[hh] - j)/v*w;
f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w < g[k] - (k - j) / v * w)
tt--; // 队尾元素小于等于/小于 g[k]-(k-j)/v*w,剔除队列
q[++tt] = k; // 记得入队
}
}
}
cout << f[V] << endl;
return 0;
}
分组背包
先枚举物品组、再从大到小枚举体积、枚举组内决策
一般题意:
有 $N$ 组物品和一个容量是 $V$ 的背包。每组物品有若干个,同一组内的物品最多只能选一个。每件物品的体积是 $v_{ij}$,价值是 $w_{ij}$,其中 $i$ 是组号,$j$ 是组内编号。 求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
状态表示: $f[i][j]$ 表示前 $i$ 个组,体积不超过 $j$ 的选取所有方案最大价值
状态计算: $f[i][j] = max(f[i - 1][j], f[i - 1][j - v_{ik} + w_{ik}])$
for(int i = 1; i <= n; i++) // 枚举 物品组
for(int j = m; j >= 0; j--) // 枚举 体积
for(int k = 0; k < s[i]; k++) // 枚举 组内分配方案
if(v[i][k] <= j) // 如果可以放入背包
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
状态机模型DP
- 建立状态机模型,多开一维表示状态,可以状态之间互相转移
状态压缩 DP
棋盘模型
要点
+ 放置合法问题,考虑从行的角度出发,当前行能不能放和上一行的放置状态有关,二进制压缩结合位运算即可破题
示例:炮兵阵地
#define pb push_back
const int N = 110, M = 1 << 10;
int n, m, cnt[M], g[N], f[2][M][M];
vector<int> state;
// 以放置在哪一行为决策阶段,空间不够,滚动数组优化,只用到了 i - 1 行状态,直接取 &
// 状态表示:f[i][j][k],表示当前在第 i 行,第 i 行状态为 j, 第 i - 1 行状态为 k 的放置数量最大值
// 状态计算:f[i & 1][b][a] = max(f[i & 1][b][a], f[(i - 1) & 1][a][c] + cnt[b]);
bool check(int x){
for(int i = 0; i < m; i++)
if( x >> i & 1 && (x >> (i + 1) & 1 || x >> (i + 2) & 1)) // 1 相邻的4个位置不能有1
return false;
return true;
}
int count(int x){
int res = 0;
for(int i = 0; i < m; i++)
if(x >> i & 1) res++;
return res;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 0; j < m; j++){
char c;
cin >> c;
if(c == 'H')
g[i] += 1 << j;
}
for(int i = 0; i < 1 << m; i++)
if(check(i)){
state.pb(i);
cnt[i] = count(i);
}
for(int i = 1; i <= n + 2; i++){
for(int j = 0; j < state.size(); j++)
for(int k = 0; k < state.size(); k++)
for(int u = 0; u < state.size(); u++){
int a = state[k], b = state[j], c = state[u]; // a:第i-1行,b:第i行,c:第i-2行
if(a & b | b & c | a & c) continue; // 三个状态不能进行转移
if(a & g[i - 1] | b & g[i]) continue; // 不能放置在山上
f[i & 1][b][a] = max(f[i & 1][b][a], f[(i - 1) & 1][a][c] + cnt[b]);
}
}
cout << f[(n + 2) & 1][0][0] << endl;
return 0;
}
二进制压缩思想
示例:Hamilton路径
给定一张完全图,求从0到n-1经过所有点的最短路径
const int N = 20, M = 1 << 20;
int f[M][N], w[N][N];
int n;
int hamilton(){
memset(f, 0x3f, sizeof f);
f[1][0] = 0; // f[i][j] 状态为i, 停留在j点最短路径
for(int i = 1; i < 1 << n; i++) // 枚举所有状态
for(int j = 0; j < n; j++) // 枚举状态中停留在哪个点
if(i >> j & 1) // 有这个点
for(int k = 0; k < n; k++) // 枚举从哪个点移动到 j
if((i ^ 1 << j) >> k & 1) // 有 k 这个点存在
f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + w[k][j]); // 状态转移
return f[(1 << n) - 1][n - 1]; // 经过了所有点,最后停留在 n - 1 这个点
}
int main(){
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> w[i][j];
cout << hamilton() << endl;
return 0;
}
集合模型
待补充
区间DP
要点
+ 以区间长度为决策阶段
一维区间DP
一些技巧
+ 环形区间,可以复制区间在后面,破环成链
例题:环形石子合并
const int N = 410, INF = 0x3f3f3f3f;
int w[N], n, s[N];
int f[N][N], g[N][N];
// 两条相同的链模拟环
// 状态表示: f[l][r] 表示从区间 l 到 区间 r 的最小合并费用
// 状态转移: f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> w[i];
w[i + n] = w[i];
}
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for(int i = 1; i <= 2 * n; i++)
s[i] = s[i - 1] + w[i];
for(int len = 1; len <= n; len++)
for(int l = 1; l + len - 1 <= 2 * n; l++){
int r = l + len - 1;
if(r > 2 * n) break;
if(len == 1) f[l][r] = g[l][r] = 0;
else
for(int k = l; k <= r; k++){
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
int max_ = -INF, min_ = INF;
for(int i = 1; i <= n; i++){
max_ = max(max_, g[i][i + n - 1]); // 长度为n的区间,端点差为len - 1
min_ = min(min_, f[i][i + n - 1]);
}
cout << min_ << endl << max_;
return 0;
}
二维区间DP
例题:棋盘分割
#include<iomanip>
const int N = 9, M = 16;
double f[N][N][N][N][M], X;
int n, g[N][N], s[N][N];
// 二维区间DP
// 状态表示:f[x1][y1][x2][y2][k], 表示在左上顶点为(x1, y1), 右下顶点为(x2, y2) 的矩形内分割 k 个矩形的最小方差
// 状态计算:循环切割的分割线(水平与竖直和继续往哪个部分切)
int get_sum(int x1, int y1, int x2, int y2){
return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
double get(int x1, int y1, int x2, int y2){
double sum = get_sum(x1, y1, x2, y2) - X;
return sum * sum / n;
}
double dp(int x1, int y1, int x2, int y2, int k){
double& v = f[x1][y1][x2][y2][k];
if(v >= 0) return v;
if(k == 1) return get(x1, y1, x2, y2);
v = 1e9;
for(int i = x1; i < x2; i++){
v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));
v = min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
}
for(int i = y1; i < y2; i++){
v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i));
}
return v;
}
int main(){
cin >> n;
for(int i = 1; i <= 8; i++)
for(int j = 1; j <= 8; j++){
cin >> g[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j];
}
memset(f, -1, sizeof f);
X = s[8][8] * 1.0 / n;
cout << fixed << setprecision(3) << sqrt(dp(1, 1, 8, 8, n)) << endl;
return 0;
}
树形DP
要点
+ 以一个点来表示一个集合
树形DP求树的直径
const int N = 1e4 + 10, M = 2 * N;
int n, idx, e[M], ne[M], h[N], w[M], ans;
// 状态表示:一个点表示以该点为最高点的所有路径最大长度
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u, int fa){ // 带入父节点编号,确保是从上到下搜索
int d1 = 0, d2 = 0; // 最大、次大到叶子节点的路径
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue;
int d = dfs(j, u) + w[i];
if(d >= d1) d2 = d1, d1 = d;
else if(d > d2) d2 = d;
}
ans = max(ans, d1 + d2);
return d1; // 返回最长的到叶子节点的路径
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
cout << ans << endl;
return 0;
}
换根DP
要点
+ 思考父节点更新子节点还是子节点更新父节点信息
换根DP求树的中心
- 树的中心:点到树中其他结点的最远距离最近
const int N = 1e4 + 10, M = 2 * N, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int n, d1[N], d2[N], up[N], p1[N], p2[N];
// 求得每个节点向上或者向下(所有方向)到边缘的长度,枚举所有点的全部路径,可以找到树的中心
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dfs_up(int u, int fa){ // 从上向下搜索,由子节点信息回溯更新父节点信息
d1[u] = d2[u] = -INF;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue;
int d = dfs_up(j, u) + w[i];
if(d >= d1[u]){
d2[u] = d1[u], d1[u] = d;
p2[u] = p1[u], p1[u] = j;
}
else if(d > d2[u])
d2[u] = d, p2[u] = j;
}
if(d1[u] == -INF) d1[u] = d2[u] = 0;
return d1[u];
}
void dfs_down(int u, int fa){ // 依然从上向下搜索, 不过是由父节点信息更新子节点信息
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue;
if(p1[u] == j) up[j] = w[i] + max(up[u], d2[u]); // 父节点向下最长路径经过该点,由次长路径更新
else up[j] = w[i] + max(up[u], d1[u]); // 否则由最长路径更新
dfs_down(j, u);
}
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i ++){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs_up(1, -1);
dfs_down(1, -1);
int res = INF;
for(int i = 1; i <= n; i++) res = min(res, max(d1[i], up[i]));
cout << res << endl;
return 0;
}
数位DP
要点
+ 以树的形式(思考数位)的形式思考数位DP问题
+ 查询 $[l, r]$ 中有多少个数合法,可用前缀和思想 dp(r) - dp(l - 1)
,dp(x)
求出 $[1,x]$ 中合法的数
状态表示
+ $f[i][j]$ 表示最高位为 $j$ ,有 $i$ 位的方案数
+ $f[i][j][k]$,表示有 $i$ 位,最高位为 $j$,所有位数之和 $\% p$ 的结果是 $k$ 的数字个数
+ $f[i][j][a][b]$, 有 $i$ 位,最高位为$j$,数位和 $\%7=a$ ,数值 $\%7=b$,合法方案个数
循环迭代
例题:度的数量
- 求有多少个数满足有 $k$ 个 $B$ 进制下的 $1$
int K, B, l, r;
int C[N][N];
// 以树的形式(思考数位)的形式思考数位DP问题
void init(){
for(int i = 0; i < N; i++)
for(int j = 0; j <= i; j++)
if(!j) C[i][j] = 1;
else C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
int dp(int n){
if(!n) return 0; // 第一步:判断边界
vector<int> v;
while(n){ // 第二步:数位转换
v.push_back(n % B);
n /= B;
}
int res = 0, last = 0; // 第三部:定义答案res和取了多少B进制下的1的个数last
for(int i = v.size() - 1; i >= 0; i--){ // 从高到低枚举每一位
int x = v[i];
if(x){ // x 为 0 没有讨论的价值,要继续下一位讨论
res += C[i][K - last]; // x > 0,这一位可以取0,后面可以取 K-last 个1
if(x > 1){ // x > 1, 这一位还可以取1,后面 i 位可以取 K-last-1 个 1
if(K - last - 1 >= 0) res += C[i][K - last - 1];
break; // 因为右边分支大于1,因为题目要求只能有0或1,所以右边不合法不继续讨论了
}
else{ // x = 1, 要记录last++,表示必须得取1了
last++;
if(last > K) break;
}
}
if(!i && last == K) // 取到了最后,数位上有last个1可以取,特殊情况res++
res++;
}
return res;
}
int main(){
cin >> l >> r >> K >> B;
init();
cout << dp(r) - dp(l - 1) << endl;
return 0;
}
记忆化搜索
单调队列优化DP
- 单调队列只能保存已经经过的点的信息
例题:烽火传递
using namespace std;
const int N = 2e5 + 10;
int f[N], w[N], n, m, q[N];
// 状态表示: f[i] 表示前i - 1个烽火已传递,并点燃第 i 烽火的最小代价(这样定义可以具有无后效性)
// 状态计算:f[i] = min(f[j]) + w[i] (i - m <= j < i - 1),用单调队列优化
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> w[i];
int hh = 0, tt = 0;
for(int i = 1; i <= n; i++){
if(hh <= tt && q[hh] < i - m) hh++;
f[i] = f[q[hh]]+ w[i];
while(hh <= tt && f[q[tt]] >= f[i]) tt--;
q[++tt] = i;
}
while(hh <= tt && q[hh] < n - m + 1) hh++; // 小技巧,队列后移一位的答案就是 min(f[n - m + 1, n])
cout << f[q[hh]] << endl;
return 0;
}
二维滑动窗口
输出仅一个整数,为 $a×b$ 矩阵中所有 ” $n×n$ 正方形区域中的最大整数和最小整数的差值”的最小值。
例题:理想的正方形
const int N = 1010;
int w[N][N], row_min[N][N], row_max[N][N], q[N], n, k, m;
// 思路:讨论最小值,最大值同理,先对每一行做单调队列记录每个点为长度为k窗口右端点,记录窗口最小值
// 对行的记录结果在列上做单调队列,对于k 行k 列之后的所有点上的数,就是 k * k 的矩阵内的最值
// 获取一个滑动窗口最小值,b[] 存取结果
void get_min(int a[], int b[], int len){
int hh = 0, tt = 0;
for(int i = 1; i <= len; i++){
if(hh <= tt && q[hh] <= i - k) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
b[i] = a[q[hh]];
}
}
// 获取一个滑动窗口最大值,b[] 存取结果
void get_max(int a[], int b[], int len){
int hh = 0, tt = 0;
for(int i = 1; i <= len; i++){
if(hh <= tt && q[hh] <= i - k) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
b[i] = a[q[hh]];
}
}
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> w[i][j];
for(int i = 1; i <= n; i++){
get_min(w[i], row_min[i], m);
get_max(w[i], row_max[i], m);
}
int a[N], b[N], c[N], res = 1e9 + 10;
for(int i = k; i <= m; i++){
for(int j = 1; j <= n; j++) a[j] = row_min[j][i];
get_min(a, b, n);
for(int j = 1; j <= n; j++) a[j] = row_max[j][i];
get_max(a, c, n);
for(int j = k; j <= n; j++)
res = min(res, c[j] - b[j]);
}
cout << res << endl;
return 0;
}
斜率优化DP
- 斜率优化普遍需要二分/CDQ/平衡树优化
基础凸包优化
例题:任务安排
有 $n$ 个 任务排成一个序列,顺序不得改变,其中第 $i$ 个 任务的耗时为 $T_i$, 费用系数为 $C_i$
现需要把该 $n$ 个 任务分成若干批进行加工处理
每批次的段头,需要额外消耗 $S$ 的时间启动机器。每一个任务的完成时间是所在批次的结束时间。
完成一个任务的费用为:从 $0$ 时刻 到该任务 所在批次结束的时刻 $t$ 乘以该任务费用系数 $C$
- 运用费用提前思想
const int N = 3e5 + 10;
ll f[N], q[N], t[N], c[N], n, s; // f[i] 表示执行到任务i的最小费用
// 1. 斜率 = t[i] + s 单调递增
// 2. 横坐标 c[i] 单调递增
// 3. f[i] 在截距上,找到截距最大的点,考虑凸包优化,找到第一个斜率大于 k 的点就是要找的答案,由于单调,采用单调队列优化到O(n)
int main(){
cin >> n >> s;
for(int i = 1; i <= n; i++){
cin >> t[i] >> c[i];
t[i] += t[i - 1], c[i] += c[i - 1];
}
int hh = 0, tt = 0;
q[0] = 0;
for(int i = 1; i <= n; i++){ // 队列hh、tt 带上 q[]
while(hh < tt && (f[q[hh + 1]] - f[q[hh]]) < (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh++;
int j = q[hh];
f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
while(hh < tt && (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]) < (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]])) tt--;
q[++tt] = i;
}
cout << f[n] << endl;
return 0;
}
IO
cin、cout解绑
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout精度控制
cout << fixed << setprecision(5) << 1.2 << endl;//输出结果为1.20000
Python3 多行输入
``python
while True:
try:
m = int(input().strip())
except EOFError:
break
md文件已经了哦,需要的同学可以上gitee下载,如果可以的话,麻烦点个 star
或者 fork
咯~
有同学想要份md文件,可以私信我~