侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【算法模板】工具 & 模板 & 技巧

GabrielxD
2022-05-24 / 0 评论 / 0 点赞 / 138 阅读 / 11,742 字 / 正在检测是否收录...

枚举

指数型枚举

1n1∼nnn 个整数中随机选取任意多个,输出所有可能的选择方案。

int N;
List<Integer> chosen = new ArrayList<>();

void dfs(int x) {
    if (x == N + 1) {
        boolean flag = true;
        for (int num : chosen) {
            if (flag) flag = false;
            else System.out.print(" ");
            System.out.print(num);
        }
        System.out.print("\n");
        return;
    }

    dfs(x + 1);
    chosen.add(x);
    dfs(x + 1);
    chosen.remove(chosen.size() - 1);
}

组合型枚举

1n1∼nnn 个整数中随机选出 mm 个,输出所有可能的选择方案。

int N, M;
List<Integer> chosen = new ArrayList<>();

void dfs(int x) {
    if (chosen.size() > M || chosen.size() + (N - x + 1) < M) return;
    if (x == N + 1) {
        boolean flag = true;
        for (int num : chosen) {
            if (flag) flag = false;
            else System.out.print(" ");
            System.out.print(num);
        }
        System.out.print("\n");
    }
    chosen.add(x);
    dfs(x + 1);
    chosen.remove(chosen.size() - 1);
    dfs(x + 1);
}

排列型枚举

1n1∼nnn 个整数排成一行后随机打乱顺序,输出所有可能的次序。

int N;
int[] nums = new int[20];
boolean[] used = new boolean[20];

void dfs(int x) {
    if (x == N + 1) {
        for (int i = 1; i <= N; ++i) {
            if (i > 1) System.out.print(" ");
            System.out.print(nums[i]);
        }
        System.out.print ("\n");
        return;
    }
    for (int i = 1; i <= N; ++i) {
        if (!used[i]) {
            nums[x] = i;
            used[i] = true;
            dfs(x + 1);
            nums[x] = 0;
            used[i] = false;
        }
    }
}

排序

快速排序

  1. 找到分界点 p(有三种选择:q[l]q[l + r >> 1]q[r])。
  2. 将区间 [l,r][l, r] 划分为两段,使得分界点左边所有数 LeftpLeft \le p,分界点右边所有数 RightqRight \ge q
  3. 递归地排序左右两边:sort(Left)sort(Right)

应用:【快速选择】第k个数

void quickSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int p = nums[l + (r - l >> 1)], i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (nums[i] < p);
        do --j; while (nums[j] > p);
        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quickSort(nums, l, j);
    quickSort(nums, j + 1, r);
}
void quick_sort(int nums[], int l, int r) {
    if (l >= r) return;
    int p = nums[l + (r - l >> 1)], i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (nums[i] < p);
        do --j; while (nums[j] > p);
        if (i < j) swap(nums[i], nums[j]);
    }
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

归并排序

  1. 把区间 [l,r][l, r] 从中点(mid = l + r >> 1)分割为 [l,mid][l, mid] 以及 [mid+1,r][mid + 1, r]
  2. 递归排序左右两边:sort(l, mid)sort(mid + 1, r)
  3. 归并,将左右两个有序序列合成为一个有序序列。

应用:【归并排序】逆序对的数量

int[] tmp; // 全局开一个与nums一样长的数组(在主函数中赋值)

void mergeSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l >> 1);
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
 	while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) nums[i] = tmp[j];
}
int tmp[N]; // 全局开一个与nums一样长的数组

void merge_sort(int nums[], int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l >> 1);
    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) nums[i] = tmp[j];
}

二分查找

整数二分

通用模板

check() 判断 mid 是否满足某种性质。

模板一

区间 [l,r][l, r] 被划分成 [l,mid][l, mid][mid+1,r][mid + 1, r] 时使用。

bool check(int x) {/* ... */} // 检查x是否满足某种性质

int bsearch(int l, int r) {
    while (l < r) {
        int mid = l + (r - l >> 1);
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
模板二
bool check(int x) {/* ... */} // 检查x是否满足某种性质

int bsearch(int l, int r) {
    while (l < r) {
        int mid = l + (r - l + 1 >> 1);
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

相等

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
左边界

找到等于 x 的元素中最靠左的索引,没有符合要求的索引则返回 -1
等同于下文的:大于等于

int left_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left >> 1);
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return nums[left] == target ? left : -1;
}
右边界

找到等于 x 的元素中最靠右的索引,没有符合要求的索引则返回 -1
等同于下文的:小于等于

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left + 1 >> 1);
        if (nums[mid] <= target) left = mid;
        else right = mid - 1;
    }
    return nums[left] == target ? left : -1;
}

小于等于

找到小于等于 x 的元素中最大的索引,没有符合要求的索引则返回 -1

int bsearch_leq(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + ((right - left + 1) >> 1);
        if (nums[mid] <= target) left = mid;
        else right = mid - 1;
    }
    return nums[left] <= target ? left : -1;
}

大于等于

找到大于等于 x 的元素中最小的索引,没有符合要求的索引则返回 -1

int bsearch_geq(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return nums[left] >= target ? left : -1;
}

浮点数二分

eps 表示精度,取决于题目对精度的要求。

const double eps = 1e-6;

double bsearch(double l, double r) {
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

nm 次方根

double root(int n, int m, double eps) {
    double l = 0.0, r = m;
    while (r - l > eps) {
        double c = (l + r) / 2;
        double product = 1.0;
        for (int i = 0; i < m; ++i) product *= c;
        if (product >= n) r = c;
        else l = c;
    }
}

高精度

待补充…

前缀和

一维前缀和

原数组下标从 00 开始:

  • 定义:S[i]=a[0]+a[1]+...+a[i1]=j=0i1a[j]S[i] = a[0] + a[1] + ... + a[i-1] = \sum_{j=0}^{i-1}a[j]
  • 构造:S[0]=0S[0] = 0S[i]=S[i1]+a[i1]S[i] = S[i - 1] + a[i - 1]
  • 使用:a[l]+...+a[r]=S[r+1]S[l]a[l] + ... + a[r] = S[r + 1] - S[l]

原数组下标从 11 开始:

  • 定义:S[i]=a[1]+a[2]+...+a[i]=j=1ia[j]S[i] = a[1] + a[2] + ... + a[i] = \sum_{j=1}^{i}{a[j]}
  • 构造:S[0]=0S[0]=0S[i]=S[i1]+a[i]S[i] = S[i - 1] + a[i]
  • 使用:a[l]+...+a[r]=S[r]S[l1]a[l] + ... + a[r] =S[r] - S[l - 1]

二维前缀和

  • 定义:S[i][j]=ij列格子左上部分所有元素的和=x=0i(y=0j)S[i][j] = 第i行j列格子左上部分所有元素的和 = \sum_{x=0}^{i}(\sum_{y=0}^j)
  • (x1,y1)(x1, y1) 为左上角,(x2,y2)(x2, y2) 为右下角的子矩阵的和为:
    S[x2][y2]S[x11][y2]S[x2][y11]+S[x11][y11]S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]

差分

一维差分

  • 给区间 [l,r][l, r] 中的每个数加上 c

    b[l] += c;
    b[r + 1] -= c
    

二维差分

  • 给以 (x1,y1)(x1, y1) 为左上角,(x2,y2)(x2, y2) 为右下角的子矩阵中的所有元素加上 c

    b[x1, y1] += c;
    b[x2 + 1, y1] -= c;
    b[x1, y2 + 1] -= c;
    b[x2 + 1, y2 + 1] += c
    

双指针

常见问题分类:

  1. 对于一个序列,用两个指针维护一段区间。
  2. 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作。

实例:【双指针】最长连续不重复子序列

for (int i = 0, j = 0; i < n; ++i) {
    while (j < i && check(i, j)) ++j;
	// 具体问题的逻辑
}

滑动窗口

void slidingWindow(char[] s) {
    int n = s.length;
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    while (right < n) {
        char curr = s[right++];
    	window.put(curr, window.getOrDefault(curr, 0) + 1);
        // 更新窗口内数据
        // ...
        // 判断窗口是否需要收缩
        while (窗口需要收缩) {
            // 在窗口每次收缩前更新答案
            // ...
            curr = s[left++];
            window.put(curr, window.getOrDefault(curr, 0) - 1);
            // 更新窗口内数据
        	// ...
        }
        // 在窗口收缩后更新答案
        // ...
    }
}
void sliding_window(string s) {
    int n = s.length();
    unordered_map<char, int> window;
    int left = 0, right = 0;
    while (right < n) {
        char curr = s[right++];
        ++window[curr];
        // 更新窗口内数据
        // ...
        // 判断窗口是否需要收缩
        while (窗口需要收缩) {
            // 在窗口每次收缩前更新答案
            // ...
            curr = s[left++];
            --window[curr];
            // 更新窗口内数据
        	// ...
        }
        // 在窗口收缩后更新答案
        // ...
    }
}

位运算

  • n 的第 k 位数字:n >> k & 1
  • 返回 n 的最后一位 1lowbit(n) = n & -n

离散化

离散化是一种比较特殊的哈希方式。

详细介绍:离散化 - OI Wiki

实例:【离散化, 前缀和】区间和「离散化经典应用」

C++ 模板

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重

二分求出 x 对应的离散化的值:

int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        // 找到第一个大于等于x的位置
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    // 映射若从0开始直接返回 从1开始返回要+1
    return r + 1;
}

Java 模板

List<Integer> alls = new ArrayList<>(); // 存储所有待离散化的值
Collections.sort(alls); // 排序
alls = alls.subList(0, unique()); // 去重 

unique() 函数实现:
实现原理见:【双指针】删除有序数组中的重复项

int unique() {
    int n = alls.size();
    int slow = 0;
    for (int fast = 0; fast < n; ++fast) {
        // 注意这里拿到的是整数包装类 所以一定要使用equals()方法判断是否相同
        if (!alls.get(slow).equals(alls.get(fast))) alls.set(++slow, alls.get(fast));
    }
    return slow + 1;
}

二分求出 x 对应的离散化的值:

int find(int x) {
    int l = 0, r = sz - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls.get(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

区间合并

将所有存在交集的区间合并

C++ 模板

void merge(vector<PII>& segs) {
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = NEG_INF, ed = NEG_INF;
    for (auto& seg : segs) {
        if (ed < seg.first) {
            if (st != NEG_INF) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else ed = max(ed, seg.second);
    }
    if (st != NEG_INF) res.push_back({st, ed});
    segs = res;
}

Java 模板

List<int[]> merge(List<int[]> segs) {
    segs.sort((a, b) -> a[0] - b[0]);
    List<int[]> res = new ArrayList<>();
    int st = NEG_INF, ed = NEG_INF;	
    for (int[] seg : segs) {
        if (ed < seg[0]) {
            if (st != NEG_INF) res.add(new int[]{st, ed});
            st = seg[0];
            ed = seg[1];
        } else ed = Math.max(ed, seg[1]);
    }
    if (st != NEG_INF) res.add(new int[]{st, ed});
    return res;
}

链表

单链表

数组模拟单链表:

// vals存储节点的值 nexts存储指向下一个节点的指针
int vals[N], nexts[N];
// head表示指向表头的指针(vals[head]就会取到表头的值)
// idx指向当前可用的节点(链表尾的空节点)
int head, idx;

// 初始化 头节点指针为-1表示没有头节点 idx=1表示当前可用的节点是第1个节点
void init() {
    head = -1;
    idx = 0;
}

// 向链表头部插入一个值为x的节点
void insert_to_head(int x) {
    vals[idx] = x;
    nexts[idx] = head;
    head = idx++;
}

// 在第k个节点*之后*插入一个值为x的节点
void insert(int k, int x) {
    vals[idx] = x;
    nexts[idx] = nexts[k];
    nexts[k] = idx++;
}

// 删除第k个节点*之后*的一个节点
void remove(int k) {
    nexts[k] = nexts[nexts[k]];
}

双链表

数组模拟双链表:

// vals存储节点的值 nexts存储指向下一个节点的指针 prevs存储上一个节点的指针
int vals[N], prevs[N], nexts[N];
int idx; // idx指向当前可用的节点(链表尾的空节点)

// 初始化 在双链表中默认第0个节点为头节点 第1个节点为尾节点
// 此时头节点下一个节点是尾节点 尾节点上一个节点是头节点 idx=2表示当前可用的节点是第2个节点
void init() {
    nexts[0] = 1;
    prevs[1] = 0;
    idx = 2;
}

// 在第k个节点*之后*插入一个值为x的节点
void insert(int k, int x) {
    vals[idx] = x;
    prevs[idx] = k;
    nexts[idx] = nexts[k];
    prevs[nexts[idx]] = idx;
    nexts[k] = idx++;
}

// 删除第k个节点
void remove(int k) {
    prevs[nexts[k]] = prevs[k];
    nexts[prevs[k]] = nexts[k];
}

数组模拟栈:

int stk[N];
int tt = 0; // 栈顶初始化为0 栈中元素从1开始

// 向栈顶推入一个数x
void push(int x) {
    stk[++tt] = x;
}

// 从栈顶弹出一个数
void pop() {
    --tt;
}

// 判断栈是否为空 tt==0时表示栈为空
bool empty() {
    return !tt;
}

// 返回栈顶的值
int top() {
    return stk[tt];
}

队列

数组模拟普通队列:

int que[N];
int hh = 0, tt = -1; // hh表示队头 tt表示队尾 队中元素从0开始

// 向队尾放入一个数x
void offer(int x) {
    que[++tt] = x;
}

// 从队头拉出一个数
void poll() {
    ++hh;
}

// 判断队列是否为空 tt<hh时表示队列为空
bool empty() {
    return tt < hh;
}

// 返回队头的值
int front() {
    return que[hh];
}

// 返回队尾的值
int back() {
    return que[tt];
}

数组模拟循环队列:

int que[N];
int hh = 0, tt = 0; // hh表示队头 tt表示队尾的后一个位置

// 向队尾放入一个数x
void offer(int x) {
    que[tt++] = x;
    if (tt == N) tt = 0;
}

// 从队头拉出一个数
void poll() {
    if (++hh == N) hh = 0;
}

// 返回队头的值
int front() {
    return que[hh];
}

// 判断队列是否为空 tt==hh时表示队列为空
bool empty() {
    return tt == hh;
}

单调栈

模板题:找出每个数左边第一个比它大/小的数

int stk[N], tt = 0;
for (int x : nums) {
    while (tt > 0 && check(stk[tt], x)) --tt;
    stk[++tt] = x;
}

单调队列

模板题:找出滑动窗口中的最大值/最小值

int que[N], hh = 0, tt = -1;
for (int i = 0; i < n; ++i) {
    while (hh <= tt && check_out(que[hh])) ++hh; // 判断队头是否滑出窗口
    while (hh <= tt && check(que[tt], nums[i])) --tt;
    q[++tt] = i;
}

KMP 算法

经典应用:【KMP算法, Rabin-Karp算法, 快速幂】找出字符串中第一个匹配项的下标

// pat: 模式串, str: 主串
int m = pat.length, n = str.length;

// 求next数组
int[] nexts = new int[m];
nexts[0] = -1;
for (int i = 1, j = -1; i < m; ++i) {
    while (j >= 0 && pat[j + 1] != pat[i]) j = nexts[j]; // 前后缀不相同了 向前回退
    if (pat[j + 1] == pat[i]) ++j; // 找到相同的前后缀
    nexts[i] = j;
}

// 匹配
for (int i = 0, j = -1; i < n; ++i) {
	while (j >= 0 && pat[j + 1] != str[i]) j = nexts[j];
	if (pat[j + 1] == str[i]) ++j;
	if (j + 1 == m) {
		// 匹配成功
		j = nexts[j]; // 回退进行下一次匹配
	}
}

Trie 树

模板题:Trie字符串统计

// N为最大可能插入的字符串数 M为最大可能的节点数(N乘以字符串最大可能的长度)
int sons[M][26], cnt[N], idx;

void insert(char word[]) {
    int p = 0;
    for (int i = 0; word[i]; ++i) {
        int curr = word[i] - 'a';
        if (!sons[p][curr]) sons[p][curr] = ++idx;
        p = sons[p][curr];
    }
    ++cnts[p];
}

int count(char word[]) {
    int p = 0;
    for (int i = 0; word[i]; ++i) {
        int curr = word[i] - 'a';
        if (!sons[p][curr]) return 0;
        p = sons[p][curr];
    }
    return cnts[p];
}

并查集

路径压缩优化的并查集

模板题:合并集合

class UnionFind {
    private int[] root;
    
    public UnionFind(int size) {
        root = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        root[find(p)] = find(q);
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
class UnionFind {
private:
    int* root;

public:
    UnionFind(int size) : root(new int[size]) {
        for (int i = 0; i < size; ++i) root[i] = i;
    }

    int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    void join(int p, int q) {
        root[find(p)] = find(q);
    }
    
    bool is_connected(int p, int q) {
        return find(p) == find(q);
    }
};

基于路径压缩的按秩合并优化的并查集

class UnionFind {
    private int[] root;
    private int[] rank;
    
    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootP] > rank[rootQ]) root[rootQ] = rootP;
        else {
        	root[rootP] = rootQ;
            if (rank[rootP] == rank[rootQ]) ++rank[rootP];
        }
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
class UnionFind {
private:
    int* root;
    int* rank;

public:
    UnionFind(int size) : root(new int[size]), rank(new int[size]) {
        for (int i = 0; i < size; ++i) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    void join(int p, int q) {
        int root_p = find(p), root_q = find(q);
        if (root_p == root_q) return;
        if (rank[root_p] > rank[root_q]) root[root_q] = root_p;
        else {
        	root[root_p] = root_q;
            if (rank[root_p] == rank[root_q]) ++rank[root_p];
        }
    }
    
    bool is_connected(int p, int q) {
        return find(p) == find(q);
    }
};

统计连通分量的综合并查集

class UnionFind {
    public int groups;
    private int[] root;
    private int[] rank;
    
    public UnionFind(int size) {
        groups = size;
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootP] > rank[rootQ]) root[rootQ] = rootP;
        else {
        	root[rootP] = rootQ;
            if (rank[rootP] == rank[rootQ]) ++rank[rootP];
        }
        --groups;
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

维护每个集合大小的并查集

模板题:连通块中点的数量

class UnionFind {
    private int[] roots, sizes;
    
    public UnionFind(int size) {
        roots = new int[size];
        for (int i = 0; i < size; ++i) {
            roots[i] = i;
            sizes[i] = 1;
        }
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rp = find(p), rq = find(q);
        if (rp != rq) {
            root[rp] = rq;
        	sizes[rq] += sizes[rp];
        }
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

维护每个节点到根节点距离的并查集

class UnionFind {
    private int[] roots, dists;
    
    public UnionFind(int size) {
        roots = new int[size];
        for (int i = 0; i < size; ++i) {
            roots[i] = i;
            dists[i] = 0;
        }
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        roots[find(p)] = find(q);
        dists[find(p)] = distance; // 根据具体问题,初始化find(a)的偏移量
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

模板题:堆排序模拟堆

// h存储堆中的值, h[1]是堆顶, x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点,及其映射关系
void heap_swap(int a, int b) {
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int k) {
    int min = k;
    if (k * 2 <= size && h[k * 2] < h[min]) min = k * 2;
    if (k * 2 + 1 <= size && h[k * 2 + 1] < h[min]) min = k * 2 + 1;
    if (k != min) {
        heap_swap(min, k);
        down(min);
    }
}

void up(int k) {
    while (k / 2 > 0 && h[k] < h[k / 2]) {
        heap_swap(k, k / 2);
        k /= 2;
    }
}

// O(n)时间把数组建成堆
for (int i = n / 2; i > 0; --i) down(i);

哈希

一般哈希

模板题:【哈希表】模拟散列表「哈希表基础」

素数选取表:

lwr upr prime
2^5 2^6 53
2^6 2^7 101
2^7 2^8 193
2^8 2^9 389
2^9 2^10 769
2^10 2^11 1531
2^11 2^12 3061
2^12 2^13 6113
2^13 2^14 12253
2^14 2^15 24379
2^15 2^16 48883
2^16 2^17 97787
2^17 2^18 195677
2^18 2^19 391627
2^19 2^20 783259
2^20 2^21 1566401
2^21 2^22 3133987
2^22 2^23 6269119
2^23 2^24 12538073
2^24 2^25 25082363
2^25 2^26 50170979
2^26 2^27 100353503
2^27 2^28 200730139
2^28 2^29 401498927
2^29 2^30 803081491

开放寻址法

// 一般N取比一倍数据范围大的素数 INF取0x3f3f3f3f
int ht[N];

// 如果x在哈希表中就返回x的下标 否则返回x应该插入的位置
int find(int x) {
    int y = (x % N + N) % N;
    while (ht[y] != INF && ht[y] != x) {
        if (++y == N) y = 0;
    }
    return y;
}

拉链法

拉链的方法与单链表向头节点前插入相同。

// 一般N取两到三倍数据范围的素数
int ht[N], vals[N], nexts[N], idx;

// 初始化
void init() {
    idx = 0;
    memset(ht, -1, sizeof(ht));
}

// 向哈希表中插入一个数
void insert(int x) {
    int y = (x % N + N) % N;
    // 从单链表头插入
    vals[idx] = x;
    nexts[idx] = ht[y];
    ht[y] = idx++;
}

// 在哈希表中查询某个数是否存在
bool find(int x) {
    int y = (x % N + N) % N;
    for (int i = ht[y]; i != -1; i = nexts[i]) {
        if (vals[i] == x) return true;
    }
    return false;
}

字符串哈希

核心思想:将字符串看成P进制数,P的经验值是 1311311333113331,取这两个值的冲突概率低。
小技巧 - 自然溢出:取模的数用 2642^{64},这样直接用 unsigned long long (Java 用 long)存储,溢出的结果就是取模的结果,这样可以省去取模的代码和时间。

模板题:字符串哈希

typedef unsigned long long ULL;

// h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
ULL h[N], p[N]; 

// 初始化
void init() {
    // s是下标从0开始的字符串 n是其长度
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] * P + str[i - 1];
        p[i] = p[i - 1] * P;
    }
}

// 计算子串 str[l...r] 的哈希值
ULL sub_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

BFS

求「最少能从初始状态到达结束状态的步数」问题的 BFS 模板。

import java.util.*;
import java.io.*;

public class Main {
    // 状态对象
    static class State {
        T content; // 状态
        int step; // 步数

        State(T content, int step) {
            // 初始化
            this.content = content;
            this.step = step;
        }

        // 重写equals方法对比状态是否相同
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof State)) return false;
            State s = (State) obj;
            // 对比状态
            // ...
        }

        // 重写hashCode方法用于存入集合 以便于快速确认状态的存在与否
        @Override
        public int hashCode() {
            // ...
        }

        // 由当前状态生成新的状态
        State newFrom(T content) {
            // ...
            return new State(content, step + 1);
        }
    }

    static State origin, target;
    
    public static void main(String[] args) throws IOException {
        // 输入状态 初始状态的步数皆为 0
        origin = new State(/* 初始状态 */, 0);
        target = new State(/* 目标状态 */, 0);
        // 输出结果(最少能从初始状态到达结束状态的步数)
        System.out.println(bfs());
    }

    static int bfs() {
        Queue<State> que = new LinkedList<>(); // BFS辅助队列
    	Set<State> vis = new HashSet<>(); // 判断状态是否已经见到过 用于剪枝
        que.offer(origin); // 放入初始状态
        while (!que.isEmpty()) {
            // 取出队尾状态
            State state = que.poll();
            // base case: 当前状态和达到目标则直接返回步数即是最短步数
            if (state.equals(target)) return state.step;
            // 枚举所有合法的状态转移
            for (eachValid in possibilities) {
                // 生成新状态
                State newState = state.newFrom(eachValid);
                // 若新生成的状态在以前没遇到过就把它加入队列与集合
                if (!set.contains(newState)) {
                    set.add(newState);
                    que.add(newState);
                }
            }
        }
        return -1;
    }
}

树与图

存储

树是一种特殊的图(无环连通图),与图的存储方式相同:对于无向图中的边 aba \to b,存储两条有向边 ab,baa \to b, b \to a,因此我们可以只考虑有向图的存储。

邻接矩阵

g[a][b]g[a][b] 存储边 aba \to b,使用空间较多,适合存稠密图。

邻接表

类似一般哈希 - 拉链法

// N为点数 M为面数一般取N的两倍
// heads中每个节点下标都存储着一个链表(头)
int heads[N], vals[M], nexts[M], idx;

// 初始化
void init() {
    idx = 0;
    memset(heads, -1, sizeof(ht));
}

// 添加一条边a->b
void add(int a, int b) {
    vals[idx] = b;
    nexts[idx] = heads[a];
    heads[a] = idx++;
}

遍历

时间复杂度:O(N+M)O(N + M)NN 表示顶点数,MM 表示边数)

深度优先遍历

模板题:树的重心

int heads[N], vals[M], nexts[M], idx;
int vis[N]; // 记录点是否被遍历过

int dfs(int u) {
    vis[u] = true;
    for (int i = heads[u]; i != -1; i = nexts[i]) {
        int v = heads[i];
        if (!vis[v]) dfs(v);
    }
}

宽度优先遍历

模板题:图中点的层次

int heads[N], vals[M], nexts[M], idx;
int vis[N]; // 记录点是否被遍历过

void bfs(int u) {
    queue<int> que;
    que.push(u); // 从顶点u开始遍历
	vis[u] = true;
    while (!que.empty()) {
        int t = que.front();
        que.pop();
        for (int i = heads[t]; i != -1; i = nexts[i]) {
            int v = vals[i];
            if (!vis[v]) {
                que.push(v);
                st[v] = true;
            }
        }
    }
}

拓扑排序

时间复杂度:O(N+M)O(N + M)NN 表示顶点数,MM 表示边数)

模板题:有向图的拓扑序列

int n, m, idx;
int heads[N], vals[M], nexts[M], ind[N]; // ind维护所有顶点的入度
int que[N], hh, tt = -1; // 维护一个队列

bool top_sort() {
    // 把所有入度为0的顶点先入队
    for (int i = 1; i <= n; ++i) {
        if (!ind[i]) que[++tt] = i;
    }
    while (hh <= tt) {
        int t = que[hh++];
        for (int i = heads[t]; i != -1; i = nexts[i]) {
            int v = vals[i];
            if (--ind[v] == 0) que[++tt] = v;
        }
    }
    // 如果所有点都入队了 说明存在拓扑序列 否则不存在拓扑序列
    return tt == n - 1;
}

if (top_sort()) {
    // 存在拓扑排序 输出拓扑排序
    for (int i = 0; i < n; ++i) printf("%d ", que[i]);
}

最短路算法

image-20221111182633376

单源最短路

朴素 Dijkstra 算法

时间复杂度: O(N2+M)O(N^2 + M)NN 表示顶点数,MM 表示边数)

一般用在不存在负权边的稠密图求单源最短路中。

求图中点 ori 到点 dest 的最短路,算法步骤:

使用邻接矩阵(g)存图,n 表示顶点的数量,维护 dists 用于存储点 ori 到任意点的最短距离,维护 vis 表示某个点是否被访问过,若一个顶点被访问过就说它是当前已确定最短距离的点

  1. 初始化:把 dists 中所有数初始化为正无穷(一般用 INF=0x3f3f3f3f 代替), dists[ori] = 0
  2. 循环 n-1 次:
    1. 取出还未确定最短距离(!vis[i])的,距离 ori 最近的顶点(mn)。
    2. mn 置为最短距离已确认的点。
    3. mn 更新 ori 到其他点的最短距离。
  3. 循环结束后若 dists 中存储的 oridest 的距离不为 INF 就说明 ori 到点 dest 的最短距离是 dists[dest]

模板代码:

const int INF = 0x3f3f3f3f;
int n;
int g[N][N], dists[N];
bool vis[N];

// 返回ori到dest的最短距离 不存在则返回-1
int dijkstra(int ori, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    dists[ori] = 0;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) {
            dists[j] = min(dists[j], dists[mn] + g[mn][j]);
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}
堆优化 Dijkstra 算法

时间复杂度: O(MlogN)O(M \log{N})NN 表示顶点数,MM 表示边数)

一般用在不存在负权边的稀疏图求单源最短路中。

和朴素 Dijkstra 算法思路一样,但是会把遍历求出最小值的操作优化为小根堆取堆顶,由于是稀疏图,使用邻接表存图。

模板代码:

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;
int heads[N], vals[N], weights[N], nexts[N], idx; // 邻接表存图
int dists[N]; // 所有点到ori的距离
bool vis[N]; // 每个点的最短距离是否已确定

// 返回ori到dest的最短距离 不存在则返回-1
int dijkstra(int ori, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    dists[ori] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
    heap.push({0, ori}); // 优先队列存pair时默认按照first排序 first存储距离 second存储节点编号
    while (!heap.empty()) {
        auto curr = heap.top();
        heap.pop();
        int mn = curr.second;
        if (vis[mn]) continue;
        int dist = curr.first;
        vis[mn] = true;
        for (int i = heads[mn]; i != -1; i = nexts[i]) {
            int j = vals[i];
            if (dist + weights[i] < dists[j]) {
                dists[j] = dist + weights[i];
                heap.push({dists[j], j});
            }
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}
Bellman-Ford 算法

时间复杂度: O(NM)O(NM)NN 表示顶点数,MM 表示边数)

一般用在存在负权边的图求单源最短路中。

求图中点 ori 到点 dest 的最短路,算法步骤:
使用结构体(edges)存图(只要能把所有边存下来用于遍历就行),n 表示顶点的数量,维护 dists 用于存储点 ori 到任意点的最短距离。伪代码:

for n: // 迭代k次时dists数组表示从ori经过不超过k条边走到每个点的最短距离
	for a, b, w in edges:
		dists[b] = min(dists[b], dists[a] + w) // 松弛操作

循环之后,所有边的距离一定满足:dist[b]<dist[a]+wdist[b] < dist[a] + w (三角不等式)

*模板代码:

const INF = 0x3f3f3f3f;
struct Edge {
    int a, b, w;
} edges[M];
int dists[N], bak[N];
int n, m, k; // n表示点数 m表示边数

int bellman_ford(int ori, int dest, int k) {
    memset(dists, 0x3f, sizeof(dists));
    dists[ori] = 0;
    while (k--) {
        memcpy(bak, dists, sizeof(dists)); // 备份上一次的结果 防止更新串联
        for (int i = 0; i < m; ++i) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            dists[b] = min(dists[b], bak[a] + w);
        }
    }
    return dists[dest];
}

int ans = bellman_ford(1, n); // 求最短路
if (ans > INF / 2) // 有可能出现最短路不存在但是dists[dest]被更新的情况 所以只要取到的ans比数据范围大就记为不存在最短路
else printf("%d\n", ans);
SPFA 算法

时间复杂度:一般情况下 O(M)O(M) 最坏情况下 O(NM)O(NM)NN 表示顶点数,MM 表示边数)

一般用在不存在负权回路的图求单源最短路中。

求图中点 ori 到点 dest 的最短路,算法步骤:

使用邻接表存图,n 表示顶点的数量,维护 dists 用于存储点 ori 到任意点的最短距离,维护 vis 表示某个点是否在队列中。

  1. 初始化:把 dists 中所有数初始化为正无穷(一般用 INF=0x3f3f3f3f 代替), dists[ori] = 0,把起始点放入队列,并标记起始点在队中。
  2. 当队列不为空时,循环:
    1. 取出队头(u),标识 u 已不在队中。
    2. 遍历顶点 u 的所有出边:
      • 拿到顶点 v ,尝试用 u 的最短路更新 dists[v],如果可以更新并且 v 不在队列中,就把 v 入队。
  3. 循环结束后如果 dists[dest] 不大于 INF / 2 就说明 oridest 的最短路存在且为 dists[dest]

模板代码:

const int INF = 0x3f3f3f3f;
int heads[N], vals[M], wts[M], nexts[M], idx;
int dists[N];
bool vis[N]

// 返回ori到dest的最短距离 不存在则返回-1
int spfa(int ori, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    dists[ori] = 0;
    queue<int> que;
    que.push(ori);
    vis[ori] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (int i = heads[u]; i != -1; i = nexts[i]) {
            int v = vals[i];
            if (dists[u] + wts[i] < dists[v]) {
                dists[v] = dists[u] + wts[i];
                if (!vis[v]) {
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}
SPFA 算法判复环

时间复杂度:O(NM)O(NM)NN 表示顶点数,MM 表示边数)

一般用在图求是否存在负权回路中。

算法步骤与普通 SPFA 算法几乎相同。

原理:如果某条最短路径上有 n 个点(除了自己),那么加上自己之后一共有 n+1 个点,由抽屉原理一定有两个点相同,所以存在环。

模板代码:

const int INF = 0x3f3f3f3f;
int heads[N], vals[M], wts[M], nexts[M], idx;
int dists[N], cnts[N]; // cnts存储这每个点最短路中经过的点数
bool vis[N];

// 如果图中存在复环返回true 否则返回false
bool spfa() {
    // 不用初始化dists 因为我们只需能看出短路的变化趋势即可 不需要真的求出最短路
    queue<int> que;
    // 有些节点的最短路可能并不经过负权回路 为了找出整个图中是否存在负权回路 要把所有顶点全部算上
    for (int x = 1; x <= n; ++x) {
        que.push(x);
        vis[x] = true;
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (int i = heads[u]; i != -1; i = nexts[i]) {
            int v = vals[i];
            if (dists[u] + wts[i] < dists[v]) {
                dists[v] = dists[u] + wts[i];
                cnts[v] = cnts[u] + 1;
                // 如果从1号点到x的最短路中包含至少n个点(不包括自己) 说明存在负权回路
                if (cnts[v] >= n) return true;
                if (!vis[v]) {
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return false;
}

多源汇最短路

Floyd 算法

时间复杂度: O(N3)O(N^3)NN 表示顶点数)

一般用在不存在负权回路的图求多源汇最短路中。

使用邻接表存图,n 表示顶点的数量,维护 dists 用于存储任意点到任意点的最短距离。

算法步骤(伪代码):

// 初始化 n表示顶点的数量
for i from 1 to n:
   	for j from 1 to n:
		d[i][j] = i == j ? 0 : INF

// Floyd算法
for k from 1 to n:
	for i from 1 to n:
		for j from 1 to n:
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])

模板代码:

const INF = 0x3f3f3f3f;
int n; // 顶点数量
int dists[N][N]; // 邻接矩阵存图

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j]);
            }
        }
    }
}

// ori->dest的最短路
if (dists[ori][dest] > INF / 2) // 不存在最短路
else // 最短路为dists[ori][dest]

最小生成树算法

image-20221115094034018

  • 生成树生成树 指的是「无向图」中,具有该图的 全部顶点边数最少连通子图
  • 最小生成树最小生成树 指的是「加权无向图」中总权重最小的生成树。

朴素 Prim 算法

时间复杂度: O(N2)O(N^2)NN 表示顶点数)

一般用在稠密图求最小生成树中。

与 [Dijkstra 算法](#朴素 Dijkstra 算法) 相似,算法步骤:

使用邻接矩阵(g)存图,n 表示顶点的数量,维护 dists 用于存储集合外的点到集合的最短距离,维护 vis 表示某个点是否已经被放入最小生成树。

  1. 初始化:把 dists 中所有数初始化为正无穷。
  2. 循环 n 次:
    1. 找到集合外距离集合最近的点(mn)。
    2. mn 放入最小生成树(vis[mn] = true)。
    3. mn 更新其他点到集合的最短距离。

为什么 Dijkstra 算法外层循环 n-1 次而 Prim 算法要循环 n 次?

——因为 Dijkstra 算法在循环前已经源点加入了集合,只用迭代 n-1 个点,而 Prim 算法要迭代所有 n 个顶点。

模板代码:

const INF = 0x3f3f3f3f;
int n; // 顶点数量
int g[N][N]; // 邻接矩阵存图
dists[N];
bool vis[N];

// 返回最小生成树的权值和 若不存在则返回INF
int prim() {
    memset(dists, 0x3f, sizeof(dists));
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        if (i) {
            if (dists[mn] == INF) return INF; // 发现不是所有点连通 不存在最小生成树
            res += dists[mn]; // 把mn加入最小生成树 并把dists[mn]累加进权值和
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) dists[j] = min(dists[j], g[j][mn]);
    }
    return res;
}

int ans = prim();
if (ans == INF) // 不存在最小生成树
else // 存在最小生成树

Kruskal 算法

时间复杂度: O(MlogM)O(M \log M)MM 表示边数)

一般用在稀疏图求最小生成树中。

算法步骤:

  1. 将所有边按照权重升序排序。
  2. 枚举每条边 uwvu \xleftrightarrow{w} v
    • 如果 a,ba, b 不连通,将这条边也加入集合中。
const int INF = 0x3f3f3f3f;
int m; // 边数
struct Edge {
    int u, v, w;
    
    bool operator<(const Edge& e) {
        return w < e.w;
    }
} edges[M]; // 结构体存储所有边 并按照权值升序排序
int roots[N];

// 并查集操作
int find(int x) {
    return x == roots[x] ? x : (roots[x] = find(roots[x]));
}

void join(int p, int q) {
    roots[find(p)] = find(q);
}

// 返回最小生成树的权值和 若不存在则返回INF
int kruskal() {
    sort(edges, edges + m);
    for (int i = 1; i <= n; ++i) roots[i] = i;
    int cnt = 0, res = 0;
    for (int i = 0; i < m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) {
            join(u, v);
            res += w;
            if (++cnt == n - 1) break;
        }
    }
    return cnt < n - 1 ? INF : res;
}

int ans = kruskal();
if (ans == INF) // 不存在最小生成树
else // 存在最小生成树

染色法判定二分图

时间复杂度: O(N+M)O(N + M)NN 表示顶点数,MM 表示边数)

模板代码:

int n, idx;
int colors[N];

bool dfs(int u, int c) {
    colors[u] = c; // 给u染色
    // 枚举与u相连的所有顶点
    for (int i = heads[u]; i != -1; i = nexts[i]) {
        int v = vals[i];
        // 若顶点v没染过色 给它染与u不同的色 如果矛盾就说明不是二分图
        // 若顶点v染过色 看它与u的颜色是否相同来判断是否有矛盾
        if (!colors[v] && !dfs(v, 3 - c) || colors[v] == c) return false;
    }
    return true;
}

for (int i = 1; i <= n; ++i) {
    if (!colors[i]) {
        // 尝试给每个节点染色
        if (!dfs(i, 1)) // 该图不是二分图
    }
}
// 该图是二分图

匈牙利算法求二分图最大匹配

时间复杂度: O(NM)O(NM) (实际运行时间一般远小于 O(NM)O(NM))(NN 表示顶点数,MM 表示边数)

模板代码:

int n1, n2, idx; // n1 n2 分别表示二分图的两部分的顶点数
int matchs[N];
bool vis[N];

bool find(int u) {
    for (int i = heads[u]; i != -1; i = nexts[i]) {
        int v = vals[i];
        if (!vis[v]) {
            vis[v] = true;
            if (!matchs[v] || find(matchs[v])) {
                matchs[v] = u;
                return true;
            }
        }
    }
    return false;
}

int ans = 0; // 记录最大匹配
for (int i = 1; i <= n1; ++i) {
    memset(vis, false, sizeof(vis)); // 重置vis
    if (find(i)) ++ans;
}

数学

算术基本定理

质因数分解式:n=i=1kpiαi=p1α1×p2α2××pkαk,p1<p2<<pkn = \prod_{i=1}^k{p_i^{\alpha_i}} = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}, \,\,\,\,\, p_1 < p_2 < \cdots < p_k

质数

试除法判质数

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

时间复杂度:O(n)O(\sqrt{n})

试除法分解质因数

模板题:【数学】分解质因数

void pf(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            printf("%d %d\n", i, s);
        }
    }
    if (n > 1) printf("%d 1\n", n);
}

时间复杂度:O(logNn)O(\log{N} \sim \sqrt{n})

筛质数

模板题:【数学】筛质数

朴素筛
int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) primes[cnt++] = i;
        for (int j = i + i; j <= n; j += i) isNotPrime[j] = true;
    }
    return cnt;
}

时间复杂度:O(NlogN)O(N\log{N})

埃氏筛
int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            primes[cnt++] = i;
            for (int j = i + i; j <= n; j += i) isNotPrime[j] = true;
        }
    }
    return cnt;
}

时间复杂度:O(NloglogN)O(N\log\log{N})

线性筛
int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; ++j) {
            isNotPrime[primes[j] * i] = true;
            if (primes[j] % i == 0) break;
        }
    }
    return cnt;
}

时间复杂度:O(N)O(N)

约数

试除法求所有约数

set<int> get_divisors(int n) {
    set<int> divisors;
    for (int i = 1; i <= n / i; ++i) {
        if (n % i == 0) {
            divisors.insert(i);
            divisors.insert(n / i);
        }
    }
    return divisors;
}

时间复杂度:O(n)O(\sqrt{n})

约数个数

模板题:【数学】约数个数

算术基本定理可得:nn 的约数个数为:f(n)=i=1k(αi+1)=(α1+1)(α2+1)(αk+1)f(n) = \prod_{i=1}^{k}{(\alpha_i + 1)} = (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)

// 求一个数的约数个数
int count_divisors(int n) {
    int cnt = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
           	cnt *= s + 1;
        }
    }
    if (n > 1) cnt *= 2;
    return cnt;
}

约数之和

模板题:【数学】约数之和

算术基本定理可得:nn 的约数个数为:

σ(n)=(p10+p11+p12++p1α1)(p20+p21+p22++p2α2)(pk0+pk1+pk12++pkαk)\sigma(n) = (p_1^0+p_1^1+p_1^2+ \cdots + p_1^{\alpha_1})(p_2^0+p_2^1+p_2^2+ \cdots + p_2^{\alpha_2}) \cdots (p_k^0+p_k^1+p_k1^2+ \cdots + p_k^{\alpha_k})

// 求一个数的约数之和
int sum_divisors(int n) {
    int sum = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
			int tmp = 1;
            while (n % i == 0) {
                n /= i;
                tmp = i * tmp + 1;
            }
            sum *= tmp;
        }
    }
    if (n > 1) sum *= n + 1;
    return sum;
}

最大公约数

辗转相除法 + 递归

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

快速幂

详细介绍及原理:快速幂 - OI Wiki

long quickPow(long base, long expo) {
    long res = 1L;
    while (expo != 0) {
        if ((expo & 1) != 0) res *= base;
        base *= base;
        expo >>= 1;
    }
    return res;
}
typedef long long LL;

LL quick_pow(LL base, LL expo) {
    LL res = 1L;
    while (expo) {
        if (expo & 1) res *= base;
        base *= base;
        expo >>= 1;
    }
    return res;
}

向上取整

a 被除数,b 为除数,求 ab\lceil\frac{a}{b}\rceil

int result = (a + b - 1) / b

动态规划

0-1背包问题

模板

int n, c; // n物品数量 c背包容量
int v[N], w[N], dp[N][N]; // v物品体积 w物品价值

// 动态规划
for (int i = 1; i <= n; ++i) {
    int vi = v[i], wi = w[i];
    for (int j = 0; j <= c; ++j) {
        dp[i][j] = dp[i - 1][j];
        if (vi <= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - vi] + wi);
    }
}

dp[n][c]; // 结果

滚动数组优化

for (int i = 1; i <= n; ++i) {
    int vi = v[i], wi = w[i];
    for (int j = c; j >= vi; --j) {
        dp[j] = max(dp[j], dp[j - vi] + wi);
    }
}

dp[c]; // 结果

完全背包问题

模板

int n, c; // n物品数量 c背包容量
int v[N], w[N], dp[N][N]; // v物品体积 w物品价值

// 动态规划
for (int i = 1; i <= n; ++i) {
    int vi = v[i], wi = w[i];
    for (int j = 0; j <= c; ++j) {
        for (int k = 0; k * vi <= j; ++k) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * vi] + k * wi);
        }
    }
}

dp[n][c]; // 结果

滚动数组优化

for (int i = 1; i <= n; ++i) {
    const int& vi = v[i], & wi = w[i];
    for (int j = vi; j <= c; ++j) {
        dp[j] = max(dp[j], dp[j - vi] + wi);
    }
}

dp[c]; // 结果

多重背包问题

模板

int n, c; // n物品数量 c背包容量
int v[N], w[N], s[N], dp[N][N]; // v物品体积 w物品价值 s物品数量

// 动态规划
for (int i = 1; i <= n; ++i) {
    int vi = v[i], wi = w[i], si = s[i];
    for (int j = 0; j <= c; ++j) {
        for (int k = 0; k <= si && k * vi <= j; ++k) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * vi] + k * wi);
        }
    }
}

dp[n][c]; // 结果

优化

// L = N * logM + 2
int n, c; // n物品数量 c背包容量
int v[L], w[L], dp[M]; // v物品体积 w物品价值


int idx = 0;
// 输入
for (int i = 1; i <= n; ++i) {
    int vi, wi, si;
    scanf("%d%d%d", &vi, &wi, &si);
    int x = 1;
    while (x <= si) {
        ++idx;
        v[idx] = vi * x;
        w[idx] = wi * x;
        si -= x;
        x <<= 1;
    }
    if (si > 0) {
        ++idx;
        v[idx] = vi * si;
        w[idx] = wi * si;
    }
}
n = idx;

// 动态规划
for (int i = 1; i <= n; ++i) {
    int vi = v[i], wi = w[i];
    for (int j = c; j >= vi; --j) {
        dp[j] = max(dp[j], dp[j - vi] + wi);
    }
}

dp[c]; // 结果

分组背包问题

模板

int n, c; // n物品数量 c背包容量
int v[N][N], w[N][N], s[N], dp[N]; // v物品体积 w物品价值 s物品数量

// 动态规划
for (int i = 1; i <= n; ++i) {
    int si = s[i];
    for (int j = c; j >= 0; --j) {
        for (int k = 0; k < si; ++k) {
            if (v[i][k] <= j) dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
        }
    }
}

dp[c]; // 结果

最长上升子序列(LIS)

for (int i = 0; i < n; ++i) {
    dp[i] = 1;
    for (int j = 0; j < i; ++j) {
        if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
    }
}
int mx = 0;
for (int& x : dp) mx = max(mx, x);

mx; // LIS

优化

// 二分查找 找小于x的最大数
int bsearch_le(int l, int r, int x) {
    while (l < r) {
        int m = l + r >> 1;
        if (q[m] >= x) r = m;
        else l = m + 1;
    }
    return l - 1;
}

// 贪心
q[0] = -INF;
int max_len = 0;
for (int i = 0; i < n; ++i) {
    int len = bsearch_le(0, max_len + 1, a[i]);
    max_len = max(max_len, len + 1);
    q[len + 1] = a[i];
}

max_len; // LIS

最长相同子序列(LCS)

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
    }
}

dp[n][m]; // LCS
0

评论区