蓝桥杯算法竞赛笔记（杂）

本文整理了蓝桥杯竞赛中常用的算法和数据结构知识点，包括前缀和、差分、双指针、二分法、位运算、递归以及常见排序算法等内容。

1.前缀和

1.1前缀和原理和特点

表示前缀和，前缀和 由一个用户输入的数组生成。

对于一个数组 （下标从1开始），我们定义一个前缀和数组 ,满足：

有一个重要的特征，可用于快速生成 ：

可以的求数组 的一段区间的和：

但是注意， 是一种预处理算法，只适用于a数组为静态数组的情况，即a数组中的元素在区间和查询过程中不会进行修改。

如果需要实现 “先区间修改，再区间查询” 可以使用差分数组，如果需要 “一边修改，一边查询” 需要使用树状数组或线段树等数据结构。

1.2实现前缀和

利用前面讲过的特性：

我们的数组下标均从1开始， ,从前往后循环计算即可。

1
2
3
for (int i = 1,i <= n; i++) {
    prefix[i] = prefix[i - 1] + a[i];
}

求区间和：

2.差分

2.1差分的原理和特点

对于一个数组 ,差分数组 的定义是：

对差分数组做前缀和可以还原为原数组：

利用差分数组可以实现快速的区间修改，下面是将区间 都加上 的方法：

1
2
diff[l] += x;
diff[r + 1] -= x;

在修改完成后，需要做前缀和恢复为原数组，所以上面这段代码的含义是：

表示将区间 都加上 ，但是 我们并不想加 所以再将 减去 即可。

但是注意，差分数组不能实现 “边修改边查询” 需要使用树状数组、线段树等数据结构。

2.2差分的实现

直接用循环实现即可，注意这里建议使得 ,下标从1开始。

1
2
3
for (int i = 1;i <= n;i ++) {
    diff[i] = a[i] - a[i-1];
}

将区间 都加上 ：

1
2
diff[l] += x;
diff[r + 1] -= x;

3.双指针

3.1双指针简介

双指针常用于数组或字符串中进行快速查找、匹配、排序或移动操作。

双指针并非真的使用指针实现，一般用两个变量来表示下标（在后面都用指针来表示）。

双指针算法使用两个指针在数据结构上进行迭代，并根据问题的要求移动这些指针。

双指针往往也和单调性、排序联系在一起，在数组区间问题上，暴力法的时间复杂度往往是的，但是双指针利用单调性可以优化到。

3.2对撞指针

两个指针 、 分别指向序列的第一个元素和最后一个元素。

然后l指针不断递增， 不断递减，直到两个指针的值相撞或错开，或满足其他要求的 特殊条件为止。

对撞指针一般用来解决有序数组或者字符串问题。

查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。

字符串反串问题：反串字符串、回文数、颠倒二进制等问题。

3.3快慢指针

两个指针从同一侧开始遍历序列，而且移动的步长一个快一个慢。

快指针为 ，满指针为 ，这样构成的区间

两个指针以不同的速度、不同的策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他条件时为止。

4.二分法

4.1二分法简介

二分法是一种高效的查找方法，它通过将问题的搜索范围一分为二（两边具有明显的区别），迭代地缩小搜索范围，直到找到目标或者确定目标不存在。

二分法适用于有序数据集合，并且每次迭代可以将搜索范围缩小一半。

二分法本质上也是枚举，但是和暴力枚举不同，二分法利用数据结构的单调性减小了很多不必要的枚举，从而极大地提高了效率，一般可以将的枚举优化到。

常见的二分法：整数二分、浮点数二分、二分答案。

解题步骤：

  1. 研究并发现数据结构（或答案变量）的单调性。

  2. 确定最大区间，确保分界点一定在里面，具体有一些细节：若以 作为答案， 那么答案区间在 ，若以 作为答案，那么答案区间在 。

  3. 确定函数，一般为传入（区间中某个下标），返回mid所属区域或返回一个值，当函数较简单时可以直接判断。

  4. 计算中点，用判断该移动l或r指针，具体移动哪个需要根据单调性以及要求的答案来判断。

  5. 返回 或 ，根据题意判断。

4.2整数二分

整数二分就是在一个已有的有序数组上，进行二分查找，一般为找出某个值的位置，或者是找出分界点。

这个数组肯定是开的下的，其数组大小一般在 以内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//找到升序数组a中的x第一次出现的位置
int l = 0, r = 1e9;
//注意这里的判断条件，这样可以保证l，r最终一定收敛到分界点
while (l + 1 != r) {
    int mid = (l + r) / 2;
    //如果a为升序，说明mid偏大了，需要减小mid，就只能将r变小，即r = mid
    if (a[mid] >= x) {
        r = mid;
    }
    else {
        l = mid;
    }
    cout << r << '\n';
}

4.3浮点二分

浮点二分不再是在有序数组上做二分查找，而是在某个实数范围内进行查找，因为实数域本身是单调的，所以也满足单调性，和整数二分的主要区别在于使用的变量类型、退出的判断条件不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e-6;
//注意这里的判断条件，这样可以保证l，r最终一定收敛到分界点
while (r - l >= eps) {
    double mid = (l + r) / 2;
    //f(x)单调递增，f(mid) >= 0,说明mid偏大了,需要减小mid,就只能将r变小，即r = mid
    if(f(mid) > 0) {
        r = mid;
    }
    else {
        l = mid;
    }
    //最后返回l，r差别不大
    cout << r << '\n';
}

4.4二分答案

二分答案是二分法中最常见也是最重要的题型，考察的比较灵活，需要选手从题目中发现某个单调的函数，然后对其二分。

常见的模型是：

二分框架（时间复杂程度）+ 函数（时间复杂度）

一般情况下，我们会将答案进行二分，然后在枚举出某个可能解后判断其是否可以更优或者是否合法，从而不断逼近最优解。

二分答案的题的特性：如果已知某个答案，很容易判断其是否合法或更优。某些贪心问题可能可以转化成二分答案问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool check (int mid) {
    bool res = true;
    //do something to check the authority of mid...
    return res;
}

int main () {
    int l = 0, r = 1e9;
    while (l + 1 != r) {
        int mid = (l + r) / 2;
        //具体写法需要根据题意修改
        if (check(mid)) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    cout << l << '\n';
}

5.位运算

5.1位运算概述

在现代计算机中，所有数据都以二进制形式存储，即 0 和 1 两种状态。计算机对二进制数据进行的运算（如加、减、乘、除）被称为位运算，即对二进制数的每一位进行操作的运算。

为了更好地理解位运算，举个简单的例子：假设我们有如下代码进行两个整数的加法运算：

1
2
3
int a = 35;
int b = 47;
int c = a + b;

计算机会将这两个整数转换为二进制形式，然后进行加法运算：

1
2
3
4
35:  0010 0011
47:  0010 1111
----------------
82:  0101 0010

因此，与直接使用 +、-、*、/ 运算符相比，合理运用位运算可以显著提高代码在机器上的执行效率。

5.2位运算概览

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
| 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，高位补0或符号位补齐

5.3按位与运算符（&）

定义：对参与运算的两个数据的二进制位进行”与”运算。

运算规则：

1
2
3
4
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

总结：只有两位同时为1时，结果才为1，否则结果为0。

例如：3 & 5 即 0000 0011 & 0000 0101 = 0000 0001，因此 3 & 5 的值为1。

注意：负数按补码形式参与按位与运算。

用途：

  1. 清零：如果想将一个单元清零，只要与一个各位都为零的数值相与，结果为零。
  2. 取一个数的指定位：例如，取数 X = 1010 1110 的低4位，只需另找一个数 Y = 0000 1111，然后 X & Y = 0000 1110 即可得到 X 的指定位。
  3. 判断奇偶：通过判断最未位是0还是1来决定奇偶，可以用 if ((a & 1) == 0) 代替 if (a % 2 == 0) 来判断 a 是否为偶数。

5.4按位或运算符（|）

定义：对参与运算的两个对象的二进制位进行”或”运算。

运算规则：

1
2
3
4
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

总结：只要有一个为1，其值为1。

例如：3 | 5 即 0000 0011 | 0000 0101 = 0000 0111，因此 3 | 5 的值为7。

注意：负数按补码形式参与按位或运算。

用途：

  1. 设置某些位为1：例如，将数 X = 1010 1110 的低4位设置为1，只需另找一个数 Y = 0000 1111，然后 X | Y = 1010 1111 即可得到。

5.5异或运算符（^）

定义：对参与运算的两个数据的二进制位进行”异或”运算。

运算规则：

1
2
3
4
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

总结：相应位相同为0，相异为1。

性质：

  1. 交换律
  2. 结合律： (a ^ b) ^ c == a ^ (b ^ c)
  3. 对于任何数 x，都有 x ^ x = 0，x ^ 0 = x
  4. 自反性：a ^ b ^ b = a ^ 0 = a

用途：

  1. 翻转指定位：例如，将数 X = 1010 1110 的低4位翻转，只需另找一个数 Y = 0000 1111，然后 X ^ Y = 1010 0001 即可得到。
  2. 与0相异或值不变：例如 1010 1110 ^ 0000 0000 = 1010 1110
  3. 交换两个数：
1
2
3
4
5
6
7
void Swap(int &a, int &b) {
	if (a != b) {
    	a ^= b;
   		b ^= a;
    	a ^= b;
	}
}

5.6取反运算符（~）

定义：对参与运算的一个数据的二进制位进行”取反”运算。

运算规则：

1
2
~1 = 1111 1110
~0 = 1111 1111

即：

1
2
~1 = -2
~0 = -1

总结：将 0 变 1，1 变 0。

用途：

  1. 使一个数的最低位为零：例如，使 a 的最低位为0，可以表示为：a & ~1。~1 的值为 1111 1111 1111 1110，再按”与”运算，最低位一定为0。

5.7左移运算符（<<）

定义：将一个运算对象的各二进制位全部左移若干位，高位丢弃，低位补0。

例如，设 a = 1010 1110，a = a << 2 将 a 的二进制位左移2位、右补0，即得 a = 1011 1000。

若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

5.8右移运算符（>>）

定义：将一个数的各二进制位全部右移若干位，高位补0或补符号位，右边丢弃。

例如，a = a >> 2 将 a 的二进制位右移2位，左补0 或补符号位，具体取决于数的正负。

操作数每右移一位，相当于该数除以2。

5.9位运算技巧

x & l：结果为 说明为奇数，为 说明为偶数。

x >> i & l：结果为 的二进制表示中的第 位。

x | (l << i)：将 的第 位或上 ，则 变为 ，其他位上或上 没有影响。

修改为 就类似地用与运算即可，就是构造出只有第 位为 ，其他位都为 的一个二进制数然后和 做与运算。

x & (x - 1)：如果 为 的幂次方，则 的二进制表示中只有一个 ， 就有很多个连续的 并且和 的 没有交集，两者与运算一定为 ，可以证明其他情况必然不为 。

lowbit (x) = x & -x：如果 ，则 。

常用于数据结构树状数组中。

6.递归

6.1递归的介绍

概念：递归是指函数直接或者间接调用自身的过程。

解释递归的两个关键要素：

基本情况（递归终止条件）：递归函数中的一个条件，当满足该条件时，递归终止，避免无限递归。可以理解为直接解决极小规模问题的方法。

递归表达式（递归调用）：递归函数中的语句，用于解决规模更小的子问题，再将子问题的答案合并成为当前问题的答案。

6.2递归如何实现

递归函数的基本结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
返回类型 函数名 (参数列表) {
    //基本情况(递归终止条件)
    if (满足终止条件) {
        //返回终止条件下的结果
    }
    //递归表达式，(递归调用)
    else {
        //将问题分解为规模更小的子问题
        //使用递归调用解决子问题
        //返回子问题的结果
    }
}

实现过程：

1.将大问题分解为规模更小的子问题。

2.使用递归调用解决每个子问题。

3.通过递归终止条件来结束递归。

设计时需注意的细节：

1.确保递归一定能到递归出口，避免无限递归，这可能导致TLE（超时）、MLE（超内存）或RE（运行错误）。

2.考虑边界条件，有时候递归出口不止一个。

3.避免不必要的重复计算，尽可能优化递归函数的性能（例如使用记忆化）。

6.3递归和循环的比较

递归的特点：

1.直观、简洁，易于理解和实现。

2.适用于问题的规模可以通过递归调用不断减小的情况。

3.可以处理复杂的数据结构和算法，如树和图的遍历。

4.存在栈溢出的风险（栈空间一般只有 ,所以递归层数不宜过深，一般不超过 蹭层）。

循环的特点：

1.直接控制流程，效率较高。

2.适用于问题的规模没有明显的缩减，或者需要特定的迭代次数。

3.适合处理大部分的动态规划问题。

部分情况下，递归和循环可以相互转化。

7.冒泡排序

7.1冒泡排序的思想

冒泡排序的思想是每次将最大的一下一下运到最右边，然后将最右边这个确定下来。

再来确定第二大的，再确定第三大的…

对于数组 ，具体的来说，每次确定操作就是从左往右扫描，如果 ,我们就执行 将两项交换，然后再往右检查，这样可以找出最大的并将其丢到最右边。

第一次确定操作是将 中最大的放到 ;

第二次确定操作是将 中最大的放到 。

以此类推（类似的，如果你想把最小的放到最左边也是可以的），时间复杂度为

由于排序过程中，数字像冒泡泡一样从左往右换过去，故名冒泡排序。

7.2冒泡排序的实现

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

using namespace std;

const int N = 1e3 + 9;
int a[N];

int main () {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i ++) {
        cin >> a[i];
    }
    
    //i表示当前要确定的位置
    for (int i = n;i >= 1;i --) {
        
        //j从左往右扫
        for (int j = 1;j <= i - 1;j ++) {
            if (a[j] > a[j + 1]) {
                swap(a[j],a[j + 1]);
            }
        }
    }
    
    //输出
    for (int i = 1;i <= n;i ++) {
        cout << a[i] << "\n";
    }
    
    return 0;
}

8.选择排序

8.1选择排序的思想

选择排序的思想和冒泡排序类似，是每次找出最大的然后直接放到右边对应位置，然后将最右边这个确定下来（而不是一个一个地交换过去）。

再来确定第二大的，再确定第三大的…

对于数组 ,具体的来说，每次操作（假设当前要确定的是 位置）就是从左往右扫描，计算出最大元素的下标 ,最后一次执行 将两项交换即可。

第一次确定操作是将 中最大的放到 ;

第二次确定操作是将 中最大的放到 。

以此类推（类似的，如果你想先把最小的放在左边也是可以的），时间复杂度为

8.2选择排序的实现

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 <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 9;
int a[N];

int main () {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i ++) {
        cin >> a[i];
    }
    
    //i表示当前要确定的位置
    for (int i = n;i >= 1;i --) {
        int max_id = 1;//初始化为1
        //j从左往右扫描出max_id
        for (int j = 1;j <= i;j ++) {
            if (a[j] > a[max_id]) {
                max_id = j;
            }
        }
        swap (a[max_id],a[i]);
    }
    
    //输出
    for (int i = 1;i <= n;i ++) {
        cout << a[i] << "\n";
    }
    
    return 0;
}

9.插入排序

9.1插入排序的思想

插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素逐个插入到已排序序列的合适位置中，使得已排序序列逐渐扩大，从而逐步构建有序序列，最终得到完全有序的序列。

它类似于我们打扑克牌时的排序方式，将一张张牌插入到已经有序的手牌中。

时间复杂度为

9.2插入排序的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//i表示当前要确定的位置
for (int i = 2;i <= n;i ++) {
    //此时[1，i - 1]已经为有序的数组
    
    int val = a[i], j;
    
    //将val和a[j - 1]比较
    //如果val < a[j - 1]就将a[j - 1]往后移动一格
    //给val留出位置
    for (j = i;j > 1 && val < a[j - 1];j --) {
        a[j] = a[j - 1];
    }
    //当循环跳出时，j = 1或val >= a[j],且此时a[j]已经往后移动
    //此时的j为给val腾出位置
    a[j] = val;
}

10.快速排序

10.1快速排序的思想

快速排序是一种基于分治法的排序方法，原理是将一个数组分成两个子数组，其中一个子数组的所有元素都小于另一个子数组的元素，然后递归地对这两个子数组进行排序。

快速排序的思想是通过不断地将数组分成两个子数组，递归地对子数组进行排序，最终得到一个有序的数组。这个过程通过选择合适的基准和分区操作来实现。

快速排序拥有更好的时间复杂度 ,且不需要额外空间。

10.2快速排序的实现

1
2
3
4
5
6
7
void QuickSort (int a[],int l,int r) {
    if (l < r) {
        int mid = Partition (a,l,r);
        QuickSort (a,l,mid - 1);
        QuickSort (a,mid + 1,r);
    }
}

这是快速排序的递归主体 。传入参数为要排序的数组和区间的左右端点。

函数会将数组这个区间中某个基准数字放到正确的位置并将这个位置返回。

在确定了 的位置之后，可以保证 都 ,于是只需要将左右两边分别向下递归地排序即可。

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
int partition (int a[],int l,int r) {
    //设a[r]为基准，这一次partition会将a[r]放到正确位置上
    int pivot = a[r];
    //设两个下标i，j分别从l，r开始往中间走
    int i = l,j = r;
    while (i < j) {
        while (i < j && a[i] <= pivot) {
            i ++;
        }
        //从上面循环出来后有i >= j 或 a[i] > pivot(说明找到了需要交换的位置)
        
        while (i < j && a[j] >= pivot) {
            j --;
        }
        //从上面循环出来后有i >= j 或 a[j] > pivot(说明找到了需要交换的位置)
        
        //如果i < j说明存在a[j] < pivot,否则就是a[r] <= pivot,a[i] >= pivot
        if (i < j) {
            swap (a[i],a[j]);
        }
        else {
            swap (a[i],a[r]);
        }
    }
    return i;
}

这是 函数 （分区函数），用于将比 小的放到左边，大的放到右边，最后返回 所处的位置。

11.后缀表达式

后缀表达式的处理过程如下：扫描后缀表达式，凡遇到操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。