算法笔记1.0

左神课程笔记

前置基本问题:

1. 归并分治算法

大范围的答案等不等于左边部分 + 右边部分 + 跨越左右两边的答案

💡考虑跨左右有序是否能提升便捷性。

归并排序:

💡归并排序是一个稳定的排序。

分成左右，merge排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int help[N];

void merge(int l,int r){
    int i = l, j = ((l + r) >> 1) + 1, t1 = 0;

    while(i <= ((l + r)>> 1) && j <= r){
          help[t1++] = (a[i] <= a[j]) ? a[i++] : a[j++];}
    while(i <= ((l + r)>> 1) ){. help[t1++] = a[i++];  }
    while(j <= r){. help[t1++] = a[j++];  }

    for(i = r; i >=l; i--){. a[i] = help[--t1];  }
}
void guibin(int l, int r,int n){
     if(l >= r) return ;

     guibin(l, (l + r) >> 1, n);
     guibin(((l + r) >> 1)+1, r, n);
     merge(l, r);
}

归并分治

💡

归并分治是基于归并排序，在归并排序的基础上进行分 左右 + 左右中的过渡，主要是分析左右中的过渡过程是否跟左右部分的有序性相关。

2. 随机快速排序

基本内容与快速排序保持一致，只是在选择pivot的时候是随机选择。

💡

pivot的随机选择是从概率上讲快速排序的时间复杂度降低到O(nlogn)

快排的重要部分是 partition函数部分

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int nums[N];

int a,b;
void swap(int i, int j){
    int temp;
    temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void part(int l, int r, int x){
    int  i = l; // 小于区域 a 大于区域 b
    a = l, b = r;
    while(i <= b){
         if(nums[i] < x){
            swap(i++,a++);
         }else if(nums[i] > x){
            swap(i, b--);
         }else i++;
    }
}

void quick__sort(int l, int r){
    if(l >= r){
        return;
    }
    int pivot = nums[l];
    part(l, r, pivot);
    quick__sort(l,a-1);
    quick__sort(b+1,r);
}

可以用 partition 来寻找第k大第k小 (荷兰国旗问题)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int nums[N];

int a, b;

void swap(int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void partition(int l, int r, int x){
    int i = l;
    a = l, b = r;
    while(i <= b){
          if(nums[i] < x){
            swap(i++,a++);
          }else if(nums[i] > x){
            swap(i, b--);
          }else i++;
    }

}
int find(int k, int n){
    int ans = 0;
    for(int l = 0, r = n; l <= r;){
        partition(l, r, nums[l]);
        if(k < a){
            r = a -1;
        }else if(k > b){
            l = b + 1;
        }else{
            ans = nums[k];
            break;
        }
    }

    return ans;
}

构建前缀信息（46）

常见构建

构建前缀信息（最早最晚）出现的位置

前缀和来求区间和

sum[i] = sum[i-1] + a[i]
{l , r} → sum[r + 1] - sum[l] 2. 求区间累加和为确定值的最长长度（子数组个数）
记录 t = sum[i] - aim 的最早出现次数（i 之前的 t 的出现个数）3. 正数和负数相等的最长数组长度
正数相当于 1 负数相当于 -1 求区间为 0 1的子数组最长长度

区间大于 0 的最长数组长度（值只有 -1, 1）

aim = sum[i] - sum[j] ≥ 0
if sum[i] > 0 → ans = i
if sum[i] ≤ 0 → sum[i] -1 最早出现的位置

移除最短的数组子数组长度 sum 能被 p 整数

与余数相关
sum1 % p = a // sum2 % p = b
if(a + b % p == 0) (sum1 + sum2) % p == 0
整体 aim = sum(总) % p → 看哪个区间的的余数 (t + aim) % p == 0
find = (t + p - aim) % p (同余原理) → 与环也有关

💡

单调队列和单调栈一样，保存着对于答案的可能性，并且从栈中弹出的时候，进行计算，不进行后续的计算，一般应用于区间问题。

核心思想 : 越往后的满足要求更好的选择更好

单调队列

单调队列基本用法 → 用来维护一个窗口里面的最值（左闭右开）

💡 因为从左弹出的时候，这个队列无论如何是没有过期下标的（要不一开始被最值从右边顶出去了，要不越界被左边弹出去了）

deque<int> q;
    for (l = r = 0; r < n; r++)
    {
        while (!q.empty() && a[r] >= a[q.back()])
        {
            q.pop_back();
        }
        q.push_back(r);
        if (q.size() == limit + 1)
        {
            if (l++ == q.front())
            {
                q.pop_front();
            }
        }
    }

优先队列扩展

区间和小于定值的最短长度

 int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> sum(n + 1, 0);
    deque<int> q; // 小 -> 大
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i-1] + nums[i-1];
    }
    int ans = INT_MAX;
    q.push_back(0);
    for(int i = 1; i <= n; i++){
        while(!q.empty() && sum[i] - sum[q.front()] >= k){
            //cout << ans << " " << i - q.front() << endl;
            ans = min(ans,i - q.front());
            q.pop_front();
        }
        while(!q.empty() && sum[i] <= sum[q.back()]){
            q.pop_back();
        }
        q.push_back(i);
    }
    return ans == INT_MAX ? -1 : ans;
    }

双端队列吃药任务安排


    int n, s;
    cin >> n >>s;
    vector<int> a(n);
    vector<int> b(n);
    for(int i = 0; i < n; i++) cin >> a[i]; // 人的体力
    for(int i = 0; i < n; i++) cin >> b[i]; // 任务的需求
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans = 0; // 最少的药丸次数
    deque<int> q;
    /*
          先看每一个的力所能及 放入队列中
      */

    for(int i = 0, p = 0; i < n; i++){
        while(p < n && b[p] <= a[i]){
            q.push_back(b[p++]);
        }
        if(!q.empty() && a[i] >= q.front()){
           q.pop_front();
        }else {
            while(p < n && b[p] < a[i] + s){
                q.push_back(b[p++]);
            }
            if(q.empty()){
                cout << "can't do it" << endl;
                return 0;
            }else{
                ans++;
                q.pop_back(); // 吃药取最大
            }
        }
    }
    cout << ans << endl;
    return 0;

单调栈

基本使用方法维护 左右侧 比当前元素 大或者小 的最近位置

💡

构建一个栈 → 越后出现的值有更大的影响力

找出以某个值为最值的子数组（最长或者对这个子数组进行一些计算）

同时间维护左右的最近的最值

    stack<int> s; // 记录下标
    for(int i = 0; i < n; i++){
        while(!s.empty() && a[s.top()] >= a[i]){
            // i 为右边
            int cur = s.top(); s.pop(); // 中间
            int l = s.empty() ? -1 : s.top(); // 左边
        }
        s.push(i);
    }
    while(!s.empty()){
        int cur = s.top(); s.pop();
        int l = s.empty() ? -1 : s.top();
        ans += (cur - l) * (n - cur) * a[cur];
    }

创新 :

求 子数组中的最小值的和

💡

用单调栈 → 求出左右两边小于(大于) 这个值的位置 → 在这个中间 i位置的值便是最值

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    // 在子数组中 cur 位置为最小 i 为 右边
    stack<int> s; // 记录下标
    long long ans = 0;
    for(int i = 0; i < n; i++){
        while(!s.empty() && a[s.top()] >= a[i]){
            int cur = s.top(); s.pop(); // 中间
            int l = s.empty() ? -1 : s.top(); // 左边
            ans += (cur - l) * (i - cur) * a[cur];
        }
        s.push(i);
    }
    while(!s.empty()){
        int cur = s.top(); s.pop();
        int l = s.empty() ? -1 : s.top();
        ans += (cur - l) * (n - cur) * a[cur];
    }
    return 0;
}

实现最小字典序（单调栈）

💡

利用单调栈来维护一个从小到大的 stack

   for(int i = 0; i < a.size(); i++){
        in[a[i] - 'a']++;
    }

    stack<pair<char,int>> s;
    vector<bool> vis(26,false);

    for(int i = 0; i < a.size(); i++){
    if(!vis[a[i] - 'a']){
    while(!s.empty() && s.top().first > a[i] && in[s.top().first - 'a'] >= 1){
            vis[s.top().first- 'a'] = false;
            s.pop();
        }
    vis[a[i] - 'a'] = true;
    s.push({a[i], i});
    }
    in[a[i] - 'a']--;
    }
    string ans = "";

    while(!s.empty()){
        ans = s.top().first + ans;
        s.pop();
    }

滑动窗口 + 双指针（视频）

数据结构

前缀树（字典树）

💡

前缀树有点像链式前向星，是一个用静态数组来连接。

重点部分

cnt:用序号表示连接，如果这个节点没有使用过，他把这个节点用cnt来编号，然后cur会使用它来跳转，会到达一个没有去过的层次。

int cnt = 1; // 层次编号
// 插入单词
void insert(const string& word) {
    int cur = 1;
    pass[cur]++;
    for (char ch : word) {
        int path = ch - 'a';
        if (tree[cur][path] == 0) {
            tree[cur][path] = ++cnt;
        }
         cur = tree[cur][path];
        pass[cur]++;
    }
    end[cur]++;
}
// 查询前缀的数量
int prefixNumber(const string& prefix) {
    int cur = 1;
    for (char ch : prefix) {
        int path = ch - 'a';
        if (tree[cur][path] == 0) {
            return 0;
        }
        cur = tree[cur][path];
    }
    return pass[cur];
}
// 删除单词
void deleteWord(const string& word) {
    if (prefixNumber(word) > 0) {
        int cur = 1;
        for (char ch : word) {
            int path = ch - 'a';
            if (--pass[tree[cur][path]] == 0) {
                tree[cur][path] = 0;
                return;
            }
            cur = tree[cur][path];
        }
        end[cur]--;
    }
}
// 清空前缀树
void clear() {
    memset(tree, 0, sizeof(tree));
    memset(pass, 0, sizeof(pass));
    memset(end, 0, sizeof(end));
    cnt = 1;
}

以下是关于字典树 + 二进制运算:

const int N = 1e3+10;
const int M = 2;

int pass[N];
int End[N];
int tree[N][M];
int cnt = 1;

void insert(int s){
     int cur = 1;
     for(int i = 63; i >= 0; i--){
         int temp = ((1 << i) & s) >>i;
         //cout << temp << endl;
        if(tree[cur][temp] == 0){
            tree[cur][temp] = ++cnt;
        }
        cur = tree[cur][temp];
     }
     // 我如何取到这个二进制上面的值
}

int exam(int t){
    int cur = 1;
    int Max = 0;
    for(int i = 63; i >= 0; i--){
        int temp = (t >> i) & 1;
        // 最好 temp ^ aim == 1 aim == 1 ^ temp
        int aim = 1 ^ temp;
        if(tree[cur][aim] == 0){
           aim ^= 1;
        }
        Max |= ((temp ^ aim) << i);
        cur = tree[cur][aim];
    }
    return Max;
}

单调栈 + 单调队列

stack st 便是单调栈的形式，只是栈中的元素是单调的。

priority_queue q 便是单调队列（优先队列）的形式，在优先队列中的元素是单调的。

并查集（模版）

const int N = 1e5 + 10;
int father[N];
// 初始化并查集
void build(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}
// 查找元素的根，并进行路径压缩
int find(int i) {
    if (i != father[i]) {
        father[i] = find(father[i]);
    }
    return father[i];
}
// 判断两个元素是否属于同一个集合
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}
// 合并两个集合
void unite(int x, int y) {
    father[find(x)] = find(y);
}

基本建图方法

vector 数组建图

vector<pair<int,int>>a[10005];

链式前向星

💡 **初始的 cnt 是没有使用过的然后将这个 cnt 对应 v节点 next 表示下一条边的编号 head[u] 节点的头部边的编号** ---

u -> new -> old 一开始的 head[u] -> old 现在将 head[u] -> new 将 new 的 next -> old

const int N = 1e5+10;

int cnt = 0;
int head[N];
struct{
    int to, next, w;
}edge[N];

void init(){
    for(int i = 0; i < N; i++){
        head[i] = -1;
        edge[i].next = -1;
    }
    cnt = 1;
}

void add(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
// 遍历方法
void ex(){
    int u ;
    for(int e = head[u]; e > 0; e = edge[e].next){
        int v = edge[e].to;
     }
}

拓扑排序

💡 所谓的拓扑排序，其实是图论里面的一个常见手段，常用于有前后关系的节点状态问题。

常从 入度为0 的节点开始访问**。（与 priority_queue 小根堆结合应用）**

如果无法把所有的点都删掉，说明有向图里有环

const int N = 1e5+10;
int queue[N]; // 可以用 STL 代替 （queue）
int indegree[N];

拓扑排序扩展知识（类似树型dp）

💡

将上游节点的信息 → 推送到下游节点

倍增算法 + ST表（用于区间查询最值，gcd）(先看基础dp )

💡

原理:每一个数字都能用二进数来表示 // 尽量逼进目标值

应用: 可重复贡献问题

前提:后面的点跳的距离会大于等于前面的点

跳跃公式:ST[ i ][ p ] = ST[ ST[ i ][ p-1 ] ][ p-1] p → 跳 2 的 p 次方

从 大 → 小 尝试

仅需初始化 ST[ i ][ 0 ] ，其余可以用跳跃公式解决 // 从列开始填

💡

 ST[i][p] = max(ST[i][p-1], ST[i + 2 ^ p-1][p-1])
 ST[i][p] = min(ST[i][p-1], ST[i + 2 ^ p-1][p-1])
 ST[i][p] = gcd(ST[i][p-1], ST[i + 2 ^ p-1][p-1])

 (i , j) -> max(ST[i][p], ST[j - 2 ^ p + 1][p])
         // p == log2(i - j + 1)

Max，Min的基本代码


const int N = 1e3 + 10;
int Log2[N];
int stmax[N][N];
int stmin[N][N];
int num[N];
void bulid(int n){
    Log2[0] = -1;
    for(int i = 1; i <= n; i++){
        Log2[i] = Log2[i >> 1] + 1;
        stmax[i][0] = num[i];
        stmin[i][0] = num[i];
    }

    for(int p = 1; p <= Log2[n]; p ++){
        for(int i = 1; i <= n; i++){
            stmax[i][p] = max(stmax[i][p-1],stmax[i + (1 << (p-1))][ p-1 ]);
            stmin[i][p] = min(stmin[i][p-1],stmin[i + (1 << p-1)][p-1]);
        }
    }
}

扩展的可重复贡献区间问题:

区间与区间或 (两个相同的数字与或不会影响结果)

树上问题

树上倍增 + LCA

tarjian算法

💡

批量离线查询

如果访问的 ans -> u 的对应节点v 访问过 ans = v 的代表节点

理解:

      因为 你到这个节点的时候，对应的节点访问过了的话，那些节点是在一个集合里面的，然后 节点遍历是 属于 DFS，所以都是 分支访问，访问完这个 分支， 节点进行汇总集合。

void tarjan(int u, int f){
    vis[u] = true;
    for(int e = head[u]; e != 0; e = ed[e].next){
        int v = ed[e].to;
        if(v != f){
            tarjan(v, u);
            father[v] = u;
        }
    }

    for(int e = q_head[u]; e != 0; e = que[e].next){
        int v = que[e].to;
        if(vis[v]){
            ans[que[e].w] = find(v);
        }
    }
}

ST表

💡

当 Deep 深度数组到达同一层的时候所对应的节点是否相同

相同 : LCA = Deep 小的

不相同:

再次同时间跳（only 不跳到同一节点我们才跳）

ST表实现的问题 : 加快 Deep数组的跳跃过程


int LCA(int u, int v){
    /*
        u在下面
     */
    if(Deep[u] < Deep[v]){
        int t = u;
        u = v;
        v = t;
    }
    for(int i = power; i >= 0; i--){
        if(Deep[ST[u][i]] >= Deep[v]){
            u = ST[u][i];
        }
    }

    if(u == v){
        return v;
    }

    for(int i = power; i >= 0; i--){
        if(ST[u][i] != ST[v][i]){
            u = ST[u][i];
            v = ST[v][i];
        }
    }
    return ST[v][0];

}

树的重心（有一个或者两个）

树的重心的基本定义:

最大子树的节点数足够小
每棵子树的节点数不超过总节点数的一半
所有节点汇聚到重心的步数最少

补充性质:

一棵树最多有两个重心，两个重心一定相邻
如果树上增加或者删除一个叶节点，重心最多移动一条边
将两棵树连起来，新树的重心一定在两个原来重心的连线上
如果边权为正，所有节点走向重心的总距离和最小

求法一 : 最大子树足够小

int ans = 0, best = INT_MAX;
/*
  重心:
   以当前节点为 重心，所有子树中 最大数量的子树的 数量足够小
*/
int dfs(int u, int f){
    Size[u] = 1;
    int mx = 0;
    for(int v = head[u]; v != 0; v = edge[v].next){
        int e = edge[v].to;
        if(e != f){
            dfs(e,u);
            Size[u] += Size[e];
            mx = max(mx, Size[e]);
        }
    }
    mx = max(mx, n - Size[u]);
    if(mx < best || (mx  == best && u < ans)){
        ans = u;
        mx = best;
    }

}

求法二 :每棵子树的节点数不超过总节点的一半

int Size[N];
vector<int> ans;
void dfs(int u, int f){
    Size[u] = 1;
    int Mx = 0;
    for(int e = head[u]; e != 0; e =edge[e].next){
        int v = edge[e].to;
        if(v != f){
            dfs(v,u);
            Size[u] += Size[v];
            Mx = max(Size[v], Mx);
        }
    }
    Mx = max(Mx, n - Size[u]);
    if(Mx <= n / 2){
        ans.push_back(u);
    }
}

扩展: 带点权的树如何求重心

仅修改一个 → Size[u] 的初始值变成了点权重 56分以上

💡

首先:重心是与边权没有关系的，所谓的点权，可以理解为一个独立的树，树中的节点数量就是点的权重

int Size[N];
int a[N];
vector<int> ans;
int sum; // sum 是总点权和
void dfs(int u, int f){
    Size[u] = a[u];
    int Mx = 0;
    for(int e = head[u]; e != 0; e =edge[e].next){
        int v = edge[e].to;
        if(v != f){
            dfs(v,u);
            Size[u] += Size[v];
            Mx = max(Size[v], Mx);
        }
    }
    Mx = max(Mx, sum - Size[u]);
    if(Mx <= sum / 2){
        ans.push_back(u);
    }
}

树的直径

树上的最长路径

两次 DFS（仅使用没有负边权）

💡能得到路径信息 1. 从根节点找离根节点最远的点 2. 在从这个节点找离这个节点最远的点

/*
  法一: 两次dfs
  优点:能得到路径信息
*/
int start, End;

int di[N]; // 记录从规定节点到 当前节点到距离
int la[N]; // 记录路径

void dfs(int u, int f, int w){
      la[u] = f;
      di[u] = di[f] + w;
      for(int e = head[u]; e != 0; e = ed[e].next){
        int v = ed[e].to;
        if(v != f){
            dfs(v, u, ed[e].w);
        }
      }
}
pair<int,int> find_road(int n){
    dfs(1, 0, 0);
    start = 1;
    for(int i = 1; i <= n; i++){
        if(di[i] > di[start]){
            start = i;
        }
    }
    dfs(start, 0, 0);
    End = 1;
    for(int i = 1; i <= n; i++){
        if(di[i] > di[End]){
           End = i;
        }
    }
    return {start, End};
}

树型dp

💡

只能得到直径长度

int Max_dia = INT_MIN;
void dp(int u, int f){
    for(int e = head[u];  e != 0; e = ed[e].next){
        int v = ed[e].to;
        if(v != f){
            dp(v, u);
            Max_dia = max(Max_dia, dist[u] + dist[v] + ed[e].w);
            dist[u] = max(dist[u], dist[v] + ed[e].w);
        }
    }
}

树上差分

点差分

💡

1.计算公式 （子节点的变化会向上传递)

(x → y) + v

x += v

y += v

LCA -= v

LCA_father -= v

2.合并

num[i] += num[所有孩子]

边差分

💡

计算公式点权变化:

   (x → y) + v

    x += v

    y += v

    LCA -=  2*v

更新权重

num[ i → j 边] += weight[ j ]（点权）

weight[ i ] += weight[ 所有子节点 ]

树状数组（视频）

树状数组是处理区间查询的方法。

一般处理 可差分信息（总体是由部分构成的）| 下标一定从 1 开始
怎么得到最右边的 1 → i & -i

常见有以下四种查询类型

单点增加 + 范围查询

管理范围 (去除最右边的 1（ lowbit(i) ） + 1，自己)

💡

输入的时候 tree数组用add 方法进行添加

int tree[N];
// 单点增加  区间查询
int n; //数组长度
int lowbit(int i){
    // 取最右边的 1
    return i & -i;
}
void add(int i, int w){
     // 下标 + 最右边的 1 的地方 + w
     while(i <= n){
        tree[i] += w;
        i += lowbit(i);
     }
}
// 1 -- r 的范围和
int sum(int r){
    // sum = tree[x] 自己 然后不断去除最右边的 1
    int ans = 0;
    while(r > 0){
        ans += tree[r];
        r -= lowbit(r);
    }
    return ans;
}

范围增加 + 单点查询（改成差分数组）

💡

原数组 a[i] = sum(delat[1] + …+ delat[i])

delat[i] = a[i] - a[i - 1]

差分数组可以实现原数组的区间增减

delat[l] + w, delat[r + 1] - w.

构建 tree数组的时候, add_sum( i , w);

int tree[N];
// 单点增加  区间查询
int n; //数组长度
int lowbit(int i){
    // 取最右边的 1
    return i & -i;
}
void add(int i, int w){
     // 下标 + 最右边的 1 的地方 + w
     while(i <= n){
        tree[i] += w;
        i += lowbit(i);
     }
}
// 查询 r 位置的值
int sum(int r){
    // sum = tree[x] 自己 然后不断去除最右边的 1
    int ans = 0;
    while(r > 0){
        ans += tree[r];
        r -= lowbit(r);
    }
    return ans;
}
// 增加 l -> r 的值
void add_sum(int l, int r)
{
  add(l, w),add(r + 1, -w);
}

范围增加 + 范围查询

💡

sum(1 → r)

= r _ Sum( delat[1 → r] ) - sum(1 → r)[(i - 1) _ delat[i] ]\

维护两个差分数组 Di + （i - 1) * Di


const int N = 1e5 + 10;
// Di
int tree1[N];
// (i - 1) * Di
int tree2[N];

int n;
int lowbit(int i){
    return i & -i;
}
void add(int i, int w){
    int t = i;
    while(t <= n){
        tree1[t] += w;
        t += lowbit(t);
    }
    t = i;
    int W = (i - 1) * w;
    while(t <= n){
        tree2[t] += W;
        t += lowbit(t);
    }
}
void Add(int l, int r, int w){
    add(l, w); add(r + 1, -w);
}
// 1 -> i 的和
int sum(int i){
    int ans = 0, t = i;
    while(t > 0){
        ans += (tree1[t] * i);
        ans -= tree2[t];
        t = t - lowbit(t);
    }
    return ans;
}

二维的单点增加 + 范围查询

要从 1 1开始

const int N = 1e3 + 10;
const int M = 1e3 + 10;
int tree[N][M];

int n, m;
int lowbit(int i){
    return i & -i;
}
void add(int x, int y, int w){
    for(int i = x; i += lowbit(i); i <= n){
       for(int j = y; j += lowbit(j); j <= m){
        tree[i][j] += w;
       }
    }
}
// 1 -> x 1 -> y
int sum(int x, int y){
     int ans = 0;
     for(int i = x; i > 0; i -= lowbit(i)){
        for(int j = y; j > 0; j-= lowbit(j)){
            ans += tree[i][j];
        }
     }
     return ans;
}

二维数组的范围增加 + 范围查询

逆序队问题

线段树

基本线段树

动态规划（先做题目）

背包dp （66 - 75）

区间dp

将大范围划分为若干个小范围的问题

💡

可能性展开:

基于 两侧端点 讨论

基于 范围划分 讨论

状态dp

利用二进制的 0 1 来表示节点状态

树型dp

将子树的信息返回给父亲

数位dp

判断 数字的可能性

💡

大部分都是从左向右进行尝试（线性展开）

换根dp

将根节点互换，要求值的变化

轮廓线dp

三进制状压dp

dp优化

字符串

KMP

前缀函数

💡

NEXT 函数构建

 前后缀 匹配长度

int Next[N];
void get_next(string s){
    Next[0] = -1;
    Next[1] = 0;
    int i = 2, cn = 0;
    // Next[i] 表示的是 1 - i-1 的最长前后缀匹配长度
    while(i < s.size()){
        if(s[i - 1] == s[cn]){
            Next[i++] = ++cn;
        }else if(cn > 0){
            cn = Next[cn];
        }else{
            Next[i++] = 0;
        }
    }
}

💡

KMP 是依靠这个前缀函数来实现的

如果当前的字符不匹配

需要检测的字符，根据 NEXT 数组向前跳转

扩展 KMP （Z数组）前缀匹配问题

动态图展示 🔗:https://personal.utdallas.edu/~besp/demo/John2010/z-algorithm.htm ↗

💡

Z[i] 表示 s[0 - n-1] 和 s[i - n-1] 的最长匹配长度

线性加速过程:

   如果在最右的最长前缀匹配区间中，会加速前缀加速匹配过程


const int N = 2e6 + 10;
int z[N];
void Z(string s){
     z[0] = 0;
     int n = s.size();
     for(int i = 0, r = 0, l = 0; i < n;i++){
         if(i <= r && z[i - l] < r - i + 1){
            z[i] = z[i - l];
         }else{
            z[i] = max(0, r - i + 1);
            while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
            if(i + z[i] - 1 > r){
                r = i + z[i] - 1;
                l = i;
            }
     }
     }
}

Manacher

💡

P[i] 数组是保留了更新的数组的回文串长度

# a # a # a # 总长度为 2 * n + 1

1 2 3 4 3 2 1

const int N = 3e7;
int p[N];
int Max = 0;
string c(string s){
    string s1 = "#";
    for(auto x : s){
       s1 += x;
       s1 += '#';
    }
    return s1;
}
void manacher(string s){
     int n = s.length();
     int c = 0, r = 0;
     for(int i = 0, len; i < n; i++){
        len = r > i ? min(p[2 * c - i], r - i) : 1; // 至少的回文半径区域
        while(i  + len < n && i - len >= 0 && s[i + len] == s[i - len] ){
            len ++;
        }
        if(i + len > r){
            c = i;
            r = i + len;
        }
        Max = max(Max, len);
         p[i] = len;
     }
}

AC自动机

字符串哈希

数学

埃式筛

💡

如果这个元素没有访问过，便是质数，并且 这个质数的所有倍数的值就不是质数

void ehrlich(int n){
    vector<bool> vis(n + 1, false);
    for(int i = 2; i * i <= n; i++){
        if(!vis[i]){
            for(int j = i * i; j <= n; j +=i){
                vis[j] = true;
            }
        }
    }

    int cnt = 0; // 质数 记数 vis 未访问过的 便是质数字
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            cnt ++;
            cout << i << " ";
        }
    }cout << endl;
    }

乘法逆元

逆元含义:

x\rightarrow \frac{1}{x}

法一 :扩展欧几里得求逆元

typedef long long LL;
LL ExGCD(LL a, LL mod, LL &x, LL &y){
    if(mod == 0){
        x = 1; y = 0;
        return a;
    }
    LL d = ExGCD(mod, a % mod, x, y), t = x;
    x = y; y = t - a / mod * x;
    return d;
}
int ExGcdInv(int a, int mod){
    LL x, y;
    ExGCD(a, mod, x, y);
    return (x + mod) % mod;
}

法二 : 快速幂求逆元

LL fastpow(int a, int b, int mod){
    LL ret = 1;
    while(b){
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
LL FermatInv(int a, int mod){
    return fastpow(a, mod - 2, mod);
}

法三 : 费马小递推求逆元

\text{inv}[i] = ( \text{mod} - (\text{mod} \div i) ) \times \text{inv}[\text{mod} \% i] \% \text{mod}

int invList[mod+ 10];
voidGetInv(int mod)
{
    invList[1]= 1;
for(int i= 2; i< mod; i++)
        invList[i]= 1LL* (mod- mod/ i)* invList[mod% i]% mod;
}

容斥原理

奇 ➕ 偶 ➖ 两个集合:

|A \cup B| = |A| + |B| - |A \cap B|

三个集合:

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

n个集合:

\quad \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right|

快速幂

基本快速幂

typedef long long LL;
const int mod = 1e9 + 7;
LL fastpow(int a, int b){
    LL ant = 1;
    while(b){
        if(b & 1){
            ant = ant * a %mod;
        }
        a = a * a %mod;
        b >>= 1;
    }
    return ant % mod;
}

矩阵快速幂

💡

矩阵快速幂常用于 DP（固定线性递归）问题

一维 k阶（k 个式子） 时间复杂度 :O(logn * 2^k)

f(n) = c_1 f(n-1) + c_2 f(n-2) + … + c_k f(n-k)

k维一阶

\mathbf{X}n = A \mathbf{X}{n-1}

💡

相当于第 i 位置的 ans 需要第 i-1 位置的 ans（可能是二维的，以为着需要 i-1 位置的多个答案）

矩阵快速幂的基本伪代码

vector<vector<int>> multiply(vector<vector<int>> a, vector<vector<int>> b){
    int n = a.size();
    int m = b[0].size();
    int k = a[0].size();
    vector<vector<int>> ans(n, vector<int>(m));
    // ans[i][j] == a的 第i行 * b的 第j列
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int temp = 0;
            for(int t = 0; t < k; t++){
                ans[i][j] +=a[i][t] * b[t][j];
            }

        }
    }
    return ans;
}

vector<vector<int>> power(vector<vector<int>> a, int t){
    int n = a.size();
    vector<vector<int>> ans(n, vector<int> (n, 0));
    for(int i = 0; i < n; i++) ans[i][i] = 1;
    while(t){
        if(t & 1) ans = multiply(ans, a);
        a = multiply(a, a);
        t >>= 1;
    }
    return ans;
}