XCPC丨算法竞赛汇总

XCPC丨算法竞赛汇总

Conqueror712 Lv1
  2023-03-18 20:01:25 2023-03-18 20:01:25 创建   2024-02-22 19:29:23 2024-02-22 19:29:23 更新    

前言：

2023.03.18正式退役啦，特此来把之前杂乱无章且错误百出的，有关算法竞赛的博客整合起来，汇总成此篇博客。

（其实是我自己的板子，如果大家有需要就拿去就好啦，能帮到各位的话也算是一种传承吧）

个人博客：https://conqueror712.github.io/

Github：https://github.com/Conqueror712

掘金：https://juejin.cn/user/1297878069809725/posts

Algorithm Model Version 1.0 - 2023.03 —— by Conqueror712

Graph - Theory

Bellman-Ford

适用情况：单源最短路 + 可有负权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 时间复杂度：O(nm)
// vector邻接表写法
vector <PII> edge[N];
int shortestpath(int s, int t){
    memset(dist, 127, sizeof(dist));
    dist[s] = 0;
    while (1){
    // 在每次迭代中，遍历所有边，尝试用Relieve_Operation更新距离数组
        bool ok = false;
        for (int i = 1; i <= n; i++){
        	for (auto it : edge[i]){
	            int x = i; int y = it.fir; int v = it.sec;
	            if (dist[x] < (1 << 30)){
	                if (dist[x] + v < dist[y]){
	                    dist[y] = dist[x] + v; ok = true;
	                }
	            }
	        }
        }
        if (!ok){ break; }
    }
    return dist[t];
}

Dijkstra

适用情况：单源最短路 + 无负权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 堆优化Version 时间复杂度：O((n + m)logn)
// 用一个堆来维护dist数组，可以使用set，也可以使用priority_queue
vector <PII> edge[N];
set <pair<int, int>> q;
vector <PII> edge[N];
int n, m, dist[N];
int Dijkstra(int s, int t){
    memset(dist, 127, sizeof(dist));
    dist[s] = 0; q.clear();
    for (int i = 1;i <= n;i++){
        q.insert({dist[i], i});
    }
    while(!q.empty()){
        int x = q.begin()->sec;
        q.erase(q.begin());
        if (x == t || dist[x] > (1 << 30)){ break; }
        for (auto p : edge[x]){
            if (dist[x] + p.sec < dist[p.fir]){
                q.erase({dist[p.fir], p.fir});
                dist[p.fir] = dist[x] + p.sec;
                q.insert({dist[p.fir], p.fir});
            }
        }
    }
    return dist[t];
}

Floyd

适用情况：多源最短路 + 可有负权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 空间优化Version 时间复杂度：O(n^3) 空间复杂度：O(n^2) 
// 邻接矩阵写法
int a[1001][1001];
int v[1001][1001];
inline void Floyd(int n){
    memset(v, 127, sizeof(v));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            v[i][j] = a[i][j];
        }
    }
    for (int k = 1; k <= n; k++){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (v[i][k] < (1 << 30) && v[k][j] < (1 << 30)){
                    v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
                }
            }
        }
    }
    return;
}

Prim

适用场景：稠密图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 堆优化Version 时间复杂度：O((n+m)logn)
set <pair<int, int>> q;
vector <PII> edge[N];   // 边集
int n, m, dist[N];      // dist集
bool b[N];              // 存在性集
int Prim(){
    memset(b, false, sizeof(b));
    memset(dist, 127, sizeof(dist));
    dist[1] = 0;
    q.clear();
    for (int i = 1;i <= n;i++){
        q.insert({dist[i], i});
    }
    int ans = 0, tot = 0;
    while(!q.empty()){
        int x = q.begin()->sec;
        q.erase(q.begin());
        if (dist[x] > (1 << 30)){ break; }
        ++tot; ans += dist[x]; b[x] = true;
        for (auto i : edge[x]){
            if (!b[i.fir] && i.sec < dist[i.fir]){
                q.erase({dist[i.fir], i.fir});
                dist[i.fir] = i.sec;
                q.insert({dist[i.fir], i.fir});
            }
        }
    }
    if (tot != n){ return -1; }
    else{ return ans; }
}

Kruskal

适用场景：稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 时间复杂度：O(mlogn)
int n, m, fa[N];    // fa是并查集的代表
struct Node{
    int x, y, v;    // x, y代表这条边连接的两个点，v代表这条边的边权
    bool operator < (const Node &A) const{  // 重构 < 运算符
        return v < A.v;
    }
} a[M];
int FindSet(int i){
    if (i == fa[i]){ return i; }
    return fa[i] = FindSet(fa[i]);
}
int Kruskal(){
    for (int i = 1; i <= n; i++){
        fa[i] = i;  // 并查集初始化
    }
    sort(a + 1, a + m + 1); // 按边权排序
    int ans = 0; int cnt = n;
    for (int i = 1; i <= m; i++){
        int x = FindSet(a[i].x);
        int y = FindSet(a[i].y);
        if (x != y){
            fa[x] = y;
            ans += a[i].v;
            --cnt;
        }
        if (cnt == 1){ break; }
    }
    if (cnt != 1){ return -1;  /*多于一个连通块*/ }
    else{ return ans; }
}

TopoSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// STL写法 时间复杂度：O(n + m)
// 在进行TopoSort之前要先算好每个点的d，也就是入度
inline void TopoSort(){
    // 队列S
    queue <int> s, l;
    for (int i = 1; i <= n; i++){
        if (!d[i]){
            // 入度为0，加到S里面去
            s.push(i);
        }
    }
    // 当队列非空的时候
    while (s.size()){
        // 将x加入到L的队尾，并把x从S中删去
        int x = s.front();
        s.pop();
        l.push(x);
        // 遍历x的所有边，令y的入度--，再判断如果此时y的入度为0，加进队列
        for (auto y : edge[x]){
            if (--d[y] == 0){
                s.push(y);
            }
        }
    }
    // 判断L里面有多少个点
    if (int(l.size()) == n){
        cout << "No" << endl;  
        // q中记录了一个合法的拓扑序列
    }
    else{
        // 有环
        cout << "Yes" << endl;
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 字典序最小/最大的拓扑序 时间复杂度：O(nlogn + m)
inline void TopoSort(){
    // 优先队列S
    queue <int> l;
    priority_queue <int> s;
    for (int i = 1; i <= n; i++){
        if (!d[i]){
            // 入度为0，加到S里面去
            s.push(-i);
        }
    }
    // 当队列非空的时候
    while (s.size()){
        int x = -s.top();
        s.pop();
        l.push(x);
        // 遍历x的所有边，令y的入度--，再判断如果此时y的入度为0，加进队列
        for (auto y : edge[x]){
            if (--d[y] == 0){
                s.push(-y);
            }
        }
    }
    while (l.size()){
        cout << l.front() << " ";
        l.pop();
    }
    return;
}

Euler Road

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 有向图的欧拉路
// 此代码的假设是将图中所有的有向边改为无向边后，图中所有度非零的点是联通的
const int N = 10010, M = 10010;
vector <int> edge[N]; // 存边
// f[i]表示i里面0到f[i - 1]那些边已经走过了 下次要走f[i]了 防止重复枚举
// ind入度 outd出度 c用来记路径
int n, m, l, f[N], ind[N], outd[N], c[M];
void dfs(int x){
	while (f[x] < outd[x]){
		// 这条边要存在
		int y = edge[x][f[x]];
		f[x]++;
		dfs(y);
		c[++l] = y;
	}
}
inline void Euler(){
	// x是起点
	// y表示有多少个点的出度比入度大1
	// z是有多少点的出度不等于入度
	int x = 0, y = 0, z = 0;
	// 枚举每个点
	rep(i, 1, n){
		// y的情况
		if (ind[i] + 1 == outd[i]){
			// 可能是起点
			x = i, ++y;
		}
		// z的情况
		if (ind[i] != outd[i]){
			++z;
		}
	}
	if (!((y == 1 && z == 2) || !z)){
		// 没有欧拉路
		cout << "No" << endl;
		return;
	}
	// 起点还没找到 写!z也可以
	if (!x){
		rep(i, 1, n){
			if (ind[i]){
				x = i;
			}
		}
	}
	memset(f, 0, sizeof(f));
	l = 0;
	dfs(x);
	c[++l] = x;
	if (l == m + 1){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
	// per(i, l, 1){
	// 	cout << c[i] << " \n"[i == 1];
	// }
	return;
}
// -------------------------------
// 以下是main函数的一部分 记得更改d数组
rep(i, 1, m){
	char str[101];
	cin >> str;
	int x = str[0] - 'a' + 1, y = str[strlen(str) - 1] - 'a' + 1;
	edge[x].push_back(y);
	++outd[x];
	++ind[y];
}
Euler();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// 无向图的欧拉路
const int N = 10010, M = 10010;
// 存边 fir为去向 sec为idx
vector <PII> edge[N];
int n, m, l, cnt = 1, f[N], d[N], v[N], c[M];
bool b[2 * M];
void dfs(int x){
	while (f[x] < v[x]){
		// 这条边要存在
		int y = edge[x][f[x]].fir, idx = edge[x][f[x]].sec;
		if (!b[idx]){
			f[x]++;
			b[idx] = b[idx ^ 1] = true;
			dfs(y);
			c[++l] = y;
		}
		else{
			f[x]++;
		}
	}
}
inline void Euler(){
	int x = 0, y = 0;
	// 枚举每个点
	rep(i, 1, n){
		if (d[i] & 1){
			// 可能是起点
			x = i, ++y;
		}
	}
	if (y && y != 2){
		// 没有欧拉路
		cout << "No" << endl;
		return;
	}
	if (!x){
		rep(i, 1, n){
			if (d[i]){
				x = i;
			}
		}
	}
	memset(f, 0, sizeof(f));
	memset(b, false, sizeof(b));
	l = 0;
	dfs(x);
	c[++l] = x;
	if (l != m + 1){
		cout << "No" << endl;
		return;
	}
	cout << "Yes" << endl;
	per(i, l, 1){
		cout << c[i] << " \n"[i == 1];
	}
	return;
}
// ------------------------------
// 以下是main函数的一部分 记得更改d数组
rep(i, 1, m){
	int x, y;
	cin >> x >> y;
	edge[x].push_back({y, ++cnt});
	edge[y].push_back({x, ++cnt});
	++d[x];
	++d[y];
}
rep(i, 1, n){
	v[i] = edge[i].size();
}
Euler();

Bipartite Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 染色法判别二分图 时间复杂度：O(n + m)
const int N = 10010;
vector <int> edge[N];
// c数组存颜色 即color 1和2是不同的颜色 0代表还没染过色
int n, m, c[N];
bool dfs(int x){
	// 遍历x的边 然后递归下去就是遍历x的连通块
	for (auto y : edge[x]){
		if (!c[y]){
			// 还没染过色 染之
			c[y] = 3 - c[x];
			if (!dfs(y)){
				// 染不动了
				return false;
			}
		}
		else{
			if (c[x] == c[y]){
				return false;
			}
		}
	}
	return true;
}
bool check(){
	memset(c, 0, sizeof(c))
	rep(i, 1, n){
		if (!c[i]){
			c[i] = 1;
			if (!dfs(i)){
				return false;
			}
		}
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 求二分图最大匹配 时间复杂度：O(nm)
const int N = 10010;
// edge只记左边的点
vector <int> edge[N];
// v[i]表示有右边的第i个点 如果有匹配 匹配的是左边的哪个点 没有就为0
int n, m, n1, n2, v[N];
bool b[N];
bool Find(int x){
	b[x] = true;
	for (auto y : edge[x]){
		if (!v[y] || (!b[v[y]] && Find(v[y]))){
			v[y] = x;
			return true;
		}
	}
	return false;
}
int match(){
	int ans = 0;
	memset(v, 0, sizeof(v));
	rep(i, 1, n1){
		memset(b, false, sizeof(b));
		if (Find(i)){
			// dfs
			ans++;
		}
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
最大独立集
在图中选出最多的点，满足他们两两之间没有边相连。

最大独立集.size = n - 最大匹配数

最小点覆盖
在图中选出最少的点，使得每条边的两个端点中至少有一个在集合里

最小点覆盖.size = 最大匹配数

Data - Structure

Chain - Table：Skipped, I don’t like it.

Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 数组实现队列的简单操作
int q[100010];
int front = 1, rear = 0;
void Push(int x){
    q[++rear] = x;
}
void Pop(){
    ++front;
}
int Query(int k){  // 询问第k个元素
    // 如何判断队列里有几个元素？ rear - front + 1即可
    return q[front + k - 1];
}
int Top(){
    return q[front];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 数组实现循环队列
// 有些时候 入队出队次数 远远大于 队伍的元素个数，那么开很大的数组就浪费空间了
// 于是我们就让 当队尾指针移动到数组末端时，再将其移动到数组头即可，反之亦然
const int size = 1010;            // size要严格大于队列最长的时候的长度
int q[size];
int front = 1, rear = size;
void Push(int x){
    rear = rear % size + 1;
    q[rear] = x;
    return;
}
void Pop(){
    front = front % size + 1;
    return;
}
bool Empty(){
    return rear % size + 1 == front;
}
int Query(int x){
    if (front + x - 1 <= size){
        return q[front + x - 1];
    }
    else{
        return q[front + x - 1 - size];
    }
}

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 栈的数组实现
int s[100010];  // 创建栈
int top = 0;  // 创建头指针，一开始在底部
void Push(int x){
    s[++top] = x;        //先移动top 再赋值
}
void Pop(){
    if (top == 0){
        return;
    }
    else{
        --top;
    }
}
int Top(){
    if (top == 0){
        return -1;
    }
    else{
        return s[top];
    }
}
int Query(int k){  // 查询从栈顶往下数第k个元素是多少
    return s[top+1-k];
}

Binary - Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
// 指针建立二叉树
struct TreeNode{
    int val;
    TreeNode *l, *r, *fa;
} a[100010];
// 插入子节点
void Insert(TreeNode *fa, TreeNode *p, int flag){
    // flag = 0 插入到左边 flag = 1 插入到右边
    if (!flag){ fa->l = p; }
    else{ fa->r = p; }
    p->fa = fa;
}
void PreOrder(TreeNode *p){
    cout << p->val << " ";
    if (p->l) PreOrder(p->l);
    if (p->r) PreOrder(p->r);
}
void InOrder(TreeNode *p){
    if (p->l) InOrder(p->l);
    cout << p->val << " ";
    if (p->r) InOrder(p->r);
}
void PostOrder(TreeNode *p){
    if (p->l) PostOrder(p->l);
    if (p->r) PostOrder(p->r);
    cout << p->val << " ";
}
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        int l, r; cin >> l >> r; a[i].val = i;
        if (l != 0){ a[i].l = &a[l]; a[l].fa = &a[i]; }
        if (r != 0){ a[i].r = &a[r]; a[r].fa = &a[i]; }
    }
    PreOrder(&a[1]); cout << endl;
    InOrder(&a[1]); cout << endl;
    PostOrder(&a[1]); cout << endl;
    return 0;
}
/*
4
2 3
0 0
4 0
0 0
*/

Heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 堆的数组实现
const int Maxsize = 10010;
int len = 0;    // 记录当前size
// int heap[Maxsize]; 这是数组实现 我们选择vector
vector <int> heap;
// 每一次插入新的数据，都要和它的父节点比一比（判别依据是根据本来是大根堆||小根堆）
// 以小根堆举例，插入的复杂度为O(logn)
void Up(int k){
    while(k > 1 && heap[k] < heap[k / 2]){
        swap(heap[k], heap[k / 2]);
        k /= 2;
    }
}
void Insert(int x){
    heap[++len] = x;
    Up(len);
}
// 堆最常用的功能就是维护min||max
// 以小根堆为例，我们常常会求得最小的数字，然后让它出堆；
// 这时候我们就要从堆中删除堆顶元素。
// 由于这时除了堆顶为空，它的左右子树堆仍然满足堆结构。
// 为了操作简单，我们将堆尾元素放到堆顶，然后再将其"逐 步 下 移"
void Down(int k){
    while(k + k <= len){
        int j = k + k;
        if (j + 1 <= len && heap[j + 1] < heap[j]){
            j++;
        }
        if (heap[k] <= heap[j]){
            break;
        }
        swap(heap[k], heap[j]);
        k = j;
    }
}
void Pop(){
    swap(heap[1], heap[len]);
    len--;
    Down(1);
}
// 删除堆中任意一个元素
void Delete(int p){
    if (p == len){
        heap[len] = 0;
        len--;
        return;
    }
    int x = heap[p];
    int y = heap[len];
    swap(heap[p],heap[len]);
    len--;
    if (y < x){
        Up(p);
    }
    else{
        Down(p);
    }
}
1
2
3
4
5
6
7
// STL - Heap
// 大根堆：
priority_queue<int> q;
priority_queue<int, vector<int>,less<int>> q;
// 小根堆：
priority_queue<int, vector<int>,greater<int>> q;
// 基本操作：empty size top push pop...(没有clear)

Hash

1
2
// 一般的情况就用unordered_map来做就可以了，如果被卡了就换成map
// 如果需要解决值冲突，需要二次哈希甚至三次哈希，那么就需要用正经的哈希函数来搞了，我暂时用不到，故暂略之

Monotone - Stack and Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// PS: 用的不是很好
// 单调栈模板
// 从下往上元素单调递减
rep(i, 1, n){
	while (/* 栈非空 && 栈顶元素 < a[i] */){
		// 栈顶元素所在位置答案为i
		// 弹出栈顶元素
	}
	// 将a[i]入栈 并记录其位置
}	// 清空栈 栈中元素所在位置答案为0
// ---------------------------------------
// 单调队列模板
rep(i, 1, n){
	while (/*队列非空 && 队尾元素 <= a[i]*/){
		// 弹出队尾元素
	}
	// 将a[i]加入队尾
	// 如果队首元素已经"过气"，将其出队
	// 队首为当前区间的答案
}

Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// PS：用的不是很好
const int N = 100010;
VI edges[N];
// 数组里面的每一个元素都是一个vector，就是用vector来存树，当然也可以用链表来存
// edges[i]（这是个vector）就代表第i个点的所有子节点的下标
int n, fa[N];// n代表树里面有多少个节点，fa[]代表节点的父节点编号
void addEdge(int x, int y){
    edges[x].pb(y);// 给x节点添加一个儿子y
    fa[y] = x;// 更新y的父节点信息（对于有根树而言）
    return;
}
void PrintSon(int x){
    // 遍历x的所有儿子
    for (auto i : edges[x]){
        cout << edges[x][i] << " ";
    }
    return;
}
VI dfn;// 有根树的DFS序
void DFS(int x){
    dfn.pb(x);
    for (/*x的所有儿子y*/){
        DFS(y);
    }
    return;
}
// 有根树的BFS序 q中出现的元素顺序即BFS序
void BFS(int root){
    // 将root加入队列q
    while(!q.empty()){
        // x = q队首元素;
        // x出队;
        for (/*x的所有儿子y*/){
            // y入队;
        }
    }
    return;
}

Trie Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int N = 500010;
const int charsize = 26;    // 字符集大小
int nxt[N][charsize];   // 记录此节点的子节点编号（默认全是小写字母）
bool isEnd[N];  // 表示此编号节点是否为终止节点
int root = 0;
int cnt = 0;    // 表示当前的节点编号数
inline void insert(string s, int len){  // s为等待插入的字符串，0_base，len为字符串长度
    int now = 0;    // 当前在哪个节点上
    for (int i = 0; i < len; i++){   // 遍历
        int x = s[i] - 'a';     // 转成数字
        if (!nxt[now][x]){     // 如果当前节点没有子节点x，则创建之，并且给予编号
            nxt[now][x] = ++cnt;
        }
        now = nxt[now][x];     // 无论创建了新节点与否，都更新当前节点的位置
    }
    isEnd[now] = true;          // 最后的最后，把该字符串的最后一个字符的isEnd标记为true
    return;
}
// s为等待插入的字符串，0_base，len为字符串长度
inline bool search(string s, int len){
    int now = 0;    //和上面一样，记录当前在看的节点
    for (int i = 0; i < len; i++){  //遍历之
        int x = s[i] - 'a';     //转成数字
        if (!nxt[now][x]){ return false; }//如果当前节点没有子节点x，则直接返回false
        now = nxt[now][x];     //如果没有return则更新当前节点位置，继续循环
    }
    return isEnd[now];          //最后进行判断最后一个字符是否是结束位置，返回即可
}
// 字典树的删除比较罕见 暂略
/*字符集较大的时候请使用哈希
struct TreeNode{
    unordered_map <char, int> nxt;
    bool isEnd;
} tree[N];*/
int main(){
    // 例题描述：n个字符串s1~sn和m组询问，每次询问一个字符串是否在s1~sn中出现过，有1，无0
    ios;
    int n, m;
    string s;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s;
        int len = s.size();
        insert(s, len);
    }
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> s;
        int len = s.size();
        cout << search(s, len) << endl;
    }
    return 0;
}

Union - Find - Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 一开始有n个元素，互相独立，则构成了n个集合，每个集合的代表元素就是它本身
const int maxn = 100010;
int fa[maxn + 1];   // fa数组记录每个元素由谁代表
int sz[maxn + 1];   // sz数组记录每个集合的元素个数
int dep[maxn + 1];  // dep数组记录每个集合的树深度
inline void Initialize(int n){
    for (int i = 1;i <= n;i++){ // 一共有n个点
        fa[i] = i;              // 把代表元素设置为自己
        sz[i] = dep[i] = 1;     // 一开始的深度就是1，子树大小也是1，因为只有自己孤零零的一个元素
    }
}
int Findset(int x){
    if (x == fa[x]){    //如果就是代表元素就直接返回咯
        return x;
    }
    fa[x] = Findset(fa[x]);      //在不是的情况下每一次都设置一遍
    return fa[x];
}
void Union(int x, int y){	// 启发式合并O(logn)
    int fx = Findset(x);
    int fy = Findset(y);
    if (fx == fy){ return; }
    if (sz[fx] > sz[fy]){ swap(fx, fy); } 	// 确定谁是骡子谁是马
    fa[fx] = fy; sz[fy] += sz[fx];   		//子树的大小也要加起来
}

Segment Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*线段树和树状数组在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树. 树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决。于是我们这里暂时就学线段树就可以了。*/
const int N = 500010;
// f[i]记录的是编号为i的节点 记录的区间和
// v[i]记录的是编号为i的节点 整体要加上v[i]
int n, m, f[4 * N], a[N];
void BuildTree(int k, int l, int r){
	//k是编号 l r是左端点和右端点
	if (l == r){
		//走到叶子节点了，走不动了
		f[k] = a[l];	//f[k] = a[r]当然也可以，无所谓
		return;
	}
	int mid = (l + r) / 2;	//这里可以用(l + r) >> 1，也是除以2的意思
	//获得了当前区间的中点，开始分割递归
	BuildTree(k + k, l, mid);
	BuildTree(k + k + 1, mid + 1, r);
	f[k] = f[k + k] + f[k + k + 1];
	//这里是用到了完全二叉树的节点编号的性质，父节点为k，则两个子节点分别为k + k和k + k + 1
	return;	//整棵树就建好了
}
void Add(int k, int l, int r, int x, int val){
	//k是编号
	//递归的去从根节点开始加val，一直加到点x上
	f[k] += val;
	if (l == r){ return; }
	int mid = (l + r) >> 1;
	if (x <= mid){
		//如果x在mid的左边，也就是说要往左子树递归
		Add(k + k, l, mid, x, val);
	}
	else{
		//如果x在mid的右边，也就是说要往右子树递归
		Add(k + k + 1, mid + 1, r, x, val);
	}
}
int calc(int k, int l, int r, int s, int t){
	//编号为k的点对应的区间是l~r，s~t是其子区间
	if (l == s && r == t){ return f[k]; }
	int mid = (l + r) >> 1;
	if (t <= mid){
		//如果s~t完全位于左区间
		return calc(k + k, l, mid, s, t);
	}
	else if (s > mid){
		//如果s~t完全位于右区间
		return calc(k + k + 1, mid + 1, r, s, t);
	}
	else{
		//如果s~t横跨两边，加起来即可
		return calc(k + k, l, mid, s, mid) + calc(k + k + 1, mid + 1, r, mid + 1, t);
	}
}
int main(){
	ios;
	// m次操作
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	// 递归建树
	BuildTree(1, 1, n);
	for (int i = 1; i <= m; i++){
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1){	// 操作1：第x个数加上y
			Add(1, 1, n, x, y);
		}
		else{			// 操作2：查询区间x~y的区间和
			cout << calc(1, 1, n, x, y) << endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 带标记的线段树
// 上面一部分 + 下面一部分
const int N = 500010;
ll n, m, a[N], f[4 * N], v[N]; //f[i]记录的是编号为i的节点记录的区间和
inline void BuildTree(int k, int l, int r){
	//k是编号 l r是左端点和右端点
	if (l == r){
		//走到叶子节点了，走不动了
		f[k] = a[l];	//f[k] = a[r]当然也可以，无所谓
		return;
	}
	int mid = (l + r) >> 1;	//这里可以用(l + r) >> 1，也是除以2的意思
	//获得了当前区间的中点，开始分割递归
	BuildTree(k + k, l, mid);
	BuildTree(k + k + 1, mid + 1, r);
	f[k] = f[k + k] + f[k + k + 1];
	//这里是用到了完全二叉树的节点编号的性质，父节点为k，则两个子节点分别为k + k和k + k + 1
	//整棵树就建好了
}
inline void Insert(int k, int l, int r, int x, int y, ll z){
	if (l == x && r == y){
		v[k] += z;	// 这里的f不用改，因为只考虑其子树下面的和
		return;
	}
	f[k] += (y - x + 1) * z;
	int mid = (l + r) >> 1;
	if (y <= mid){
		Insert(k + k, l, mid, x, y, z);
	}
	else {
		if (x > mid){
			Insert(k + k + 1, mid + 1, r, x, y, z);
		}
		else{
			Insert(k + k, l, mid, x, mid, z);
			Insert(k + k + 1, mid + 1, r, mid + 1, y, z);
		}
	}
}
ll calc(int k, int l, int r, int x, int y, ll p){
	//编号为k的点对应的区间是l~r x~y是其子区间 p是根到当前的点的v的和
	p += v[k];
	if (l == x && r == y){
		return p * (r - l + 1) + f[k];
	}
	int mid = (l + r) >> 1;
	if (y <= mid){
		//如果完全位于左区间
		return calc(k + k, l, mid, x, y, p);
	}
	else{
		if (x > mid){
			//如果完全位于右区间
			return calc(k + k + 1, mid + 1, r, x, y, p);
		}
		else{
			//如果横跨两边，加起来即可
			return calc(k + k, l, mid, x, mid, p) + calc(k + k + 1, mid + 1, r, mid + 1, y, p);
		}
	}
}
int main(){
	ios;
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	//递归建树
	BuildTree(1, 1, n);
	for (int i = 1; i <= m; i++){
		int op, x, y; ll k;
		cin >> op;
		if (op == 1){	//操作1：x~y的区间都加上k
			cin >> x >> y >> k;
			Insert(1, 1, n, x, y, k);
		}
		else{			//操作2：查询区间x~y的区间和
			cin >> x >> y;
			cout << calc(1, 1, n, x, y, 0) << endl;
		}
	}
	return 0;
}

Number - Theory

Exact - Division & gcd & lcm

1
2
3
4
5
6
7
8
9
int gcd(int a, int b){ return b ? gcd(b, a % b) : a;}
int lcm(int a, int b){ return (a / gcd(a, b)) * b;}

int exgcd(int a, int b, int &x, int &y){
    if (b == 0){ x = 1, y = 0; return a; }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

Prime Sieve & Block - By - Block

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 试除法分解质因数
void Divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0){
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
// 试除法求所有约数
vector <int> get_divisors(int x){
    vector <int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0){
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}
// 线性筛
const int N = 100010;
int primes[N], cnt;     // primes[]存储所有素数 0_base
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[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
    return;
}

Coresidual & Euler Func & Inverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//给一个素数p 求1∼n关于p的逆元 (有四种求逆元的方法)
const int N = 10100000;
long long inv[N];
int n, p, ans = 1;
int main(){
    cin >> p >> n; inv[1] = 1;
    for (int i = 2; i <= n; i++){
        inv[i] = (p - p / i) * inv[p % i] % p;
        ans ^= inv[i];  // 由于输出可能很大 只需要求这些逆元的异或和即可
    }
    cout << ans << endl;
    return 0;
}
// 求欧拉函数
inline int phi(int x){
    int res = x;
    for (int i = 2; i <= x / i; i ++ ){
        if (x % i == 0){
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

Qmi & Conbinatorial Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 快速幂：求a^k%mod 时间复杂度O(logk)
const int mod = 998244353;
inline int qmi(int a, int k){
    a %= mod; int res = 1;
    while (k){
        if (k & 1) { res = res * a % mod; }
        a = a * a % mod; k >>= 1;
    }
    return res;
}
// 快速乘
const int mod = 1e9+7;
ll quickmul(ll a, ll b, ll mod){
    ll ans = 0; a %= mod;
    for (; b; b >>= 1){
        if (b & 1){ ans += a; ans %= mod; }
        a += a; a %= mod;
    }
    return ans;
}
// 矩阵乘法
//优化的 O(n^3 log k) 但是常数小了很多
void aa(){
    ll w[N][N];
    memset(w, 0, sizeof(w));
    for (int i = 1; i <= n; i++){
        for (int k = 1; j <= n; j++){
            if (a[i][k]){
                for (int j = 1; j <= n; j++){
                    if (a[k][j]){
                        w[i][j] += a[i][k] * a[k][j]; w[i][j] %= P;
                    }
                }
            }
        }
    }
    memcpy(a, w, sizeof(a));
    return;
}
1
2
3
4
5
6
// 排列数
int A(int n, int m) {
    int res = 1;
    for (int i = m; i >= 1; i--) { res *= n; n--; }
    return res;
}

四种求组合数的方式：

1
2
3
4
5
6
// 普通组合数 N^2：
// c[a][b] 表示从a个中选b个的方案数
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]) % mod;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 通过预处理逆元的方式求组合数：
// 首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
// 如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p){
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ ){
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Lucas定理：
// 若p是质数，则对于任意整数 1 <= m <= n，有：
// C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int qmi(int a, int k, int p){
    int res = 1 % p;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int C(int a, int b, int p) /* 通过定理求组合数C(a, b)*/ {
    if (a < b) return 0;
    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ ){
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }
    return x * (LL)qmi(y, p - 2, p) % p;
}
int lucas(LL a, LL b, int p){
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 分解质因数法求组合数：
/* 当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘 */

int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
bool st[N];     // 存储每个数是否已被筛掉
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[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int get(int n, int p)/*求n！中的次数*/{
    int res = 0;
    while (n){
        res += n / p;
        n /= p;
    }
    return res;
}
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;
    }
    return c;
}
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 ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

Gaussian Elimination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// a[N][N]是增广矩阵
int gauss(){
    int c, r;
    for (c = 0, r = 0; c < n; c ++ ){
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if (fabs(a[t][c]) < eps) continue;
        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];
        r ++ ;
    }
    if (r < n){
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

Chinese Remainder Theorem

1
2
3
4
5
6
7
8
9
10
11
// 中国剩余定理可求解一元线性同余方程组
ll CRT(int k, ll* a, ll* r) {
    ll n = 1, ans = 0;
    for (int i = 1; i <= k; i++) n = n * r[i];
    for (int i = 1; i <= k; i++) {
        ll m = n / r[i], b, y;
        exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n;
    }
    return (ans % n + n) % n;
}

Other Algorithm

BFS & DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// BFS
int BFS(){
    queue<int> q;
    st[1] = true; // 表示1号点已经被遍历过
    q.push(1);
    while (q.size()){
        int t = q.front();
        q.pop();
        for (/*遍历所有当前点的相邻位置*/){
            // 用变量xxx表示新的点
            if (!st[/*xxx*/]){
                st[/*xxx*/] = true; // 表示点j已经被遍历过
                q.push(/*xxx*/);
            }
        }
    }
}
// DFS
int DFS(int u){
    st[u] = true; // st[u] 表示点u已经被遍历过
    for (/*遍历所有当前点的相邻位置*/){
        // 用变量xxx表示新的点
        if (!st[/*xxx*/]) {
            DFS(/*xxx*/);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 整数二分：
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;
}

String

KMP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
// 求模式串的Next数组：
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){
        j = ne[j];
        // 匹配成功后的逻辑...
    }
}

字串Substr：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
    string str = "HelloWorld";
    // substr(l, len) = [l, len)
    rep(i, 0, 9){
        cout << str.substr(0, i) << endl;
    }
    cout << endl;
    rep(i, 0, 9){
    	cout << str.substr(9 - i, i) << endl;
    }
    cout << endl;
    // substr(l) = [l, end]
    rep(i, 0, 9){
        cout << str.substr(i) << endl;;
    }
    return 0;
}

Discretization & Prefix sum & Difference

高维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
for(int i=1;i<=n;++i)//先求数组a关于第一个维度的前缀和{
    for(int j=1;j<=m;++j){
        a[i][j]=a[i][j]+a[i][j-1];
    }
} 
for(int i=1;i<=n;++i){
    //在已经求完一个维度前缀和的基础上求数组a关于第二个维度的前缀和
    for(int j=1;j<=m;++j){
        a[i][j]=a[i][j]+a[i-1][j];
    }
}
/*
这种方式可以理解成二维前缀和是数组在求完关于第一个维度的前缀和，
然后再for一遍求它关于第二个维度的前缀和。
然后它在求三维以上前缀和的时候，就体现出这种写法在高维前缀和上的优越性了。
*/
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        for(int k=1;k<=p;++k){
            a[i][j][k]+=a[i-1][j][k];
        }
    }
}
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        for(int k=1;k<=p;++k){
            a[i][j][k]+=a[i][j-1][k];
        }
    }
}
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        for(int k=1;k<=p;++k){
            a[i][j][k]+=a[i][j][k-1];
        }
    }
} // 无需借助容斥原理，求高维前缀和的复杂度变为O(|高维空间容量|*k)，可以处理k稍大一些的情况。

差分：

1
2
3
4
5
void insert(int l, int r, int c){
    b[l] += c; b[r+1] -= c;
}
// 二维
a[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];	//子矩形加

Double Pointer

1
2
3
4
5
6
7
for (int i = 0, j = 0; i < n; i ++ ){
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}
/* 常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 */

High Precision

高精度加：（没搞懂怎么用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ){
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}

高精度减：（也没搞懂）

1
2
3
4
5
6
7
8
9
10
11
12
13
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    for (int i = 0, t = 0; i < int(A.size()); i ++ ){
        t = A[i] - t;
        if (i < int(B.size())) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (int(C.size()) > 1 && C.back() == 0) C.pop_back();
    return C;
}

Bit Operation

1
2
// 返回x的最后一位1以及以后
inline int lowbit(int x) {return x & -x; }

Quick Readin

1
2
3
4
5
6
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0'; ch=getchar();}
    return x*f;
}

Game Theory

1
2
3
4
5
6
7
8
9
10
11
12
（更多是在平等博弈下讨论的）
假设我们的游戏是**无环的**，即*不会存在能回到原来的状态从而无限进行下去的可能*；
则该游戏存在的所有状态构成一个**有向无环图**；
*注：以下都是基于Alice和Bob轮流进行游戏的情况下*
**先手必胜态**和**先手必败态**都是指的当前局面下，下一步谁来走，而不是整局游戏的先手。
必胜态触发的两种情况：（对必败态同理）
1. 达到终止条件（胜利条件）
2. 存在一个后继为必败态（随着后续的步骤会转变到必败态）
如果存在平局的情况，那么我们可以采用：胜1平0负-1的状态表示方式，此时我们的dp方程就是min(后继)；
不难想到，无论是平等博弈还是不平等博弈，我们都可以从**终点开始枚举**所有的状态，利用**动态规划**的思想。
那么，什么情况下不能dp呢？
就是当游戏局面很多的时候，没有办法把所有的状态都记下来的时候，就需要用到博弈论的手法了。

Team Mo

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void move(int pos, int sign) { /*update nowAns*/ }
inline void solve() {
	BLOCK_SIZE = int(ceil(pow(n, 0.5)));
	sort(querys, querys + m);
	for (int i = 0; i < m; ++i) {
	    const query &q = querys[i];
	    while (l > q.l) move(--l, 1);
	    while (r < q.r) move(r++, 1);
	    while (l < q.l) move(l++, -1);
	    while (r > q.r) move(--r, -1);
	    ans[q.id] = nowAns;
  	}
}

Computation Geometry

  • 精度：减少正反三角函数、除法、根号的使用次数。
  • 简洁：多归纳，多模块化，少分类讨论。
  • 除零： 所有除法都要考虑0
1
2
3
a = b → abs(a − b) < eps
a < b → a < b − eps
a > b → a > b + eps
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 判断两线段是否相交
// 注意：如果有#include <math.h>则需要注意y1, y2等变量需要放进局部变量而非全局变量，因为math.h中有同名函数。
struct Line {
    double x1;
    double y1;
    double x2;
    double y2;
};
 
bool intersection(const Line &l1, const Line &l2){
    //快速排斥实验
    if ((l1.x1 > l1.x2 ? l1.x1 : l1.x2) < (l2.x1 < l2.x2 ? l2.x1 : l2.x2) ||
        (l1.y1 > l1.y2 ? l1.y1 : l1.y2) < (l2.y1 < l2.y2 ? l2.y1 : l2.y2) ||
        (l2.x1 > l2.x2 ? l2.x1 : l2.x2) < (l1.x1 < l1.x2 ? l1.x1 : l1.x2) ||
        (l2.y1 > l2.y2 ? l2.y1 : l2.y2) < (l1.y1 < l1.y2 ? l1.y1 : l1.y2)){
        return false;
    }
    //跨立实验
    if ((((l1.x1 - l2.x1)*(l2.y2 - l2.y1) - (l1.y1 - l2.y1)*(l2.x2 - l2.x1))*
        ((l1.x2 - l2.x1)*(l2.y2 - l2.y1) - (l1.y2 - l2.y1)*(l2.x2 - l2.x1))) > 0 ||
        (((l2.x1 - l1.x1)*(l1.y2 - l1.y1) - (l2.y1 - l1.y1)*(l1.x2 - l1.x1))*
        ((l2.x2 - l1.x1)*(l1.y2 - l1.y1) - (l2.y2 - l1.y1)*(l1.x2 - l1.x1))) > 0){
        return false;
    }
    return true;
}

偷的板子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
const double pi = acos(-1.0);  //π
const double eps = 1e-8;       //精度控制
const double inf = 1e100;      //无穷大
int sgn(double s)              //判断浮点数的符号
{
    if (fabs(s) < eps) return 0;
    if (s > 0) return 1;
    return -1;
}
int cmp(double x, double y)  //判断x和y的大小关系,-1表示x<y
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}
double r2d(double rad)  //弧度转角度
{
    return rad / pi * 180.0;
}
double d2r(double degree)  //角度转弧度
{
    return degree / 180.0 * pi;
}
struct Point  //点与向量
{
public:
    double x, y;
    Point(double a = 0, double b = 0)
        : x(a), y(b) {}
    void input()  //输入
    {
        scanf("%lf%lf", &x, &y);
    }
    void debug()  //输出
    {
        printf("(%lf,%lf)\n", x, y);
    }
    Point operator+(Point b)  //向量相加
    {
        return Point(x + b.x, y + b.y);
    }
    Point operator-(Point b)  //向量相减
    {
        return Point(x - b.x, y - b.y);
    }
    Point operator*(double b)  //向量数乘
    {
        return Point(x * b, y * b);
    }
    double operator*(Point b)  //向量内积
    {
        return x * b.x + y * b.y;
    }
    Point operator/(double b)  //除法
    {
        return Point(x / b, y / b);
    }
    bool operator<(const Point& b)  //大小比较
    {
        if (cmp(x, b.x) == 0) return y < b.y;
        return x < b.x;
    }
    bool operator==(const Point& b)  //判等
    {
        return cmp(x, b.x) == 0 && cmp(y, b.y) == 0;
    }
    double cross(Point b) const  //向量叉乘
    {
        return x * b.y - y * b.x;
    }
    double angle()  //极角,弧度(-pi, pi]
    {
        return atan2(y, x);
    }
    double length()  //模
    {
        return sqrt((*this) * (*this));
    }
    double length2()
    {
        return (*this) * (*this);
    }
    double angleTo(Point b)  //向量角度,弧度
    {
        return acos(((*this) * b) / length() / b.length());
    }
    double angleTo(Point a, Point b)  //从该点看其它两点的角度,弧度
    {
        return Point(a - *this).angleTo(b - *this);
    }
    double area(Point a, Point b)  //求三点组成平行四边形有向面积
    {
        return (a - *this).cross(b - *this);
    }
    double dist(Point b)  //求两点间欧式距离
    {
        return (*this - b).length();
    }
    double dist2(Point b)
    {
        return (*this - b).length2();
    }
    double manhattanDis(Point b)  //求两点间曼哈顿距离
    {
        return fabs(x - b.x) + fabs(y - b.y);
    }
    Point rotate(Point p, double ang)  //绕点p逆时针旋转ang弧度,不修改本身的值
    {
        Point v = (*this) - p;
        double c = cos(ang), s = sin(ang);
        return p + Point(v.x * c - v.y * s, v.x * s + v.y * c);
    }
    Point rotate(double ang)  //直接逆时针旋转ang弧度
    {
        return rotate(Point(0, 0), ang);
    }
    Point rotLeft()  //左转90
    {
        return Point(-y, x);
    }
    Point rotRight()  //右转90
    {
        return Point(y, -x);
    }
    Point regular()  //化为单位向量
    {
        return *this / length();
    }
    Point normal()  //左转90的单位法向量
    {
        return rotLeft().regular();
    }
    Point trunc(double r)  //化为长度为r的向量
    {
        return regular() * r;
    }
    bool parrelTo(Point b)  //向量平行
    {
        return sgn(cross(b)) == 0;
    }
    bool verticalTo(Point b)  //向量垂直
    {
        return sgn((*this) * b) == 0;
    }
};
typedef Point Vector;
int toLeftTest(Point from, Point to, Point test)  //测试test在不在from->to的左边,1在左边,-1在右边,0共线
{
    return sgn((to - from).cross(test - to));
}
struct Circle  //圆
{
    Point o;   //圆心
    double r;  //半径
    Circle(Point o = Point(), double r = 0.0)
        : o(o), r(r) {}

    void input()
    {
        scanf("%lf%lf%lf", &o.x, &o.y, &r);
    }
    void debug()
    {
        printf("(%lf,%lf,%lf)\n", o.x, o.y, r);
    }
    Circle invertToCicle(Point P, double R)  //外部反演点反演,反演为圆; p为反演中心,r为反演半径
    {
        Circle ans;
        double d1 = P.dist(o);
        ans.r = r / (d1 * d1 - r * r) * R * R;
        double d2 = R * R / (d1 - r) - ans.r;
        ans.o = P + (o - P) * (d2 / d1);
        return ans;
    }
};
struct Line
{
    Point pos;
    Vector to;
    Line(Point p = Point(), Vector t = Point())  //顶点和方向向量
        : pos(p), to(t)
    {
    }
    static Line tp(Point a, Point b)  //两点构造
    {
        return Line(a, b - a);
    }
    Line(double x1, double y1, double x2, double y2)  //两点构造
    {
        pos = Point(x1, y1), to = Point(x2, y2) - Point(x1, y1);
    }
    Point point(double s)  //获取某处的一个点
    {
        return pos + to * s;
    }
    double angle()  //获得直线倾角,[0,pi)
    {
        return acos(to.regular().x * sgn(to.regular().y));
    }
    int onLine(Point s)  //判断点与直线的位置关系0在直线外;1在直线上
    {
        return sgn(to.cross(s - pos)) == 0;
    }
    bool operator==(Line l)  //两条直线是否是同一条(重合)
    {
        return l.onLine(point(0)) && l.onLine(point(1));
    }
    bool operator!=(Line l)
    {
        return !((*this) == l);
    }
    bool parrelTo(Line l)  //直线平行
    {
        return to.parrelTo(l.to);
    }
    bool verticalTo(Line l)  //直线垂直
    {
        return to.verticalTo(l.to);
    }
    Point insWithLine(Line l)  //与另一条直线的交点
    {
        return point(l.to.cross(pos - l.pos) / to.cross(l.to));
    }
    double disToPoint(Point s)  //点到直线的距离
    {
        return fabs(to.cross(s - pos) / to.length());
    }
    Point projection(Point s)  //点在直线上的投影
    {
        return point((to * (s - pos)) / (to * to));
    }
    Circle invertToCircle(Point P, double R)  //直线外一点反演为圆
    {
        Line lp(P, to.rotLeft());
        Point ps = this->insWithLine(lp);
        Circle c;
        c.r = R * R / this->disToPoint(P) / 2.0;
        c.o = P + (ps - P).regular() * c.r;
        return c;
    }
};

double disToSegment(Point s, Point a, Point b)  //点到线段ab最短距离
{
    if (a == b) return (s - a).length();
    Vector v1 = b - a, v2 = s - a, v3 = s - b;
    if (sgn(v1 * v2) < 0) return v2.length();
    if (sgn(v1 * v3) > 0) return v3.length();
    return Line(a, b - a).disToPoint(s);
}
double area(Point a, Point b, Point c)  //三角形面积
{
    return fabs((b - a).cross(c - a) / 2);
}
bool onSegment(Point p, Point a, Point b)  //点是否在线段上
{
    return (sgn((a - p).cross(b - p)) == 0 && sgn((a - p) * (b - p)) < 0) || p == a || p == b;
}
int insWithSegment(Line l, Point a, Point b, Point& ans)  //直线与线段相交
{
    if (l.parrelTo(Line(a, b - a))) return -1;  //不相交
    ans = l.insWithLine(Line(a, b - a));
    if (!onSegment(ans, a, b)) return -1;
    if (ans == a || ans == b) return 0;  //与端点相交
    return 1;                            //相交
}
bool segmentIns(Point a1, Point a2, Point b1, Point b2)  //判断线段是否相交
{
    double c1 = (a2 - a1).cross(b1 - a1), c2 = (a2 - a1).cross(b2 - a1);
    double c3 = (b2 - b1).cross(a1 - b1), c4 = (b2 - b1).cross(a2 - b1);
    if (!sgn(c1) || !sgn(c2) || !sgn(c3) || !sgn(c4)) {  //控制是否可以在顶点处相交
        bool f1 = onSegment(b1, a1, a2);
        bool f2 = onSegment(b2, a1, a2);
        bool f3 = onSegment(a1, b1, b2);
        bool f4 = onSegment(a2, b1, b2);
        bool f = (f1 | f2 | f3 | f4);
        return f;
    }
    return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0;
}
double polygonArea(Point* p, int n)  //计算多边形有向面积,点需要按顺序排列
{
    double s = 0;
    for (int i = 1; i < n - 1; i++) s += (p[i] - p[0]).cross(p[i + 1] - p[0]) / 2;
    return s;
}
double polygonPerimeter(Point* p, int n)  //计算多边形周长,点需要按顺序排列
{
    double ans = 0;
    p[n] = p[0];
    for (int i = 0; i < n; i++) ans += p[i].dist(p[i + 1]);
    return ans;
}
int quad(Point a)  // 判断象限的函数，每个象限包括半个坐标轴
{
    if (cmp(a.x, 0) > 0 && cmp(a.y, 0) >= 0) return 1;
    if (cmp(a.x, 0) <= 0 && cmp(a.y, 0) > 0) return 2;
    if (cmp(a.x, 0) < 0 && cmp(a.y, 0) <= 0) return 3;
    if (cmp(a.x, 0) >= 0 && cmp(a.y, 0) < 0) return 4;
}

void sortByPolarAngle(Point at, Point* begin, Point* end)  //极角逆时针排序，以at为极点
{
    sort(begin, end, [&](Point a, Point b) {
        a = a - at, b = b - at;
        int l1 = quad(a), l2 = quad(b);
        if (l1 == l2) {
            double c = a.cross(b);
            return cmp(c, 0) > 0 || (cmp(c, 0) == 0 && a.length() < b.length());
        }
        return l1 < l2;
    });
}

int gramhamScan(Point* res, int n, Point* ans)  //求凸包,O(nlogn),ans存放答案,返回凸包上点的数量
{
    if (n < 1) return 0;
    Point p = res[0];
    int k = 0, top = 1;
    for (int i = 1; i < n; i++) {
        if (res[i] < p) p = res[i], k = i;
    }
    swap(res[0], res[k]), sortByPolarAngle(res[0], res + 1, res + n), ans[0] = res[0];
    for (int i = 1; i < n; i++) {
        while (top > 2 && sgn((ans[top - 1] - ans[top - 2]).cross(res[i] - ans[top - 2])) <= 0) --top;
        ans[top++] = res[i];
    }
    return top;
}
double rotatingCalipers(Point* poly, int n)  //旋转卡壳,返回凸包直径
{
    double ans = 0;
    int j = 2;
    poly[n] = poly[0];
    for (int i = 0; i < n; i++) {
        while (area(poly[i], poly[i + 1], poly[j]) < area(poly[i], poly[i + 1], poly[j + 1])) {
            ++j;
            if (j > n) j = 0;
        }
        ans = max(ans, max(poly[i].dist(poly[j]), poly[i + 1].dist(poly[j])));
    }
    return ans;
}
int isPointInPolygon(Point p, Point* poly, int n)  //点在多边形内1;在外-1;在边界上0
{
    int wn = 0;
    for (int i = 0; i < n; ++i) {
        if (onSegment(p, poly[i], poly[(i + 1) % n])) return 0;
        int k = sgn((poly[(i + 1) % n] - poly[i]).cross(p - poly[i]));
        int d1 = sgn(poly[i].y - p.y);
        int d2 = sgn(poly[(i + 1) % n].y - p.y);
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    if (wn != 0) return 1;
    return -1;
}
  • 标题: XCPC丨算法竞赛汇总
  • 作者: Conqueror712
  • 创建于 : 2023-03-18 20:01:25
  • 更新于 : 2024-02-22 19:29:23
  • 链接: https://redefine.ohevan.com//post/ICPC.html
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
 评论
此页目录
XCPC丨算法竞赛汇总
  1. Graph - Theory
    1. Bellman-Ford
    2. Dijkstra
    3. Floyd
    4. Prim
    5. Kruskal
    6. TopoSort
    7. Euler Road
    8. Bipartite Graph
  2. Data - Structure
    1. Queue
    2. Stack
    3. Binary - Tree
    4. Heap
    5. Hash
    6. Monotone - Stack and Queue
    7. Tree
    8. Trie Tree
    9. Union - Find - Set
    10. Segment Tree
  3. Number - Theory
    1. Exact - Division & gcd & lcm
    2. Prime Sieve & Block - By - Block
    3. Coresidual & Euler Func & Inverse
    4. Qmi & Conbinatorial Number
    5. Gaussian Elimination
    6. Chinese Remainder Theorem
  4. Other Algorithm
    1. BFS & DFS
    2. Binary Search
    3. String
    4. Discretization & Prefix sum & Difference
    5. Double Pointer
    6. High Precision
    7. Bit Operation
    8. Quick Readin
    9. Game Theory
    10. Team Mo
  5. Computation Geometry