算法-蓝桥杯真题（1）

涉及的知识有很多，这里罗列出来:

这里涉及到的所有数据结构的时间复杂度都为$O(n)$

  1. 并查集
  2. 单调栈
  3. 单调队列

易错点（我自己的）

并查集

  • 并查集不使用 root() 函数来找祖先，虽然已经进行 路径压缩，但是防止写错还是要用 root() 来找根
  • 老是忘记 判断自环！！！！！！！ if(a == b) return ;

单调栈

  • 记得判断当前的 top 是否有效，无效的话要设为 $0$ 或者看题目要求，一般输出 $-1$ 或者定义为

    数组边界（$0$ 和 $n+1$）

单调队列

  • 第一：记得 维护下标合法性，这个老是忘记
  • 第二：记得一定一定一定要 清空队列，不然下一个判断受影响
  • 第三：一定要 形成滑动窗口 的时候才 记录答案
  • 第四：输出的时候也是 一定要有滑动窗口（括弧从 k 开始）才输出哈哈哈哈哈哈哈哈哈哈

并查集

详情见： 并查集 - OI Wiki

image-20250401200222968

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;
const int N = 1e5 + 10;
int n , m;
int p[N] , cnt[N]; // cnt数组用来维护连通块的大小

int find(int x) // 路径压缩
{
    if (x != p[x]) p[x] = find(p[x]);

    return p[x];
}

signed main()
{
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++ ) p[i] = i , cnt[i] = 1;
    

    while (m -- )
    {
        string op;
        cin >> op;
        if (op == "C")
        {
            int x , y;
            cin >> x >> y;
            int px = find(x) , py = find(y);
            if (px != py)
            {
                p[px] = py;
                cnt[py] += cnt[px];
            }
        }
        else if (op == "Q1")
        {
            int x , y;
            cin >> x >> y;

            int px = find(x) , py = find(y);
            if (px != py) cout << "No" << endl;
            else cout << "Yes" << endl;
        }

        else if (op == "Q2")
        {
            int temp;
            cin >> temp;
            cout << cnt[find(temp)] << endl;
        }
    } 

    return 0;
}

image-20250401200253287

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;
const int N = 1e5 + 10;
int n , m;
int p[N] , cnt[N];

int find(int x){
    if (x != p[x]) p[x] = find(p[x]);

    return p[x];
}

signed main()
{
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++ ) p[i] = i , cnt[i] = 1;
    

    while (m -- )
    {
        string op;
        cin >> op;
        if(op == "M")
        {
        	int a, b; cin >> a >> b;
        	int px = find(a), py = find(b);
        	if(px != py) p[px] = py;
        }
        else
        {
        	int a, b; cin >> a >> b;
        	int px = find(a), py = find(b);
        	if(px != py) cout << "No" << endl;
        	else cout << "Yes" << endl;
        }
    } 

    return 0;
}

单调栈

详情见：单调栈 - OI Wiki

image-20250401200410189

这道题真的非常已经是一个模板了，建议这道题必刷

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int n;
int a[N];
int stk[N];
int top;
int res[N];

int main()
{
	scanf("%d", &n);
	for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	
	// 左边第一个比其大的数字  比他小就弹出 <= a[i]
	for(int i = 1;i <= n;i ++)
	{
		while( top && a[stk[top]] <= a[i]) top --;
		// 此时我们的栈顶就是这个数字
		if(top) printf("%d ",a[stk[top]]);
		else  printf("-1 ");
		
		stk[++ top] = i;
	}
	puts("");
	top = 0;
	
	for(int i = n;i >= 1; i --)
	{
		while(top && a[stk[top]] <= a[i]) top --;
		if (top) res[i] = a[stk[top]]; // 存储结果
        else res[i] = -1;
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++) printf("%d ", res[i]); // 按原顺序输出
	puts("");
	top = 0;
	
	for(int i = 1;i <= n;i ++)
	{
		while( top && a[stk[top]] >= a[i]) top --;
		// 此时我们的栈顶就是这个数字
		if(top) printf("%d ",a[stk[top]]);
		else  printf("-1 ");
		
		stk[++ top] = i;
	}
	
	puts("");
	top = 0;
	
	for(int i = n;i >= 1; i --)
	{
		while(top && a[stk[top]] >= a[i]) top --;
		if (top) res[i] = a[stk[top]]; // 存储结果
        else res[i] = -1;
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++) printf("%d ", res[i]); // 按原顺序输出
	
	return 0;	
}
  • 注意这道题需要注意我们输出每个数字右边的数字时，我们利用的单调栈是反向维护的所以，我们要把数字存下来，正序输出
  • 还有就是每次我们都要重置整个栈，避免数据发生占用，重置语句 top = 0;

image-20250401200622564

  • 思路：我们可以发现只要当每个区间的最小值为 $a[i]$ 的时候，我们的 $min(A_L,A_{L+1},…,A_R)$ 会尽可能大，根据贪心策略我们知道 $R$ 和 $L$ 越相对 $a[i]$ 越远整个答案的值就越大，所以我们要找出对于 $a[i]$ 来说左边第一个比他小的数字，和右边第一个比他小的数字，然后两边都往中间收缩一位就是对于最小值为 $a[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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 3e5 + 10;

int n;
int a[N];
int stk[N];
int top;
int l[N], r[N];

int main()
{
	scanf("%d", &n);
	for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	
	// 找对于每一个a[i]左边的第一个比他小的数字
	for(int i = 1;i <= n;i ++)
	{
		while(top && a[stk[top]] >= a[i]) top --;
		if(top) l[i] = stk[top];
		else l[i] = 0;
		
		stk[++ top] = i;
	}	 
	
	top = 0;
	
	// 右边第一个比他小的数字
	for(int i = n;i >= 1;i --)
	{
		while(top && a[stk[top]] >= a[i]) top --;
		if(top) r[i] = stk[top];
		else r[i] = n + 1;
		
		stk[++ top] = i;
	}
	
	long long ans = 0;
	for(int i = 1;i <= n;i ++)
	{
		ans = max(ans ,((long long)(r[i] - 1) - (l[i] + 1) + 1) * a[i]);
	}
	
	printf("%lld", ans);
    return 0;
}

单调队列

详情见：单调队列 - OI Wiki

单调队列是一种用于维护滑动窗口最值的数据结构，支持以下操作：

  1. 维护窗口范围：确保队列中的元素都在当前窗口内。
  2. 维护单调性：确保队列中的元素按照某种单调性（递增或递减）排列。

单调队列的实现

1. 初始化

  • 使用数组 dq 模拟队列，hh 和 tt 分别表示队首和队尾的下标。
  • 初始化 hh = 1，tt = 0，表示队列为空。
1
ll dq[N], hh = 1, tt = 0;

2. 维护窗口范围

  • 检查队首元素是否在当前窗口内，如果不在则出队。
1
while(hh <= tt && dq[hh] < i - k) hh++;

3. 维护单调性

  • 检查队尾元素是否小于当前元素，如果是则出队，确保队列的单调性。
1
while(hh <= tt && dp[i] >= dp[dq[tt]]) tt--;

4. 入队操作

  • 将当前元素的下标入队。
1
dq[++tt] = 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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;

int n, k, dq[N], a[N];

int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    int hh = 1, tt = 0;
    // 维护的是 [i - k + 1, i]这个区间的最值
    for(int i = 1;i <= n;i ++)
    {
        // 1.维护队首下标的合法性
        while(hh <= tt && dq[hh] < i - k + 1) hh ++;
        // 2.维护队尾值的优越性(存储最小值)
        while(hh <= tt && a[dq[tt]] >= a[i]) tt --;
        // 3.存储当前值的下标
        dq[++ tt] = i;
        // 4.输出窗口的最值（这里是最小值）
        if(i >= k) cout << a[dq[hh]] << ' ';
	}
    // 5.清空队列（数组模拟的优势O(1)）
    hh = 1, tt = 0;
    
    return 0;
}

STL 双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 使用STL标准库进行单调队列 --- <deque> (双端队列)*/
#include <bits/stdc++.h>
using namespace std;
const int N  = 2e5 + 5;

int a[N], n, k;
deque<int> dq;

int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    
    for(int i = 1;i <= n;i ++)
    {
        while(dq.size() && dq.front() < i - k + 1)dq.pop_front();
        while(dq.size() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push(i);
        if(i >= k) cout << a[dq.front()] << ' ';
	}
    while(dq.size()) dq.pop_front(); // 时间复杂度为O(n)
    return 0;
}

例题：

image-20250401203851116

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1e5 + 10;

int n, k;
int a[N];
// 数组模拟队列
int q1[N], q2[N];
int h1 = -1, t1 = 0;
int h2 = -1, t2 = 0;
int dpmin[N], dpmax[N];

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	
	for(int i = 1;i <= n;i ++)
	{
		// 维护下标合法性
		while(h1 <= t1 && q1[h1] <= i - k) h1 ++;
		while(h2 <= t2 && q2[h2] <= i - k) h2 ++;
		// 维护单调性（单调递增）队头是最小值
		// 只要队尾比a[i]还大就让出位置将a[i]插入到这个队列中
		// 实际上这个循环是在给更小的元素让位置
		while(h1 <= t1 && a[q1[t1]] >= a[i]) t1 --;
		q1[++ t1] = i;
		// 单调递减,队头是最大值
		while(h2 <= t2 && a[q2[t2]] <= a[i]) t2 --;
		q2[++ t2] = i;
		dpmin[i] = a[q1[h1]];
		dpmax[i] = a[q2[h2]];
	}
	
	for(int i = k;i <= n; i ++) printf("%d ", dpmin[i]);
	puts("");
	for(int i = k;i <= n; i ++) printf("%d ", dpmax[i]);
    return 0;
}

子矩阵（2023 单调队列省赛真题）

image-20250401215850311

  • 这个思维就是使用二维滑动窗口来优化这个问题，我们先对每一行求出对应的滑动窗口的最值，再竖着切一刀对每一列求出最值，然后控制每一行和每一列的滑动窗口的最值，就可以求出一个二维的滑动窗口的最值
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1010;
const int M = 1e6;
const int p = 998244353;

int n, m, a, b;
int g[N][N];
int q[M];
int hh = 0, tt = -1;

int line_max[N][N]; // line_max[i][j - b + 1] 表示第i行以j下标处为起点大小为b的滑动窗口的最大值
int line_min[N][N]; // 最小值同理

int maxv[N][N];   // maxv[i][j] 表示左上角为[i, j]的唯一的矩阵的最大值
int minv[N][N];   // 最小值同理
int main()
{
	scanf("%d%d%d%d", &n, &m, &a, &b);
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= m;j ++)
			scanf("%d", &g[i][j]);
	
	// 求最大值
	
	// 求每一行的最大值
	for(int i = 1;i <= n;i ++)
	{
		hh = 0, tt = -1;
		for(int j = 1;j <= m;j ++)
		{
			while(hh <= tt && q[hh] < j - b + 1) hh ++;
			while(hh <= tt && g[i][q[tt]] <= g[i][j]) tt --;
			q[++ tt] = j;
			if(j - b + 1 >= 0) line_max[i][j - b + 1] = g[i][q[hh]];
		}
	}
	
	// 对每一行的滑动窗口再求一遍滑动窗口
	for(int j = 1;j <= m;j ++)
	{
		hh = 0, tt = -1;
		for(int i = 1;i <= n;i ++)
		{
			while(hh <= tt && q[hh] < i - a + 1) hh ++;
			while(hh <= tt && line_max[q[tt]][j] <= line_max[i][j]) tt --;
			q[++ tt] = i;
			if(i - a + 1 >= 0) maxv[i - a + 1][j] = line_max[q[hh]][j];
		}
	}
	
	// 求最小值
	// 求每一行的最小值
	for(int i = 1;i <= n;i ++)
	{
		hh = 0, tt = -1;
		for(int j = 1;j <= m;j ++)
		{
			while(hh <= tt && q[hh] < j - b + 1) hh ++;
			while(hh <= tt && g[i][q[tt]] >= g[i][j]) tt --;
			q[++ tt] = j;
			if(j - b + 1 >= 0) line_min[i][j - b + 1] = g[i][q[hh]];
		}
	}
	
	// 对每一行的滑动窗口再求一遍滑动窗口
	for(int j = 1;j <= m;j ++)
	{
		hh = 0, tt = -1;
		for(int i = 1;i <= n;i ++)
		{
			while(hh <= tt && q[hh] < i - a + 1) hh ++;
			while(hh <= tt && line_min[q[tt]][j] >= line_min[i][j]) tt --;
			q[++ tt] = i;
			if(i - a + 1 >= 0) minv[i - a + 1][j] = line_min[q[hh]][j];
		}
	}
	
	long long ans = 0;
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= m;j ++)
		{
			ans += (maxv[i][j] * minv[i][j] % p) % p;
		}
	printf("%lld", ans);
    return 0;
}

游戏(2023 国赛真题单调队列)

image-20250401221730871

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 <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1e5 + 10;

int n, k;
int a[N];
int q[N];
int hh = 0, tt = -1;
int maxi[N], mini[N];

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	
	for(int i = 1;i <= n;i ++)
	{
		while(hh <= tt && q[hh] <= i - k) hh ++;
		while(hh <= tt && a[i] >= a[q[tt]]) tt --;
		q[++ tt] = i;
		if(i >= k) maxi[i] = a[q[hh]];
	}
	hh = 0, tt = -1;
	for(int i = 1;i <= n;i ++)
	{
		while(hh <= tt && q[hh] <= i - k) hh ++;
		while(hh <= tt && a[i] <= a[q[tt]]) tt --;
		q[++ tt] = i;
		if(i >= k) mini[i] = a[q[hh]];
	}
	
	double sum = 0;
	int cnt = n - k + 1;
	for(int i = k;i <= n;i ++)
	{
		sum += maxi[i] - mini[i];
	}
	printf("%.2lf", sum / cnt);
    return 0;
}
  • 注意我们会有几个滑动窗口，要记录完整的滑动窗口