Zaliasc's Blog
文章 标签 分类
Zaliasc's Blog

Contents

算法模板整理

   4370 words   9 minutes 

STL

vector    支持
    size()
    empty()
    clear()   清空
    front()/back()   数组头尾元素
    push_back()/pop_back
    begin()/end()   首尾元素
    支持字典序比较
    
pair
    first   第一个元素
    second   第二个元素


string
    size()/length   返回长度
    empty()
    clear()
    substr(a,b)  得到一个下标位a长度位b的子字符串
    substr(a)   得到一个下表为a长度取最长的子字符串
    c_str()   取string定义数组的首地址


queue
    size()
    empty()
    push()   在队尾插入一个元素
    front()/back()   返回队头/队尾元素
    pop()   弹出队头元素


priority_queue 优先队列(堆) 默认大根堆
    size()
    empty()
    push()
    top()
    pop()
    定义小根堆: priority_queue<int , vector<int> , greater<int>>


stack    
    size()
    empty()
    push()
    pop()
    top()


deque       支持[]
    size()
    empty()
    clear()
    front()/back()   头尾元素
    push_back()/push_front()   在头尾插入
    begin()/end()



set , map , multimap , multiset , 基于平衡二叉树 (红黑树) 维护一个有序数列 大部分函数时间复杂度都是logn (因为是树)
    size()
    empty()
    clear()
    begin()/end()  支持++ -- 时间复杂度 O(logn)
    lower_bound()/upper_bound()
    lower_bound(x)     返回一个大于等于x的最小值
    upper_bound(x)     返回一个大于x的最小值

set / multiset    set不支持重复数插入 插入重复数直接跳过
    insert()    插入一个数
    find()      查找一个数
    count()     返回一个数存入的个数
    erase()
        (1) 输入是一个x , 删除全部x , 时间复杂度 O(k + logn)
        (2) 输入是一个迭代器 , 删除这个迭代器

map / multimap
    insert()    插入的是一个pair
    erase()     输入的参数是pair 或者 迭代器
    find()
    支持[]

unordered_set , unordered_map , unordered_multiset , unordered_multimap
    基本跟上面一个一样 查找删改时间复杂度是 O(1)
    不支持lower_bound()/upper_bound()  迭代器的++ --



bitset   压位
    bitset<放大小> s;   初始化时候全为0  —— false;
    ~取反  &且  |或  ^异或
    == , !=
    移位 <<   >>
    支持[]
        
    count()     返回有多少个1

    any()       判断是否有1
    none()      判断是否全为0

    set()       把所有位置为1
    set(k,v)    将第k位变成v
    reset()     把所有位置为0
    flip()      等价于~
    flip(x)     第k位取反

基础算法

快速排序

const int N = 1e6 + 10;

int n;
int q[N];


void quick_sort(int *q,int l,int r) {
  if (l >= r) return;

  int x = q[l+r>>1], i = l-1, j = r + 1;
  while (i <j) {
    do i++; while (q[i] < x);
    do j--; while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
  }

  quick_sort(q, l, j);
  quick_sort(q, j+1 , r);

}

归并排序

const int N = 1e6 + 10;

int n;
int q[N], tmp[N];


void merge_sort(int q[],int l,int r) {
  if (l >= r) return;

  int mid = l + r >> 1;

  merge_sort(q, l, mid), merge_sort(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++];
  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];
}

二分

AcWing 789. 图解 y总的二分模板 （最容易理解版本 ) - AcWing

//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; 
        else l = mid + 1; 
    }   
    return l;
}
//查找右边界 SearchRight 简写SR 
int SR(int l, int r) 
{
    while (l < r)
    {                   
        int mid = l + r + 1 >> 1; //需要+1 防止死循环
        if (check(mid)) l = mid;
        else r = mid - 1; 
    }
    return r; 
}

704 35 34 69 367

STL

数据结构

单链表

#include<iostream>

using namespace std;

const int N = 100000;

int e[N], ne[N];

int head, idx;

void init() {
  head = -1;
  idx = 0;
}

void add_to_head(int x) {
  e[idx] = x, ne[idx] = head, head = idx++;
}

void add(int k, int x) {
  e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

void remove(int k) {
  ne[k] = ne[ne[k]];
}

int main() {
  int m;
  cin >>m;
  
  init();
  
  while(m--) {
    int k, x;
    
    char op;
    cin >> op;
    if (op == 'H') {
      cin >> x;
      add_to_head(x);
    }
    else if (op == 'D') {
      cin >> k;
      if(!k) head = ne[head];
      remove(k-1);
    }
    else {
      cin >> k >> x;
      add (k-1, x);
    }
    
    // cout << op << endl;
    }
    
    
    for (int i = head; i!= -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
    
    return 0;
}

双链表

const int N = 100000;

int e[N], ne[N];

int head, idx;

void init() {
  head = -1;
  idx = 0;
}

void add_to_head(int x) {
  e[idx] = x, ne[idx] = head, head = idx++;
}

void add(int k, int x) {
  e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

void remove(int k) {
  ne[k] = ne[ne[k]];
}

栈

单调栈

#include <iostream>

using namespace std;

const int N = 100010;

int n ;
int skt[N], tt;


int main () {
  cin >> n;
  for (int i = 0; i< n; i++) {
    int x;
    cin >> x;
    while (tt && skt[tt] >= x) tt--;
    if (tt) cout << skt[tt] << " ";
    else cout << -1 << " ";
  
    skt[++tt] = x;
  }
  
  return 0;
}

单调递增：小于，单调递减：大于

class Solution {
 public:
  int sumSubarrayMins(vector<int>& arr) {
    int n = arr.size();
    vector<int> left(n, -1), right(n, -1);

    stack<int> skt1;
    // ++
    for (int i = 0; i < n; ++ i) {
      while (!skt1.empty() && arr[skt1.top()] >= arr[i]) {
        right[skt1.top()] = i;
        skt1.pop();
        
      }
			left[i] =skt1.empty()? -1: skt1.top();
      skt1.push(i);
    }

    for (int i = 0; i < n; ++ i) {
      cout << left[i] << " ";
    }

    cout << endl;
    for (int i = 0; i < n; ++ i) {
      cout << right[i] << " ";
    }

    return 1;
  }
};

单调队列

优先队列

#include<bits/stdc++.h>

using namespace std;

// 自定义比较函数，需重载 () 运算符
struct cmp {
    bool operator() (pair<int, int> &a, pair<int, int> &b) {
        return a.first > b.first;   // 小根堆
    }
};

// 自定义数据结构，需重载 < 运算符
struct Info
{
    int h_;
    Info(int h) : h_(h) {}

    bool operator<(const Info& t) const // 不加const会报错！
    {
        return h_ > t.h_; // 小根堆
    }
};

int main() {
    // 默认大根堆, 第三个参数 less<int> 可以不加
    priority_queue<int, vector<int>, less<int>> q1;
    // 小根堆
    priority_queue<int, vector<int>, greater<int>> q2;
    // 自定义比较函数
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q3;
    // 自定义数据类型
    priority_queue<Info, vector<Info>> q4;
}

KMP

https://www.acwing.com/blog/content/2347/

const int N = 100010, M= 1000010;

int n, m;
char p[N], s[M];
int ne[N];

int main() {
    cin >> n >> p + 1 >> m >> s + 1;

    // get next array
    for (int i = 2, j = 0; i <= n; 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 <= m; i++) {
        while (j && s[i] != p[j +1]) j = ne[j];
        if (s[i] == p[j+1]) j++;
        if (j == n) {
            // match success
            printf("%d ", i- n);
            j = ne[j];
        }
    }
    return 0;
}

Trie

const int N = 100010;

int son[N][26], cnt[N], idx; // 下标是0的点，即是根节点，又是空节点

void insert(const 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(const 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];
}

并查集

https://www.acwing.com/problem/content/description/838/

#include <iostream>

using namespace std;

const int N = 100010;

int n,m;
int p[N];

// 返回x祖宗节点 + 路径压缩
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) p[i] = i;

    while (m--) {
        char op[2];
        int a,b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M') p[find(a)] = find(b);
        else {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

堆

堆排序 https://www.acwing.com/problem/content/840/

//
// Created by zhuzhicheng on 2022/8/28.
// 838. 堆排序
// https://www.acwing.com/problem/content/840/

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;

int n, m;
int h[N], cnt;

void down(int u) {
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}

void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &h[i]);
    }
  
    cnt = n;

    // for (int i = 1; i <= n / 2; ++i) down(i);
    for (int i = n / 2; i; i--) down(i);

    while (m--) {
        printf("%d ", h[1]);
        h[1] = h[cnt--];
        down(1);
    }

    return 0;
}

线段树

关于线段树 - AcWing

模拟堆c

数学知识

质数

试除法

#include <iostream>
using namespace std;

bool is_prime(int n) {
  if (n < 2) return false;
  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) return false;
  }
  return true;
}

int main () {
  int n;
  cin >> n;
  for (int i = 0; i< n; i++) {
    int x; cin >> x;
    if(is_prime(x)) puts("Yes");
    else puts("No");
  }
  return 0;
}

分解质因数

质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。

#include <iostream>
using namespace std;

void divide(int n) {
  for (int i = 2; i <= n/i; i++) {
    if (n % i == 0) { // i 一定是质数
    	int s = 0;
    	while(n % i == 0) {
    	  n /= i;
    	  s ++;
    	}
    	printf("%d %d\n", i, s);
    }
  }
  
  if (n > 1) printf("%d %d\n", n, 1);
  
  cout << "\n";
}

int main () {
  int n;
  cin >> n;
  for (int i = 0; i< n; i++) {
    int x; cin >> x;
    divide(x);
  }
  return 0;
}

筛质数(埃shi筛法)

https://www.acwing.com/solution/content/7950/

#include <iostream>
using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n) {
  for (int i =2; i <= n; i++) {
    if (!st[i]) {
      primes[cnt ++] = i;
      for (int j = i; j <= n; j += i) st[j] = true;
    }
  }
}

int main() {
  int n;
  cin >> n;
  get_primes(n);
  cout << cnt;
  return 0;
}

约数

试除法

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<int> get_divisions(int n) {
  vector<int> res;

  for (int i = 1; i <= n / i; i++)
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }

  sort(res.begin(), res.end());
  return res;
}


int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    auto res = get_divisions(x);
    for (auto t : res) cout << t << " ";
    cout << endl;

  }
  return 0;

}

约数个数

$N=P1^{\alpha 1}.P2^{\alpha 2}.P3^{\alpha 3}…Pk^{\alpha k}$

约数个数为 $$(\alpha 1+1)(\alpha 2+1)(\alpha 3+1)…(\alpha k+1)$$

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;

  unordered_map<int, int> primes;

  while (n--) {
    int x;
    cin >> x;

    for (int i = 2; i <= x / i; i++)
      while (x % i == 0) {
        x /= i;
        primes[i] ++;
      }

    if (x > 1) primes[x] ++;
  }

  LL res = 1;
  for (auto prime : primes) res = res * (prime.second + 1) % mod;

  cout << res;

  return 0;

}

约数之和为$$(P1^0+ P1^1+P1^2+…+P1^{\alpha 1})…(Pk^0+ Pk^1+Pk^2+…+Pk^{\alpha k})$$

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;

  unordered_map<int, int> primes;

  while (n--) {
    int x;
    cin >> x;

    for (int i = 2; i <= x / i; i++)
      while (x % i == 0) {
        x /= i;
        primes[i] ++;
      }

    if (x > 1) primes[x] ++;
  }

  LL res = 1;
  for (auto prime : primes) {
    int p = prime.first;
    int a = prime.second;

    LL t = 1;
    while (a--) t = (t * p + 1) % mod;

    res = res * t % mod;
  }

  cout << res;

  return 0;

}

最大公约数（欧几里得算法）

#include <iostream>

using namespace std;

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  int n;
  cin >> n;
  while (n--) {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
  }
  return 0;
}

欧拉函数

1∼N 中与 N 互质（最大公约数为1）的数的个数被称为欧拉函数，记为 ϕ(N)。

https://www.acwing.com/solution/content/8702/

#include<iostream>
#include<algorithm>

using namespace std;

int main() {

  int n;
  cin >> n;

  while (n--) {
    int a;
    cin >> a;

    int res = a;
    for (int i = 2; i <= a / i; i++ ) {
      if (a % i == 0) {
        res = res / i * (i - 1);
        while (a % i == 0) a /= i;
      }
    }

    if (a > 1) res = res / a * (a - 1);
    cout << res << endl;
  }
	return 0;
}

筛法求欧拉函数

给定一个正整数n，求1~n中每个数的欧拉函数之和。

https://www.acwing.com/solution/content/3952/

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int primes[N], cnt;
int phi[N];
bool st[N];


LL get_eulers(int n) {
  phi[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[primes[j] * i] = primes[j] * phi[i];
        break;
      }
      phi[primes[j] * i] = (primes[j] - 1) * phi[i];
    }
  }

  LL res = 0;
  for (int i = 1; i <= n; ++ i) {
    res += phi[i];
  }
  return res;
}

int main() {
  int n;
  cin >> n;

  cout << get_eulers(n) << endl;

  return 0;
}

快速幂

#include<iostream>
using namespace std;

using LL = long long;

LL qmi(LL a, int b, int p) {
  LL res = 1;
  while(b) {
    if (b&1) res = res * a % p;
    b >>= 1;
    a = a*a %p;
  }
  return res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        long long res=1;
        cin>>a>>b>>p;
        cout << qmi(a,b,p) <<endl;;
   }
   return 0;
}

欧几里得算法 (辗转相除法)

中国剩余定理

高斯消元

求组合数

容斥原理

博弈论

拆分Nim游戏

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>

using namespace std;

const int N = 110;

int f[N];

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));
    }

  // mex op
  for (int i = 0;; i++)
    if (!S.count(i))
      return f[x] = i;

}

int main() {
  int n ;
  cin >> n;

  memset(f, -1, sizeof f);

  int res = 0;

  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    res ^= sg(x);
  }

  if (res) puts("Yes");
  else puts("No");

  return 0;
}

搜索与图论

图的定义问题

微信公众平台

邻接矩阵

这是一种使用二维矩阵来进行存图的方式。

适用于边数较多的**「稠密图」使用，当边数量接近点的数量的平方，即  时，可定义为「稠密图」**。

// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边  
int[][] w = new int[N][N];  
  
// 加边操作  
void add(int a, int b, int c) {  
    w[a][b] = c;  
}

邻接表

这也是一种在图论中十分常见的存图方式，与数组存储单链表的实现一致（头插法）。

这种存图方式又叫**「链式前向星存图」**。

适用于边数较少的**「稀疏图」使用，当边数量接近点的数量，即  时，可定义为「稀疏图」**。

int N = 110, M = 6010;

int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];  
int idx;  
  
void add(int a, int b, int c) {  
    e[idx] = b;  
    ne[idx] = he[a];  
    he[a] = idx;  
    w[idx] = c;  
    idx++;  
}

首先 idx 是用来对边进行编号的，然后对存图用到的几个数组作简单解释：

  • he 数组：存储是某个节点所对应的边的集合（链表）的头结点；

  • e  数组：由于访问某一条边指向的节点；

  • ne 数组：由于是以链表的形式进行存边，该数组就是用于找到下一条边；

  • w  数组：用于记录某条边的权重为多少。 因此当我们想要遍历所有由 a 点发出的边时，可以使用如下方式：

for (int i = he[a]; i != -1; i = ne[i]) {  
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的边，权重为 c  
}

类

这是一种最简单，但是相比上述两种存图方式，使用得较少的存图方式。

只有当我们需要确保某个操作复杂度严格为O(m)  时，才会考虑使用。

具体的，我们建立一个类来记录有向边信息：

class Edge {  
    // 代表从 a 到 b 有一条权重为 c 的边  
    int a, b, c;  
    Edge(int _a, int _b, int _c) {  
        a = _a; b = _b; c = _c;  
    }  
}

通常我们会使用 List 存起所有的边对象，并在需要遍历所有边的时候，进行遍历：

List<Edge> es = new ArrayList<>();  
  
...  
  
for (Edge e : es) {  
    ...  
}

dfs

https://www.acwing.com/problem/content/844/

const int N = 10;

int path[N];
int sts[N];
int n;

void dfs(int u) {
  if (u == n) {
    for (int i = 0 ;i < n; i++) cout << path[i] << " ";
    puts(" ");

    return;
  }

  for (int i = 0 ;i < n; i++) {
    if (sts[i] != 1) {
      path[u] = i + 1;
      sts[i] = 1;
      dfs(u+1);
      sts[i] = 0;
    }
  }
}

八皇后

https://www.acwing.com/problem/content/845/

solve: https://www.acwing.com/solution/content/2820/

#include <iostream>

using namespace std;

const int N = 10;

int n;
bool col[N], dg[N], udg[N];
char g[N][N];


void dfs(int u) {
  if (u == n) {
    for (int i = 0; i < n; i++) puts(g[i]);
    puts(" ");
    return;
  }
  
  for (int i = 0; i < n; i++) {
    if(!col[i] && !dg[u + i] && !udg[n-u+i]) {
      g[u][i] = 'Q';
      col[i] = dg[u+i] = udg[n-u+i] = true;
      dfs(u+1);
      col[i] = dg[u+i] = udg[n-u+i] = false;
      g[u][i] = '.';
    }
  }
}

int main() {
  cin >> n;
  for (int i = 0; i< n; i++) {
    for (int j = 0; j< n; j++) {
      g[i][j] = '.';
    }
  }
  
  dfs(0);
  
  return 0;
}

bfs

https://www.acwing.com/problem/content/description/846/

https://www.acwing.com/solution/content/2078/

#include <iostream>
#include <queue>

using namespace std;


const int N = 102;
int g[N][N], d[N][N];
int n, m;

using PII = pair<int,int>;

int bfs() {
  queue<PII> q;
  
  for(auto &v: d)
    for (auto &x :v) {
      x = -1;
    }
  
  d[0][0] = 0;
  q.push({0,0});
  
  int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
  
  while(!q.empty()) {
    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 >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
        d[x][y] = d[t.first][t.second] + 1;
        q.push({x,y});
      }
    }
  }
  
  return d[n-1][m-1];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }

    cout << bfs() << endl;

    return 0;
}

树的bfs

https://www.acwing.com/solution/content/13513/

（数组建立邻接表） 树的dfs

//邻接表
int h[N], e[N * 2], ne[N * 2], idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

树的bfs模板

// 需要标记数组st[N],  遍历节点的每个相邻的便
void dfs(int u) {
    st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}

树的dfs

差分与前缀和

前缀和与差分 图文并茂 超详细整理（全网最通俗易懂）_前缀和差分_林小鹿@的博客-CSDN博客

动态规划

背包问题

LFU && LRU

LFU

Updated on 2021-04-29
 algorithm, template
Back | Home