模板汇总
发现有规律单调的，可以考虑二分进行找答案
涉及到数理，多想想数学，实在不行列答案找规律
日期题目，涉及到天存不存在：二月份，31与30天，注意闰年判断
看数据范围，比较小可以考虑枚举
实在不行，考虑暴搜，打表
注意除0的边界
数据范围小，可以爆搜
前缀和和差分
前缀和
概念： 前缀和是一个数组的子数组从第一个元素到当前元素的所有元素的总和。对于数组a[1], a[2], ..., a[n]，我们可以构造一个前缀和数组s[1], s[2], ..., s[n]，其中s[i] = a[1] + a[2] + ... + a[i]。通过前缀和，我们可以快速计算任意区间内元素的和。
用途：
快速计算任意区间内元素的和。用于处理“区间查询”问题，如LeetCode中的“303. 区域和检索 - 数组不可变”。
示例： 假设有一个数组nums = [1, 2, 3, 4, 5]，其对应的前缀和数组prefixSums为[1, 3, 6, 10, 15]。如果想要查询区间[2, 4]的和，则可以通过计算prefixSums[4] - prefixSums[1]得到结果，即10 - 3 = 7。
差分
概念： 差分是一种与前缀和相反的概念。对于数组a[1], a[2], ..., a[n]，我们可以构造一个差分数组d[1], d[2], ..., d[n]，其中d[i] = a[i] - a[i - 1]（d[1] = a[1]）。差分数组的第一项与原数组相同，其余项表示原数组相邻两项的差。
用途：
快速进行区间更新操作。用于处理“区间更新”问题，如LeetCode中的“1094. 拼车”。
示例： 假设有一个数组nums = [1, 2, 3, 4, 5]，其对应的差分数组diff为[1, 1, 1, 1, 1]。如果我们想要将区间[2, 4]内的所有元素都增加1，只需要更新差分数组：diff[2] += 1和diff[5] -= 1，更新后的差分数组为[1, 2, 1, 1, 0]。通过差分数组可以反推出更新后的原数组：[1, 3, 4, 5, 5]。
二维前缀和的计算
二维前缀和的计算可以通过以下公式得到：
Sum[i][j] = Sum[i-1][j] + Sum[i][j-1] - Sum[i-1][j-1] + arr[i][j];
其中，prefixSum[i-1][j]表示当前位置上方所有元素的和，prefixSum[i][j-1]表示当前位置左侧所有元素的和，而prefixSum[i-1][j-1]表示当前位置左上角所有元素的和。由于在计算prefixSum[i-1][j]和prefixSum[i][j-1]时，prefixSum[i-1][j-1]被重复计算了两次，所以需要减去。
结构体数组申明
typedef struct {
int t, d, l;
} fly;
fly a[15];
1.P3367 【模板】并查集
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入格式
第一行包含两个整数
N
,
M
N,M
N,M ,表示共有
N
N
N 个元素和
M
M
M 个操作。
接下来
M
M
M 行，每行包含三个整数
Z
i
,
X
i
,
Y
i
Z_i,X_i,Y_i
Zi,Xi,Yi 。
当
Z
i
=
1
Z_i=1
Zi=1 时，将
X
i
X_i
Xi 与
Y
i
Y_i
Yi 所在的集合合并。
当
Z
i
=
2
Z_i=2
Zi=2 时，输出
X
i
X_i
Xi 与
Y
i
Y_i
Yi 是否在同一集合内，是的输出 Y ；否则输出 N 。
输出格式
对于每一个
Z
i
=
2
Z_i=2
Zi=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
样例 #1
样例输入 #1
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
样例输出 #1
N
Y
N
Y
提示
对于
30
%
30\%
30% 的数据，
N
≤
10
N \le 10
N≤10，
M
≤
20
M \le 20
M≤20。
对于
70
%
70\%
70% 的数据，
N
≤
100
N \le 100
N≤100，
M
≤
1
0
3
M \le 10^3
M≤103。
对于
100
%
100\%
100% 的数据，
1
≤
N
≤
1
0
4
1\le N \le 10^4
1≤N≤104，
1
≤
M
≤
2
×
1
0
5
1\le M \le 2\times 10^5
1≤M≤2×105，
1
≤
X
i
,
Y
i
≤
N
1 \le X_i, Y_i \le N
1≤Xi,Yi≤N，
Z
i
∈
{
1
,
2
}
Z_i \in \{ 1, 2 \}
Zi∈{1,2}。
代码
#include
#define MAXN 10005
int fa[MAXN], rank[MAXN]; //rank根节点深度
void init(int n) { //初始化 父节点是自己，深度是1
for (int i = 1; i <= n; i++) {
fa[i] = i;
rank[i] = 1;
}
}
int find(int x) { //合并（路径压缩） 层层访问父节点是谁，直到访问父节点指向自己（父中父）
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void merge(int i, int j) { //合并（按秩合并） 简单的树往复杂的树上合并
int x = find(i), y = find(j);
if (rank[x] <= rank[y])
fa[x] = y;
else
fa[y] = x;
if (rank[x] == rank[y] && x != y) {
rank[y]++;
}
}
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
init(n);
int x, y, z;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &z, &x, &y );
if (z == 1)
merge(x, y);
else
printf("%s\n", find(x) == find(y) ? "Y" : "N");
}
return 0;
}
并查集优化例题
P8686 蓝桥杯 2019 省 A] 修改数组
题目描述
给定一个长度为
N
N
N 的数组
A
=
[
A
1
,
A
2
,
⋯
A
N
]
A=[A_1,A_2, \cdots A_N]
A=[A1,A2,⋯AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改
A
2
,
A
3
,
⋯
,
A
N
A_2,A_3, \cdots ,A_N
A2,A3,⋯,AN。
当修改
A
i
A_i
Ai 时，小明会检查
A
i
A_i
Ai 是否在
A
1
A_1
A1 ∼
A
i
−
1
A_{i-1}
Ai−1 中出现过。如果出现过，则小明会给
A
i
A_i
Ai 加上
1
1
1；如果新的
A
i
A_i
Ai 仍在之前出现过，小明会持续给
A
i
A_i
Ai 加
1
1
1，直到
A
i
A_i
Ai 没有在
A
1
A_1
A1 ∼
A
i
−
1
A_{i-1}
Ai−1 中出现过。
当
A
N
A_N
AN 也经过上述修改之后，显然
A
A
A 数组中就没有重复的整数了。
现在给定初始的
A
A
A 数组，请你计算出最终的
A
A
A 数组。
输入格式
第一行包含一个整数
N
N
N。
第二行包含
N
N
N 个整数
A
1
,
A
2
,
⋯
,
A
N
A_1,A_2, \cdots ,A_N
A1,A2,⋯,AN。
输出格式
输出
N
N
N 个整数，依次是最终的
A
1
,
A
2
,
⋯
,
A
N
A_1,A_2, \cdots ,A_N
A1,A2,⋯,AN。
样例 #1
样例输入 #1
5
2 1 1 3 4
样例输出 #1
2 1 3 4 5
提示
对于
80
%
80\%
80% 的评测用例，
1
≤
N
≤
10000
1 \le N \le 10000
1≤N≤10000。
对于所有评测用例，
1
≤
N
≤
1
0
5
1 \le N \le 10^5
1≤N≤105，
1
≤
A
i
≤
1
0
6
1 \le A_i \le 10^6
1≤Ai≤106。
蓝桥杯 2019 年省赛 A 组 H 题。
代码
#include
#include
int f[1000005], a[1000005];
int find(int x) {
return f[x] == x ? x : (f[x] = find(f[x]));
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 1; i <= 1e6 + 5; i++)
f[i] = i;
for (int i = 1; i <= n; i++) { //重中之重
scanf("%d", &a[i]);
a[i] = find(a[i]); //变为自己的祖先
printf("%d ", a[i]); //输出
f[a[i]]++;//祖先的祖先 -> 变为不同的数
}
return 0;
}
P1177 【模板】排序
题目描述
将读入的
N
N
N 个数从小到大排序后输出。
输入格式
第一行为一个正整数
N
N
N。
第二行包含
N
N
N 个空格隔开的正整数
a
i
a_i
ai，为你需要进行排序的数。
输出格式
将给定的
N
N
N 个数从小到大输出，数之间空格隔开，行末换行且无空格。
样例 #1
样例输入 #1
5
4 2 4 5 1
样例输出 #1
1 2 4 4 5
提示
对于
20
%
20\%
20% 的数据，有
1
≤
N
≤
1
0
3
1 \leq N \leq 10^3
1≤N≤103；
对于
100
%
100\%
100% 的数据，有
1
≤
N
≤
1
0
5
1 \leq N \leq 10^5
1≤N≤105，
1
≤
a
i
≤
1
0
9
1 \le a_i \le 10^9
1≤ai≤109。
代码
#include
#include
int cmpfunc (const void *a, const void *b) {
return ( *(int *)a - * (int *)b );
}
int main(void) {
int n, a[100000] = {0,};
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmpfunc);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
关于比较函数,以结构体为例
int comparePersons(const void *a, const void *b) {
const Person *personA = (const Person *) a;
const Person *personB = (const Person *) b;
// 根据年龄比较两个 Person 结构体
if (personA->age < personB->age) {
return -1;
} else if (personA->age > personB->age) {
return 1;
}
return 0;
}
在cmp函数中，你应该返回以下值之一：
如果a应该排在b之前，返回一个小于0的值。如果a和b相等，返回0。如果a应该排在b之后，返回一个大于0的值。
P3374 【模板】树状数组 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
将某一个数加上
x
x
x 求出某区间每一个数的和
输入格式
第一行包含两个正整数
n
,
m
n,m
n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含
n
n
n 个用空格分隔的整数，其中第
i
i
i 个数字表示数列第
i
i
i 项的初始值。
接下来
m
m
m 行每行包含
3
3
3 个整数，表示一个操作，具体如下：
1 x k 含义：将第
x
x
x 个数加上
k
k
k 2 x y 含义：输出区间
[
x
,
y
]
[x,y]
[x,y] 内每个数的和
输出格式
输出包含若干行整数，即为所有操作
2
2
2 的结果。
样例 #1
样例输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
样例输出 #1
14
16
提示
【数据范围】
对于
30
%
30\%
30% 的数据，
1
≤
n
≤
8
1 \le n \le 8
1≤n≤8，
1
≤
m
≤
10
1\le m \le 10
1≤m≤10； 对于
70
%
70\%
70% 的数据，
1
≤
n
,
m
≤
1
0
4
1\le n,m \le 10^4
1≤n,m≤104； 对于
100
%
100\%
100% 的数据，
1
≤
n
,
m
≤
5
×
1
0
5
1\le n,m \le 5\times 10^5
1≤n,m≤5×105。
数据保证对于任意时刻，
a
a
a 的任意子区间（包括长度为
1
1
1 和
n
n
n 的子区间）和均在
[
−
2
31
,
2
31
)
[-2^{31}, 2^{31})
[−231,231) 范围内。
样例说明：
故输出结果14、16
代码
#include
int n, m, tree[2000010];
int lowbit(int k) {
return k & -k;
}
void add(int x, int k) {
while (x <= n) {
tree[x] += k;
x += lowbit(x);
}
}
int sum(int x) {
int ans = 0;
while (x != 0) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main(void) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
add(i, a);
}
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (a == 1)
add(b, c);
else if (a == 2)
printf("%d\n", sum(c) - sum(b - 1));
}
return 0;
}
P5367 【模板】康托展开
题目描述
求
1
∼
N
1\sim N
1∼N 的一个给定全排列在所有
1
∼
N
1\sim N
1∼N 全排列中的排名。结果对
998244353
998244353
998244353 取模。
输入格式
第一行一个正整数
N
N
N。
第二行
N
N
N 个正整数，表示
1
∼
N
1\sim N
1∼N 的一种全排列。
输出格式
一行一个非负整数，表示答案对
998244353
998244353
998244353 取模的值。
样例 #1
样例输入 #1
3
2 1 3
样例输出 #1
3
样例 #2
样例输入 #2
4
1 2 4 3
样例输出 #2
2
提示
对于
10
%
10\%
10%数据，
1
≤
N
≤
10
1\le N\le 10
1≤N≤10。
对于
50
%
50\%
50%数据，
1
≤
N
≤
5000
1\le N\le 5000
1≤N≤5000。
对于
100
%
100\%
100%数据，
1
≤
N
≤
1000000
1\le N\le 1000000
1≤N≤1000000。
#include
#define mod 998244353
int n;
int tree[1000005],a[1000005];
long jc[1000005] = {1, 1,};
int lowbit(int k) {
return k & -k;
}
void add(int x, int k) {
while (x <= n) {
tree[x] += k;
x += lowbit(x);
}
}
int sum(int x) {
int ans = 0;
while (x != 0) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
jc[i] = (jc[i - 1] * i) % mod;
add(i, 1);
}
long ans = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
ans = (ans + ((sum(a[i]) - 1) * jc[n - i]) % mod) % mod; //计算ans
add(a[i], -1); //把a[i]变成0（原来是1，减1不就是0嘛）
}
printf("%lld", ans + 1);
return 0;
}
P3383 【模板】线性筛素数
题目背景
本题已更新，从判断素数改为了查询第
k
k
k 小的素数 提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。
题目描述
如题，给定一个范围
n
n
n，有
q
q
q 个询问，每次输出第
k
k
k 小的素数。
输入格式
第一行包含两个正整数
n
,
q
n,q
n,q，分别表示查询的范围和查询的个数。
接下来
q
q
q 行每行一个正整数
k
k
k，表示查询第
k
k
k 小的素数。
输出格式
输出
q
q
q 行，每行一个正整数表示答案。
样例 #1
样例输入 #1
100 5
1
2
3
4
5
样例输出 #1
2
3
5
7
11
提示
【数据范围】 对于
100
%
100\%
100% 的数据，
n
=
1
0
8
n = 10^8
n=108，
1
≤
q
≤
1
0
6
1 \le q \le 10^6
1≤q≤106，保证查询的素数不大于
n
n
n。
Data by NaCly_Fish.
代码
#include
#include
#include
bool is_prime[100000010];
int prime[6000010];
int cnt;
void Prime(int n) {
memset(is_prime, 1, sizeof(is_prime));
is_prime[1] = 0;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
is_prime[i * prime[j]] = 0;
if (i % prime[j] == 0)
break;
}
}
}
int main(void) {
int n, q;
scanf("%d %d", &n, &q);
Prime(n);
while (q--) {
int k;
scanf("%d", &k);
printf("%d\n", prime[k]);
}
return 0;
}
P8742 蓝桥杯 砝码称重 01背包参考题
题目描述
你有一架天平和
N
N
N 个砝码, 这
N
N
N 个砝码重量依次是
W
1
,
W
2
,
⋯
,
W
N
W_{1}, W_{2}, \cdots, W_{N}
W1,W2,⋯,WN 。 请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数
N
N
N 。
第二行包含
N
N
N 个整数:
W
1
,
W
2
,
W
3
,
⋯
,
W
N
W_{1}, W_{2}, W_{3}, \cdots, W_{N}
W1,W2,W3,⋯,WN 。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
3
1 4 6
样例输出 #1
10
提示
【样例说明】
能称出的 10 种重量是:
1
、
2
、
3
、
4
、
5
、
6
、
7
、
9
、
10
、
11
1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11
1、2、3、4、5、6、7、9、10、11 。
1
=
1
2
=
6
−
4
(
天平一边放
6
,
另一边放 4)
3
=
4
−
1
4
=
4
5
=
6
−
1
6
=
6
7
=
1
+
6
9
=
4
+
6
−
1
10
=
4
+
6
11
=
1
+
4
+
6
\begin{aligned} &1=1 \\ &2=6-4(\text { 天平一边放 } 6, \text { 另一边放 4) } \\ &3=4-1 \\ &4=4 \\ &5=6-1 \\ &6=6 \\ &7=1+6 \\ &9=4+6-1 \\ &10=4+6 \\ &11=1+4+6 \end{aligned}
1=12=6−4( 天平一边放 6, 另一边放 4) 3=4−14=45=6−16=67=1+69=4+6−110=4+611=1+4+6
【评测用例规模与约定】
对于
50
%
50 \%
50% 的评测用例,
1
≤
N
≤
15
1 \leq N \leq 15
1≤N≤15 。
对于所有评测用例,
1
≤
N
≤
100
,
N
1 \leq N \leq 100, N
1≤N≤100,N 个砝码总重不超过
1
0
5
10^5
105。
蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。
思路
这道题神牛一眼01背包（但是我是蒟蒻）
有i个砝码，然后对下一个砝码进行操作，会不会很像背包里有n个物体，然后对第n+1个物体进行处理（放or不放）（此题是，单放，放左，放右）
代码
#include
#include
int dp[105][100005], w[105];
//dp[i][j]含义：i:对第i个砝码的操作 j：重量
//思路是01背包的重要点 dp的值表示在第i个砝码下，j的重量存在
int main(void) {
int n, sum = 0, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
sum += w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = sum; j > 0; j--) {
if (w[i] == j)
dp[i][j] = 1;
else if (dp[i - 1][j])
dp[i][j] = 1;
else if (dp[i - 1][j + w[i]])
dp[i][j] = 1;
else if (dp[i - 1][abs(j - w[i])])
dp[i][j] = 1;
}
}
for (int i = 1; i <= sum; i++)
if (dp[n][i]) {
ans++;
}
printf ("%d", ans);
return 0;
}
P1029 最大公约数和最小公倍数问题 gcd模板
题目描述
输入两个正整数
x
0
,
y
0
x_0, y_0
x0,y0，求出满足下列条件的
P
,
Q
P, Q
P,Q 的个数：
P
,
Q
P,Q
P,Q 是正整数。 要求
P
,
Q
P, Q
P,Q 以
x
0
x_0
x0 为最大公约数，以
y
0
y_0
y0 为最小公倍数。
试求：满足条件的所有可能的
P
,
Q
P, Q
P,Q 的个数。
输入格式
一行两个正整数
x
0
,
y
0
x_0, y_0
x0,y0。
输出格式
一行一个数，表示求出满足条件的
P
,
Q
P, Q
P,Q 的个数。
样例 #1
样例输入 #1
3 60
样例输出 #1
4
提示
P
,
Q
P,Q
P,Q 有
4
4
4 种：
3
,
60
3, 60
3,60。
15
,
12
15, 12
15,12。
12
,
15
12, 15
12,15。
60
,
3
60, 3
60,3。
对于
100
%
100\%
100% 的数据，
2
≤
x
0
,
y
0
≤
10
5
2 \le x_0, y_0 \le {10}^5
2≤x0,y0≤105。
【题目来源】
NOIP 2001 普及组第二题
主要模板
int gcd(int a, int b) {
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}
int lcm(int a, int b) {
return (a * b / gcd(a, b));
}
实现
这里复制一下大佬的题解，写的真的好（但是这个是好久之前写的找不到大佬题解的原文了，如果找到了我再回来附上原文链接）
首先，咱们得了解一下辗转相除求最大公因数法（奥数内容）。 比如说40和12，40/12余4，除数作为下一回的被除数，余数作为下一回的除数，得到12/4，这就是最大公约数（如果有余数就再除，直到没有余数，这正好符合递归思想）
int d(int a,int b){//求最大公约数函数。a,b是两个待求最大公约数的数，不是题里的x0y0。
if(a
if(a%b==0) return b;//如果a/b余0，那么b就是最大公约数。比如10和5， 10/5余0，5就是最大公约数
else return d(b,a%b);//辗转相除法求最大公因数（其实交换ab那一步没必要，小除以大余小本身，到这里自然就换过来了，比如3和15，3/15余3，到这里就变成了15和3，嗯）
}
我的思路是编求最大公约和最小公倍的函数，然后for，搜索。
大家都知道，最大公因数和最小公倍数的乘积等于原两个数的乘积。所以，最小公倍数这么求：
int x(int a,int b){//最小公倍数
return (a*b/d(a,b));//这两个数的乘积除以最大公因数等于最小公倍数。
}
放全程序：
#include
using namespace std;
int ans=0;//ans是情况数量。
int d(int a,int b){//求最大公约数函数。a,b是两个待求最大公约数的数，不是题里的x0y0。
if(a
if(a%b==0) return b;//如果a/b余0，那么b就是最大公约数。比如10和5， 10/5余0，5就是最大公约数
else return d(b,a%b);//辗转相除法求最大公因数（其实交换ab那一步没必要，小除以大余小本身，到这里自然就换过来了，比如3和15，3/15余3，到这里就变成了15和3，嗯）
}
int x(int a,int b){//最小公倍数
return (a*b/d(a,b));//最大公因数和最小公倍数的乘积等于原两个数的乘积。所以这两个数的乘积除以最大公因数等于最小公倍数。
}
int main(){
int x0,y0;//这才是x0y0.
cin>>x0>>y0;//（这里用个搜索就行了）
for(int i=x0;i<=y0;i++){//a一定在它的最大公因数和最小公倍数之间，这很明显
int j=x0*y0/i;//最大公因数和最小公倍数的乘积等于原两个数的乘积。老道理 。b就这样算
if(d(i,j)==x0&&x(i,j)==y0)// 如果ab（ij）的最大公因数，最小公倍数符合x0y0
ans++;//计数
}
cout< return 0; } 代码 #include int ans; int gcd(int a, int b) { if (a % b == 0) return b; else return gcd(b, a % b); } int lcm(int a, int b) { return (a * b / gcd(a, b)); } int main(void) { int x, y; scanf("%d %d", &x, &y); for (int i = x; i <= y; i++) { int j = x * y / i; if (gcd(i, j) == x && lcm(i, j) == y) ans++; } printf("%d", ans); return 0; } P3378 【模板】堆(小根堆) 下辈子还是学c++吧别c语言手搓了 【模板】堆 题目描述 给定一个数列，初始为空，请支持下面三种操作： 给定一个整数 x x x，请将 x x x 加入到数列中。输出数列中最小的数。删除数列中最小的数（如果有多个数最小，只删除 1 1 1 个）。 输入格式 第一行是一个整数，表示操作的次数 n n n。 接下来 n n n 行，每行表示一次操作。每行首先有一个整数 o p op op 表示操作类型。 若 o p = 1 op = 1 op=1，则后面有一个整数 x x x，表示要将 x x x 加入数列。若 o p = 2 op = 2 op=2，则表示要求输出数列中的最小数。若 o p = 3 op = 3 op=3，则表示删除数列中的最小数。如果有多个数最小，只删除 1 1 1 个。 输出格式 对于每个操作 2 2 2，输出一行一个整数表示答案。 样例 #1 样例输入 #1 5 1 2 1 5 2 3 2 样例输出 #1 2 5 提示 【数据规模与约定】 对于 30 % 30\% 30% 的数据，保证 n ≤ 15 n \leq 15 n≤15。对于 70 % 70\% 70% 的数据，保证 n ≤ 1 0 4 n \leq 10^4 n≤104。对于 100 % 100\% 100% 的数据，保证 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1≤n≤106， 1 ≤ x < 2 31 1 \leq x \lt 2^{31} 1≤x<231， o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\} op∈{1,2,3}。 代码 每一个父节点id 的左儿子是 2×id，右儿子是 2×id+1 #include #define MAX 1000005 int size, heap[MAX]; int push_up(int i, int val) { //找父节点 while (i > 1 && val < heap[i / 2]) { //存在父节点且比父节点大 heap[i] = heap[i / 2]; i /= 2; } return i; } int push_down(int i, int val) { int ch = i * 2; while (ch <= size) { if (ch < size && heap[ch + 1] < heap[ch]) ch++;//找下一个 if (val <= heap[ch]) break; heap[i] = heap[ch]; i = ch; ch += ch; } return i; } void insert(int val) { int i = ++size; i = push_up(i, val); heap[i] = val; } void delete_min() {//删除堆顶 int i = 1, val = heap[size--]; i = push_down(i, val);//调整位置 heap[i] = val; } int main(void) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { int opt, x; scanf("%d", &opt); if (opt == 1) { scanf("%d", &x); insert(x); } if (opt == 2) { printf("%d\n", heap[1]); } if (opt == 3) { delete_min(); } } return 0; } P1226 【模板】快速幂 题目描述 给你三个整数 a , b , p a,b,p a,b,p，求 a b m o d p a^b \bmod p abmodp。 输入格式 输入只有一行三个整数，分别代表 a , b , p a,b,p a,b,p。 输出格式 输出一行一个字符串 a^b mod p=s，其中 a , b , p a,b,p a,b,p 分别为题目给定的值， s s s 为运算结果。 样例 #1 样例输入 #1 2 10 9 样例输出 #1 2^10 mod 9=7 提示 样例解释 2 10 = 1024 2^{10} = 1024 210=1024， 1024 m o d 9 = 7 1024 \bmod 9 = 7 1024mod9=7。 数据规模与约定 对于 100 % 100\% 100% 的数据，保证 0 ≤ a , b < 2 31 0\le a,b < 2^{31} 0≤a,b<231， a + b > 0 a+b>0 a+b>0， 2 ≤ p < 2 31 2 \leq p \lt 2^{31} 2≤p<231。 代码 #include long long b,a,p,k,ans=1,c; int main() { scanf("%lld%lld%lld",&b,&p,&k); a=b;c=p; while(p>0)//快速幂 { if(p%2!=0) ans=ans*b%k;//如果p为单数，乘到ans里面去，然后取模 b=b*b%k;//每次运算都取模 p=p>>1; } ans %= k; printf("%lld^%lld mod %lld=%lld",a,c,k,ans);//输出 return 0; } P1886 滑动窗口 /【模板】单调队列 题目描述 有一个长为 n n n 的序列 a a a，以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。 例如，对于序列 [ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7] [1,3,−1,−3,5,3,6,7] 以及 k = 3 k = 3 k=3，有如下过程： 窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 − 1 3 1 [3 -1 -3] 5 3 6 7 − 3 3 1 3 [-1 -3 5] 3 6 7 − 3 5 1 3 -1 [-3 5 3] 6 7 − 3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 \def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} 窗口位置[1 3 -1] -3 5 3 6 7 1 [3 -1 -3] 5 3 6 7 1 3 [-1 -3 5] 3 6 7 1 3 -1 [-3 5 3] 6 7 1 3 -1 -3 [5 3 6] 7 1 3 -1 -3 5 [3 6 7]最小值−1−3−3−333最大值335567 输入格式 输入一共有两行，第一行有两个正整数 n , k n,k n,k。 第二行 n n n 个整数，表示序列 a a a 输出格式 输出共两行，第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值 样例 #1 样例输入 #1 8 3 1 3 -1 -3 5 3 6 7 样例输出 #1 -1 -3 -3 -3 3 3 3 3 5 5 6 7 提示 【数据范围】 对于 50 % 50\% 50% 的数据， 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105； 对于 100 % 100\% 100% 的数据， 1 ≤ k ≤ n ≤ 1 0 6 1\le k \le n \le 10^6 1≤k≤n≤106， a i ∈ [ − 2 31 , 2 31 ) a_i \in [-2^{31},2^{31}) ai∈[−231,231)。 代码 #include int a[1000005], q1[1000005], q2[1000005]; int n, m; void min_deque() { int h = 1, t = 0; for (int i = 1; i <= n; i++) { while (h <= t && q1[h] + m <= i)//滑动窗口空了并且下一个窗口位置没超 h++; while (h <= t && a[i] < a[q1[t]])//新进元素比前一个小，让前一个出列 t--; q1[++t] = i; if (i >= m) printf("%d ", a[q1[h]]); } printf("\n"); } void max_deque() { int h = 1, t = 0; for (int i = 1; i <= n; i++) { while (h <= t && q2[h] + m <= i) h++; while (h <= t && a[i] > a[q2[t]]) t--; q2[++t] = i; if (i >= m) printf("%d ", a[q2[h]]); } } int main(void) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); min_deque(); max_deque(); return 0; } P1775 石子合并（弱化版）区间dp 题目描述 设有 N ( N ≤ 300 ) N(N \le 300) N(N≤300) 堆石子排成一排，其编号为 1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N 1,2,3,⋯,N。每堆石子有一定的质量 m i ( m i ≤ 1000 ) m_i\ (m_i \le 1000) mi (mi≤1000)。现在要将这 N N N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。 输入格式 第一行，一个整数 N N N。 第二行， N N N 个整数 m i m_i mi。 输出格式 输出文件仅一个整数，也就是最小代价。 样例 #1 样例输入 #1 4 2 5 3 1 样例输出 #1 22 代码 #include #include int m[305], sum[305], dp[305][305]; //dp[i][j]:第i到第j段值的合并最小值 int min(int a, int b) { return a < b ? a : b; } int main(void) { int n; scanf("%d", &n); memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i <= n; i++) { scanf("%d", &m[i]); sum[i] = sum[i - 1] + m[i]; dp[i][i] = 0; } for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]); } } } printf("%d", dp[1][n]); return 0; } P9241 蓝桥杯 2023 省 B] 飞机降落 dfs爆搜 题目描述 N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_{i} Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 D i D_{i} Di 个单位时间，即它最早可以于 T i T_{i} Ti 时刻开始降落，最晩可以于 T i + D i T_{i}+D_{i} Ti+Di 时刻开始降落。降落过程需要 L i L_{i} Li 个单位时间。 一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。 请你判断 N N N 架飞机是否可以全部安全降落。 输入格式 输入包含多组数据。 第一行包含一个整数 T T T，代表测试数据的组数。 对于每组数据，第一行包含一个整数 N N N。 以下 N N N 行，每行包含三个整数 T i , D i , L i T_{i},D_{i},L_{i} Ti,Di,Li。 输出格式 对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。 样例 #1 样例输入 #1 2 3 0 100 10 10 10 10 0 2 20 3 0 10 20 10 10 20 20 10 20 样例输出 #1 YES NO 提示 【样例说明】 对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。 对于第二组数据，无论如何安排，都会有飞机不能及时降落。 【评测用例规模与约定】 对于 30 % 30 \% 30% 的数据， N ≤ 2 N \leq 2 N≤2。 对于 100 % 100 \% 100% 的数据， 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10， 1 ≤ N ≤ 10 1 \leq N \leq 10 1≤N≤10， 0 ≤ T i , D i , L i ≤ 1 0 5 0 \leq T_{i},D_{i},L_{i} \leq 10^{5} 0≤Ti,Di,Li≤105。 蓝桥杯 2023 省赛 B 组 D 题。 代码 #include #include #include int bk[15]; int t, n; typedef struct { int t, d, l; } fly; fly a[15]; int max(int a, int b) { return a > b ? a : b; } bool dfs(int dep, int tim) {//飞机架数 if (dep > n)//注意出口 return 1; for (int i = 1; i <= n; i++) { if (bk[i] || a[i].t + a[i].d < tim) //降落条件 continue; bk[i] = 1; if (dfs(dep + 1, max(tim, a[i].t) + a[i].l)) { //记得取max bk[i] = 0; return 1;//有一个成功就返回1 } bk[i] = 0; //记得去标记 } return 0; } int main(void) { scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d %d", &a[i].t, &a[i].d, &a[i].l); } for (int i = 1; i <= n; i++) { bk[i] = 0; } if (dfs(1, 0)) printf("YES\n"); else printf("NO\n"); } return 0; } P8687 蓝桥杯 2019 省 A] 糖果 状压dp 题目描述 糖果店的老板一共有 M M M 种口味的糖果出售。为了方便描述，我们将 M M M 种口味编号 1 1 1 ∼ M M M。 小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 K K K 颗一包整包出售。 幸好糖果包装上注明了其中 K K K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。 给定 N N N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。 输入格式 第一行包含三个整数 N N N、 M M M 和 K K K。 接下来 N N N 行每行 K K K 这整数 T 1 , T 2 , ⋯ , T K T_1,T_2, \cdots ,T_K T1,T2,⋯,TK，代表一包糖果的口味。 输出格式 一个整数表示答案。如果小明无法品尝所有口味，输出 − 1 -1 −1。 样例 #1 样例输入 #1 6 5 3 1 1 2 1 2 3 1 1 3 2 3 5 5 4 2 5 1 2 样例输出 #1 2 提示 对于 30 % 30\% 30% 的评测用例， 1 ≤ N ≤ 20 1 \le N \le 20 1≤N≤20。 对于所有评测样例， 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100， 1 ≤ M ≤ 20 1 \le M \le 20 1≤M≤20， 1 ≤ K ≤ 20 1 \le K \le 20 1≤K≤20， 1 ≤ T i ≤ M 1 \le T_i \le M 1≤Ti≤M。 蓝桥杯 2019 年省赛 A 组 I 题。 代码 #include #include int N, M, K, temp; int a[105], dp[1 << 20];//a数组第i包状压 int min(int a, int b) { if (a <= b) return a; else return b; } int main(void) { scanf("%d %d %d", &N, &M, &K); memset(dp, 127, sizeof(dp)); for (int i = 0; i < N; i++) { for (int j = 0; j < K; j++) { scanf("%d", &temp); a[i] |= 1 << temp - 1;//装压 } dp[a[i]] = 1; } dp[0] = 0; for (int i = 0; i < N; i++) {//遍历包糖 for (int j = 0; j < 1 << M; j++) { dp[j | a[i]] = min(dp[j | a[i]], dp[j] + 1); } } if (dp[(1 << M) - 1] < 127) printf("%d", dp[(1 << M) - 1]); else printf("-1"); return 0; } P1352 没有上司的舞会 树状dp 没有上司的舞会 题目描述 某大学有 n n n 个职员，编号为 1 … n 1\ldots n 1…n。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r i r_i ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 输入格式 输入的第一行是一个整数 n n n。 第 2 2 2 到第 ( n + 1 ) (n + 1) (n+1) 行，每行一个整数，第 ( i + 1 ) (i+1) (i+1) 行的整数表示 i i i 号职员的快乐指数 r i r_i ri。 第 ( n + 2 ) (n + 2) (n+2) 到第 2 n 2n 2n 行，每行输入一对整数 l , k l, k l,k，代表 k k k 是 l l l 的直接上司。 输出格式 输出一行一个整数代表最大的快乐指数。 样例 #1 样例输入 #1 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 样例输出 #1 5 提示 数据规模与约定 对于 100 % 100\% 100% 的数据，保证 1 ≤ n ≤ 6 × 1 0 3 1\leq n \leq 6 \times 10^3 1≤n≤6×103， − 128 ≤ r i ≤ 127 -128 \leq r_i\leq 127 −128≤ri≤127， 1 ≤ l , k ≤ n 1 \leq l, k \leq n 1≤l,k≤n，且给出的关系一定是一棵树。 代码 注意：给出的代码在洛谷会空间炸一个点QAQ #include #include #define MAXN 6005 int h[MAXN]; int v[MAXN]; int son[MAXN][MAXN]; int size[MAXN] = {0}; // 用于记录每个节点的子节点数量 int f[MAXN][2]; void dp(int x) { f[x][0] = 0; f[x][1] = h[x]; for (int i = 0; i < size[x]; i++) { int y = son[x][i]; dp(y); f[x][0] += f[y][0] > f[y][1] ? f[y][0] : f[y][1]; f[x][1] += f[y][0]; } } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &h[i]); } for (int i = 1; i <= n - 1; i++) { int x, y; scanf("%d %d", &x, &y); son[y][size[y]++] = x; // 添加子节点 v[x] = 1; } int root; for (int i = 1; i <= n; i++) { if (!v[i]) { root = i; break; } } dp(root); printf("%d\n", f[root][0] > f[root][1] ? f[root][0] : f[root][1]); return 0; } P2758 编辑距离 题目描述 设 A A A 和 B B B 是两个字符串。我们要用最少的字符操作次数，将字符串 A A A 转换为字符串 B B B。这里所说的字符操作共有三种： 删除一个字符；插入一个字符；将一个字符改为另一个字符。 A , B A, B A,B 均只包含小写字母。 输入格式 第一行为字符串 A A A；第二行为字符串 B B B；字符串 A , B A, B A,B 的长度均小于 2000 2000 2000。 输出格式 只有一个正整数，为最少字符操作次数。 样例 #1 样例输入 #1 sfdqxbw gfdgw 样例输出 #1 4 提示 对于 100 % 100 \% 100% 的数据， 1 ≤ ∣ A ∣ , ∣ B ∣ ≤ 2000 1 \le |A|, |B| \le 2000 1≤∣A∣,∣B∣≤2000。 #include #include int dp[2005][2005] = {0}; char a[2005], b[2005]; int lena, lenb; void dpp(void); int min(int, int, int); int main(void) { scanf("%s %s", &a, &b); lena = strlen(a); lenb = strlen(b); for (int i = 0; i <= lena; i++) { dp[i][0] = i; } for (int i = 0; i <= lenb; i++) { dp[0][i] = i; } dpp(); printf("%d", dp[lena][lenb]); return 0; } void dpp(void) { for (int m = 1; m <= lena; m++) { for (int n = 1; n <= lenb; n++) { if (a[m - 1] == b[n - 1]) dp[m][n] = dp[m - 1][n - 1]; else { dp[m][n] = 1 + min(dp[m][n - 1], dp[m - 1][n], dp[m - 1][n - 1]); } } } } int min(int w1, int w2, int w3) { if (w1 <= w2 && w1 <= w3) return w1; else if (w2 <= w1 && w2 <= w3) return w2; else return w3; } 2024/4/12更新 参考文章
您阅读本篇文章共花了：
发表评论