蓝桥杯
馨er BOSS
  2022-02-24 01:57:56 2022-02-24 01:57      4.5k 字  19 分钟

acwing蓝桥杯班

1 教学计划与递归

1.1 由数据范围反推算法复杂度以及算法内容

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 $10^7 \sim 10^8$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

  1. $n \le 30$：指数级别, dfs+剪枝，状态压缩dp
  2. $n \le 100$ => $O(n^3)$：floyd，dp，高斯消元
  3. $n \le 1000$ => $O(n^2)$，$O(n^2logn)$：dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
  4. $n \le 10000$ => $O(n * \sqrt n)$：块状链表、分块、莫队
  5. $n \le 100000$ => $O(nlogn)$：各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
  6. $n \le 1000000$ => $O(n)$：以及常数较小的 $O(nlogn)$ 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra、spfa
  7. $n \le 10000000$ => $O(n)$：双指针扫描、kmp、AC自动机、线性筛素数
  8. $n \le 10^9$ => $O(\sqrt n)$：判断质数
  9. $n \le 10^{18}$ => $O(logn)$：最大公约数，快速幂，数位DP
  10. $n \le 10^{1000}$ => $O((logn)^2)$：高精度加减乘除
  11. $n \le 10^{100000}$ => $O(logk \times loglogk)，k表示位数$：高精度加减、FFT/NTT

注：这里的log指的是以2为底的对数；

1.2 常用的头文件

1
2
3
4
5
6
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>

1.3 关于输入输出

输入输出规模较大的问题，推荐用scanf，printf；规模较小的问题，用cin，cout较为简洁

1.4 递归

  • 递归即自己调用自己

所有递归 ⇒ 递归搜索树

img

例：斐波那契数列

设 f(n) = {1，2，3，5，8，……}

n = 1，f(1) = 1；n = 2，f(2) = 1；n ⩾ 3，f(n) = f(n−1) + f(n−2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n - 1) + f(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;
}

1.5 例题

92. 递归实现指数型枚举

题目

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1⩽n⩽15

输入样例

1
3

输出样例

1
2
3
4
5
6
7
3
2
2 3
1
1 3
1 2
1 2 3

思路

  • 数据范围为1⩽n⩽15，所以可以用时间复杂度为$O(2^n)$的算法来做；
  • 对于1∼n这n个数，每个数有 选/不选 两种情况，所以总共的方案数即为$2^n$，又因为输出方案（方案长度最多为 n），故总的时间复杂度为$O(n2^n)$；
  • 递归（即DFS），最重要的是顺序，即找一个顺序，可以把所有方案不重不漏地找出来；
  • 从1∼n，依此考虑每个数 选/不选；

例：n=3时的递归搜索树

  • 状态（即每个数 选/不选）可以开一个长度为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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 15;

int n;
int st[N];  // 状态，记录每个位置当前的状态，0表示没考虑，1表示已选，2表示没选

void dfs(int u) {
    if (u > n) {
        for (int i = 1; i <= n; i++)
            if (st[i] == 1)
                printf("%d ", i);
        printf("\n");
        return;
    }
    st[u] = 2;
    dfs(u + 1);  // 第一个分支，不选
    st[u] = 0;  // 恢复现场

    st[u] = 1;
    dfs(u + 1);  // 第二个分支，选
    st[u] = 0;  // 恢复现场
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}
/*
运行时间： 32 ms
运行空间： 856 KB 
*/

如果要将方案记录下来

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

using namespace std;

const int N = 16;
int n;
int st[N];  // 状态：记录每个位置当前的状态，0表示还没考虑，1表示选它，2表示不选它
vector<vector<int>> ways;  //ways代表方案
void dfs(int u) {
    if (u > n) {
        vector<int>way;
        for (int i = 1; i <= n; ++i) //记录方案
            if (st[i] == 1)
                way.push_back(i);
        ways.push_back(way);
        return;
    }
    st[u] = 2;
    dfs(u + 1);
    st[u] = 0;

    st[u] = 1;
    dfs(u + 1);
    st[u] = 0;
}
int main() {
    cin >> n;
    dfs(1);
    for (int i = 0; i < ways.size(); ++i) {
        for (int j = 0; j < ways[i].size(); ++j)
            printf("%d ", ways[i][j]);
        puts("");
    }
    return 0;
}
/*
运行时间： 89 ms
运行空间： 3084 KB
*/

94. 递归实现排列型枚举

题目

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n。

输出格式

按照从小到大的顺序输出所有方案，每行 1个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1⩽n⩽9

输入样例

1
3

输出样例

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

思路

  • 数据范围为1⩽n⩽9，9!=326880，因此时间复杂度大约为O(n×n!)⇒DFS；

字典序：

A:a1,a2,⋯,an

B:b1,b2,⋯,bm

ai<bi 或 ai不存在但bi存在 ⇒A<B

ai>bi 或 bi不存在但ai存在 ⇒A>B

n=m并且an=bm⇒A=B

  • 全排列问题一般有两种枚举方式：

    1.依此枚举每个数放哪个位置；

    2.依此枚举每个位置放哪个数；

对2.的例：n=3时的递归搜索树

image-20220223023705361

上图保证了（相对意义上的）左子树的方案 字典序一定小于 右子树的方案；

  • 开一个长度为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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 10;
int n;
int state[N];  // 0表示还没放数，1~n表示放了哪个数
bool used[N];  // true表示用过，false表示还没用过

void dfs(int u) {
    if (u > n) {  // 边界
        for (int i = 1; i <= n; i++)
            printf("%d ", state[i]);  // 打印方案
        puts("");
        return;
    }
    // 依次枚举每个分支，即当前位置可以填哪些数
    for (int i = 1; i <= n; i++)
        if (!used[i]) {
            state[u] = i;
            used[i] = true;
            dfs(u + 1);
            // 恢复现场
            state[u] = 0;
            used[i] = false;
        }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}
/*
运行时间： 373 ms
运行空间： 7000 KB 
*/

分析时间复杂度

  • 需要递归n层；
  • 第一层时间复杂度为O(n)；（一个for循环）
  • 第二层时间复杂度为O(n×n)；（由第一层衍生出n个分支，每个分支一个for循环）
  • 第三层时间复杂度为O(n×n−1×n)；（由第二层衍生出n−1个分支）
  • ⋯⋯
  • 倒数第二层时间复杂度为O(n!×n)；
  • 最后一层时间复杂度为O(n!×n)；（最后一层有n!个结点，且需要输出方案）

总的时间复杂度为O[n(1+n+n(n−1)+n(n−1)(n−2)+⋯+n!)]

相当于P0n+P1n+P2n+⋯+Pnn⩾n!

原式相当于：

n(n!+n!1+n!1×2+n!1×2×3+⋯n!(n−1)!)

对其进行放缩：

原始⩽n(n!+n!1+n!2+n!4+n!8⋯n!(n−1)!)⩽n×n!(1+1+12+14+18+⋯)⩽3n!

故整个时间复杂度小于等于O(n×n!)

717. 简单斐波那契

题目

以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。

这个数列从第 3 项开始，每一项都等于前两项之和。

输入一个整数 N，请你输出这个序列的前 N 项。

输入格式

一个整数 N。

输出格式

在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。

数据范围

0 < N < 46

输入样例：

1
5

输出样例：

1
0 1 1 2 3

代码

注意一下条件判断，否则会超时

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

const int N = 50;
int n;
long long st[N] = { 0, 1, 1, 2, 3, 5, 8, 13, 21 };
long long dfs(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (st[n] == 0)
        st[n] = dfs(n - 1) + dfs(n - 2);
    return st[n];
}
int main() {
    cin >> n;
    dfs(n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", st[i]);
    printf("\n");
    return 0;
}

95. 费解的开关

题目

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

1
2
3
4
5
10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

1
2
3
4
5
01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

1
2
3
4
5
01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

数据范围

0<n≤500

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

1
2
3
3
2
-1

代码

1

1.6 习题

93. 递归实现组合型枚举

题目

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式

两个整数 n,m,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0,
0≤m≤n ,
n+(n−m)≤25

输入样例：

1
5 3

输出样例：

1
2
3
4
5
6
7
8
9
10
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

思考题：如果要求使用非递归方法，该怎么做呢？

思路

  • 画递归树：依次枚举每个位置的数是多少

  • 不重复，人为规定顺序（限制从小到大排序）=> 局部 => 只需保证每次新加的数大于前面的一个数

  • 树 => dfs 参数：(1)三个位置：way[N]；(2)当前枚举到哪个位置，形参u；(3)start 当前最小可以从哪个数枚举

代码

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

using namespace std;

int n, m;
const int N = 30;
int way[N];

void dfs(int u, int start) {
    if (u > m) {
        for (int i = 1; i <= m; i++)
            printf("%d ", way[i]);
        printf("\n");
        return;
    }
    for (int i = start; i <= n; i++) {
        way[u] = i;
        dfs(u + 1, i + 1);
        way[u] = 0; // 恢复现场
    }
}

int main() {
    cin >> n >> m;
    dfs(1, 1);
    return 0;
}
/*
	运行时间182ms
*/

剪枝优化

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

using namespace std;

int n, m;
const int N = 30;
int way[N];

void dfs(int u, int start) {
    if (u - 1 + n - start + 1 < m)  // 剪枝
        return;
    if (u > m) {
        for (int i = 1; i <= m; i++)
            printf("%d ", way[i]);
        printf("\n");
        return;
    }
    for (int i = start; i <= n; i++) {
        way[u] = i;
        dfs(u + 1, i + 1);
        way[u] = 0; // 恢复现场
    }
}

int main() {
    cin >> n >> m;
    dfs(1, 1);
    return 0;
}
/*
	运行时间60ms
*/

1209.带分数

题目

100 可以表示为带分数的形式：100=3+69258/714

还可以表示为：100=82+3546/197

注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围

1≤N<106

输入样例1：

1
100

输出样例1：

1
11

输入样例2：

1
105

输出样例2：

1
6

思路

  • 暴力枚举搜索方案：枚举全排列；枚举a，b的位数（即a，b，c的位数）；判断等式是否成立

    n=a+b/c

  • 优化：cn=ca+b

    枚举a，枚举c，枚举b是否成立（嵌套的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
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
#include<iostream>
#include<cstring>

using namespace std;

int n;
const int N = 20;
bool st[N], backup[N];
int ans;

bool check(int a, int c) {
    int b = n * c - a * c;
    if (!a || !b || !c) return false;
    memcpy(backup, st, sizeof(st));  // 把st数组的值复制到backup数组中去
    while (b) {
        int x = b % 10;  // 取个位
        b /= 10;  // 把个位删掉
        if (!x || backup[x]) return false;
        backup[x] = true;
    }
    for (int i = 1; i <= 9; i++)
        if (!backup[i])
            return false;
    return true;
}

void dfs_c(int u, int a, int c) {
    if (u == n) return;
    if (check(a, c)) ans++;
    for(int i = 1; i <= 9; i++)
        if (!st[i]) {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
}

void dfs_a(int u, int a) {
    if (a >= n) return;
    if(a) dfs_c(u, a, 0);
    for (int i = 1; i <= 9; i++)
        if (!st[i]) {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;
        }
}

int main() {
    cin >> n;
    dfs_a(0, 0);  // 枚举了几个数，a的值
    cout << ans << endl;
    return 0;
}

116.飞行员兄弟

题目

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。

但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 N，表示所需的最小切换把手次数。

接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤4

输入样例：

1
2
3
4
-+--
----
----
-+--

输出样例：

1
2
3
4
5
6
7
6
1 1
1 3
1 4
4 1
4 3
4 4

代码

1

1208. 翻硬币

题目

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数

数据范围

输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

1
2
**********
o****o****

输出样例1：

1
5

输入样例2：

1
2
*o**o***o***
*o***o**o***

输出样例2：

1
1

代码

1

2 二分和前缀和

2.1 二分

思想：

  • 确定一个区间，使得目标值一定在区间中
  • 找一个性质，满足：性质具有二段性；答案是二段性的分界点

整数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 区间[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;
        else l = mid + 1;
    }
    return 1;
}

// 区间[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;
    }
}

浮点数二分

1
2
3
4
5
6
7
8
9
double bsearch_3(double l, double r){
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    return 0;
}
  • 浮点数二分不需要考虑mid是否+1，else后是否+1。
  • 没有固定的浮点数序列，因此要考虑精度eps，一般比题目要求多1位小数就行
  • 需要自己确定l和r的值，即查找范围

2.2 前缀和

3 数学和简单DP

4 枚举、模拟与排序

5 树状数组与线段树

6 双指针、BFS与图论

7 贪心

8 数论

9 复杂DP

10 疑难杂题

  • 本文标题：蓝桥杯
  • 本文作者：馨er
  • 创建时间：2022-02-24 01:57:56
  • 本文链接：https://sjxbbd.vercel.app/2022/02/24/f1b89dd2c45c/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！