模板 - 普及-难度模板

普及-

P3383 【模板】线性筛素数

给定一个范围 $n$，有 $q$ 个询问，每次输出第 $k$ 小的素数。

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e8 + 7;

int n, q;
bool prime[N];
int ans[N], tot;

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 2; i <= n; ++i) {
		if (!prime[i]) {
			ans[++tot] = i;
		}
		for (int j = 1; j <= tot && i * ans[j] <= n; ++j) {
			prime[i * ans[j]] = 1;
			if (!(i % ans[j])) {
				break;
			}
		}
	}
	for (int i = 1; i <= q; ++i) {
		int x;
		scanf("%d", &x);
		printf("%d\n", ans[x]);
	}
	return 0;
}

P3378 【模板】堆

给定一个数列，初始为空，支持下面三种操作：

  1. 给定一个整数 $x$，请将 $x$ 加入到数列中。

  2. 输出数列中最小的数。

  3. 删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>> heap;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		if (x == 1) {
			int y;
			scanf("%d", &y);
			heap.push(y);
		} else if (x == 2) {
			printf("%d\n", heap.top());
		} else if (x == 3) {
			heap.pop();
		}
	}
	return 0;
}

P3370 【模板】字符串哈希

给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串。

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
#include<bits/stdc++.h>
using namespace std;

const int base = 47;

int n, st[10001], cnt;
int hash_(string s) {
	int ans = 0;
	for (int i = 0; i < s.length(); ++i) {
		ans = ans * base + s[i];
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		string s;
		cin >> s;
		st[i - 1] = hash_(s);
	}

	sort(st, st + n);
	unique(st, st + n);
	
	for (int i = 1; i <= n; i++) {
		if (st[i - 1] < st[i]) {
			++cnt;
		} else {
			break;
		}
	}

	printf("%d", cnt + 1);
	return 0;
}

P1226 【模板】快速幂

给定三个整数 $a,b,p$，求 $a^b \bmod p$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

long long a, b, mod;
long long qpow(int x, int y) {
	if (!y) {
		return 1;
	}
	long long n = qpow(x, y / 2) % mod;
	long long m = n * n % mod;
	if (y % 2) {
		m *= x;
	}
	return m % mod;
}

int main() {
	scanf("%lld%lld%lld", &a, &b, &mod);
	cout << a << "^" << b << " mod " << mod << "=" << qpow(a, b);
	return 0;
}

P1177 【模板】排序（归并排序做法）

将读入的 $n$ 个数从小到大排序后输出。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n;
int a[N], b[N];
int ans;

void mergesort(int l, int r) {
	if (l >= r) {  //不能再分了
		return ;
	}

	int mid = (l + r) >> 1;
	mergesort(l, mid);
	mergesort(mid + 1, r);

	int i = l, j = mid + 1, k = l;
	while (i <= mid && j <= r) {  //合并
		if (a[i] <= a[j]) {
			b[k++] = a[i++];
		} else {
			b[k++] = a[j++];
		}
	}

	while (i <= mid) {  //剩下
		b[k++] = a[i++];
	}
	while (j <= r) {
		b[k++] = a[j++];
	}
	for (int i = l; i <= r; i++) {
		a[i] = b[i];
	}
	return;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}

	mergesort(1, n);

	for (int i = 1; i <= n; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}

B3647 【模板】Floyd

给出一张由 $n$ 个点 $m$ 条边组成的无向图。求出所有点对 $(i,j)$ 之间的最短路径。数据中可能存在重边。 

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
#include<bits/stdc++.h>
using namespace std;

const int N = 105;
const int inf = 2147483647;

int n, m;
int dis[N][N];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; +j+) {
			dis[i][j] = inf;
		}
	}
	for (int i = 1; i <= n; ++i) {
		dis[i][i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if (dis[x][y] != inf && dis[y][x] != inf) {
			dis[x][y] = min(dis[x][y], z), dis[y][x] = min(dis[x][y], z);
		} else if (x != y) {
			dis[x][y] = z, dis[y][x] = z;
		} else if (x == y) {
			dis[x][y] = 0;
		}
	}

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

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (dis[i][j] == inf) {
				printf("0 ");
			} else {
				printf("%d ", dis[i][j]);
			}
		}
		printf("\n");
	}
	return 0;
}

B3644 【模板】拓扑排序 / 家谱树

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。
第 $1$ 行一个整数 $N$（$1 \le N \le 100$），表示家族的人数。接下来 $N$ 行，第 $i$ 行描述第 $i$ 个人的后代编号 $a_{i,j}$，表示 $a_{i,j}$ 是 $i$ 的后代。每行最后是 $0$ 表示描述完毕。
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。

样例输入1

1
2
3
4
5
6
5
0
4 5 1 0
1 0
5 3 0
3 0

样例输出1

1
2 4 5 3 1
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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;

int n;
int ltt, head[N];
int rd[N];

queue<int> tp;

struct G {
	int from, to;
} edge[N * N];

void addedge(int u, int v) {
	edge[++ltt] = (G) {
		v, head[u]
	};
	head[u] = ltt;
}

void topo() {
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (!rd[i]) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		tp.push(u);
		for (int i = head[u]; i; i = edge[i].to) {
			int v = edge[i].from;
			if (!(--rd[v])) {
				q.push(v);
			}
		}
	}
	return;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x;
		while (1) {
			scanf("%d", &x);
			if (x != 0) {
				addedge(i, x);
			} else {
				break;
			}
			rd[x]++;
		}
	}
	topo();
	while (!tp.empty()) {
		printf("%d ", tp.front());
		tp.pop();
	}
	return 0;
}

B3614 【模板】栈

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
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

int T;
int n;

signed main() {
	cin >> T;
	for (int i = 1; i <= T; ++i) {
		stack<int> stk;
		cin >> n;
		for (int j = 1; j <= n; ++j) {
			string op;
			cin >> op;
			if (op == "push") {
				int x;
				cin >> x;
				stk.push(x);
			} else if (op == "pop") {
				if (!stk.empty()) {
					stk.pop();
				} else {
					printf("Empty\n");
				}
			} else if (op == "query") {
				if (!stk.empty()) {
					cout << stk.top() << "\n";
				} else {
					printf("Anguei!\n");
				}
			} else {
				cout << stk.size() << "\n";
			}
		}
	}
	return 0;
}

B3616 【模板】队列

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
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

int n;

signed main() {
	queue<int> que;
	cin >> n;
	for (int j = 1; j <= n; ++j) {
		int op;
		cin >> op;
		if (op == 1) {
			int x;
			cin >> x;
			que.push(x);
		} else if (op == 2) {
			if (!que.empty()) {
				que.pop();
			} else {
				printf("ERR_CANNOT_POP\n");
			}
		} else if (op == 3) {
			if (!que.empty()) {
				cout << que.front() << "\n";
			} else {
				printf("ERR_CANNOT_QUERY\n");
			}
		} else {
			cout << que.size() << "\n";
		}
	}
	return 0;
}

B3656 【模板】双端队列

要求实现 $m$ 个双端队列，支持如下的 $q$ 次操作：

  • push_back(a,x)：在第 $a$ 个双端队列中从尾部插入一个元素 $x$；
  • pop_back(a)：在第 $a$ 个双端队列中从尾部弹出一个元素。
  • push_front(a,x)：在第 $a$ 个双端队列中从头部插入一个元素 $x$；
  • pop_front(a)：在第 $a$ 个双端队列中从头部弹出一个元素。
  • size(a)：查询第 $a$ 个双端队列的元素个数；
  • front(a)：查询第 $a$ 个双端队列的队首元素；
  • back(a)：查询第 $a$ 个双端队列的队尾元素；
    对于 pop_back，pop_front，front 和 back 操作，若当前双端队列为空则不进行，直接跳过该次操作。
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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 7;

int q;
list<int> a[N];

int main() {
	scanf("%d", &q);
	string k;
	for (int i = 1; i <= q; ++i) {
		cin >> k;
		if (k == "pop_back") {
			int m;
			cin >> m;
			if (!a[m].empty()) {
				a[m].pop_back();
			}
		} else if (k == "push_back") {
			int m, n;
			scanf("%d%d", &m, &n);
			a[m].push_back(n);
		} else if (k == "pop_front") {
			int m;
			scanf("%d", &m);
			if (!a[m].empty()) {
				a[m].pop_front();
			}
		} else if (k == "push_front") {
			int m, n;
			cin >> m >> n;
			a[m].push_front(n);
		} else if (k == "size") {
			int m;
			cin >> m;
			printf("%d\n", a[m].size());
		} else if (k == "front") {
			int m;
			cin >> m;
			if (!a[m].empty()) {
				printf("%d\n", a[m].front());
			}
		} else if (k == "back") {
			int m;
			cin >> m;
			if (!a[m].empty()) {
				printf("%d\n", a[m].back());
			}
		}
	}
	return 0;
}

P10815 【模板】快速读入

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e8 + 5;

int n;
int a[N];
int ans;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar_unlocked();
	while (!isdigit(ch)) {
		if (ch == '-')
			f = -1;
		ch = getchar_unlocked();
	}
	while (isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar_unlocked();
	}
	return x * f;
}

inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

int main() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		ans += a[i];
	}
	write(ans);
	return 0;
}

B3694 数列离散化

给定一个长度为 $n$ 的数列 $a$。定义 $\mathrm{rank}(i)$ 表示数列 $a$ 中比 $a_i$ 小的不同数字个数再加一。
对 $1 \leq i \leq n$，现在请你求出所有的 $\mathrm{rank}(i)$。

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;

int T;
int n;
int a[N], rk[N];

int main() {
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= n; ++i) {
			rk[i] = a[i];
		}
		sort(rk + 1, rk + 1 + n);
		int len = unique(rk + 1, rk + 1 + n) - rk - 1;
		for (int i = 1; i <= n; ++i) {
			a[i] = lower_bound(rk + 1, rk + 1 + len, a[i]) - rk;
		}
		for (int i = 1; i <= n; ++i) {
			printf("%d ", a[i]);
		}
		printf("\n");
	}
	return 0;
}

B2105 矩阵乘法

计算两个矩阵的乘法。$n \times m$ 阶的矩阵 $A$ 乘以 $m \times k$ 阶的矩阵 $B$ 得到的矩阵 $C$ 是 $n \times k$ 阶的，且 $C[i][j]=A[i][0] \times B[0][j]+A[i][1] \times B[1][j]+$ …… $+A[i][m-1] \times B[m-1][j](C[i][j]$ 表示 $C$ 矩阵中第 $i$ 行第 $j$ 列元素）。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int n, m, p;
int a[N][N], b[N][N], c[N][N];

int main() {
	scanf("%d%d%d", &n, &m, &p);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= p; ++j) {
			scanf("%d", &b[i][j]);
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= p; ++j) {
			for (int k = 1; k <= m; ++k) {
				c[i][j] += a[i][k] * b[k][j];
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= p; ++j) {
			printf("%d ", c[i][j]);
		}
		printf("\n");
	}
	return 0;
}