蓝桥杯C++组算法知识点整理 · 考前突击（上）【小白适用】

【背景说明】本文的作者是一名算法竞赛小白，在第一次参加蓝桥杯之前希望整理一下自己会了哪些算法，于是有了本文的诞生。分享在这里也希望与众多学子共勉。如果时间允许的话，这一系列会分为上中下三部分和大家见面，祝大家竞赛顺利！

【文风说明】本文主要会用代码＋注释的方式来解释内容。相信学过编程的人都会发现程序比长篇大论更易理解！

目录

一、语言基础

1.1 编程基础

1.2 竞赛常用库函数

1.2.1 sort 函数

1.2.2 最值查找

1.2.3 二分查找

1.2.4 大小写转换

1.2.5 全排列

1.2.6 其它库函数整理

1.3 STL的用法

1.3.1 pair

1.3.2 vector

1.3.3 stack和queue

1.3.4 set

1.3.5 map

二、基础算法

2.1 递归算法

2.2 前缀和

 2.3 差分

 2.4 贪心算法

 2.5 双指针

2.5.1 对撞指针

2.5.2 快慢指针

 2.6 位运算

---

一、语言基础

1.1 编程基础

        既然准备参加蓝桥杯竞赛，并且考虑到每年蓝桥杯的比赛时间在春季，那么本文读者想必至少学过一门编程语言基础课。作者学校安排的课程是 C 语言，因此准备比赛的时候对于 C++ 的额外知识点基本上要从头学过。本教程有一些编程基础建立在C语言上，具体教程请参考：C语言程序设计详细教程（完整版）-CSDN博客

        但面对如此纷繁的知识，我们要从哪里开始呢？当然是从比赛时 C++ 程序的基本格式，也就是最基本的 C++ 程序长什么样开始了解喽！

// 这是 C++ 的标准库，万能头文件
#include <bits/stdc++.h>
// 这句暂时不用明白，只管背下来用就行了，而且一定要写
using namespace std;int main() { // main 函数是 C++ 的启动函数，程序入口// 这一句叫做取消同步流，主要的作用是使程序读取输入和输出的速度提高// 这并不一定需要，但最好也能记住ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);// 下面这句注释掉的内容是 C 语言的输入，// 在 C++ 中也可以使用，但必须和 C 语言的输出配合使用// int n; scanf("%d", &n);// 下面这句是 C++ 的输入int n; cin >> n;// 下面这句注释掉的内容是 C 语言的输出，// 在 C++ 中也可以使用，但必须和 C 语言的输入配合使用，和上面的输入相似// printf("%d", n);// 下面这句是 C++ 的输出cout << n;// 函数遇到 return 会立刻结束，返回 0 表示 main 函数正常结束return 0;
}

         看完上面的代码，你应该明白了一个基本的 C++ 程序长什么样。下面的一个基本程序会告诉你 C++ 中的基本数据类型有哪些。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int x = 3; // 整数double d = 3.14; // 浮点数long long ll = 124124123123; // 长整数char ch = 'A'; // 字符char s[] = "Hello"; // 字符串bool f = true; // 布尔值（即真假值）// cout << x << endl; 这句话和下面一句是一样的意思cout << x << '\n'; // '\n'是换行符，比 endl 更快cout << d << '\n';cout << ll << '\n';cout << ch << '\n';cout << s << '\n';cout << f << '\n';return 0;
}

        一般而言，上面的就是我们在蓝桥杯中常用到的一些数据类型。尤其是其中的 long long 数据类型，这值得我们注意。因为一些题目中的数据范围会很大，这时候，我们一般都不用 int 而是用 long long 代替，并且使用 long long 在一定程度上可以避免未知的数据溢出的风险。

        尽管之前已经提过输入输出的函数，下面我们来正式系统地看一下输入输出的相关内容。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int a, b;cin >> a >> b; int c;double d;cin >> c >> d; // cin 会自动判断变量类型double e, f;cin >> e >> f; // 2 3// 下面的是按照要求小数位数输出的语法格式cout << fixed << setprecision(3) << e << " " << f; // 2.000 3.000char s[10];cin >> s; // lan qiao// cin输入字符串是遇到空格或回车就结束cout << s; // lanchar p[10];cin >> p + 1; // 从p[1]开始输入string str;getline(cin, str); // lan qiao// getline可以一次读入一整行的字符串，直到遇到换行结束cout << s; // lan qiaoreturn 0;
}

        仔细阅读完上面的代码，差不多蓝桥杯中可能出现的输入输出格式上的问题都应该已经解决了。在上面的代码中出现了一种新的库内容 string，因此下面我们就着重来讨论一下这个 string 库的使用方式。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);// string 库主要用于字符串处理// 它可以很方便地完成各种字符串操作，如拼接、截取、匹配等// 1. 字符串的声明和初始化// 1.1 声明并初始化一个字符串string str1 = "Hello,world";// 1.2 或者也可以只声明，不初始化string str2;// 1.3 或者可以使用一个字符串变量来初始化另一个字符串string str3 = str1;// 1.4 或者使用字符数组初始化字符串const char* charArray = "Hello";string str4(charArray);// 1.5 或者使用重复的字符初始化字符串string str5(5, 'a'); // aaaaa// 2. 各种基本操作// 2.1 将string用printf输出时需要转换成C风格的字符串printf("str1 = %s\n", str1.c_str());// 2.2 获取字符串长度int length = str1.length(); // 11// 2.3 拼接字符串string str6 = str1 + " " + str4; // 使用 + 运算符string str7 = str1.append(", ").append(str2); // 使用 append 函数// 2.4 字符串查找size_t pos = str1.find("Hel"); // 查找子字符串的位置// 2.5 字符串替换str1.replace(0, 2, "Universe"); // 三个参数分别是被替换子串的开头，长度，要替换的字符串// 2.6 提取子字符串string substr = str1.substr(0, 5);// 2.7 字符串比较int result = str1.compare(str2); // 比较规则是使用字典序// 3. 字符串遍历for (int i = 0; i < str1.length(); ++i) {cout << str1[i];}for (auto i : str1) {cout << i;i = 's'; // 修改无效，这个 i 是从原字符串中拷贝出来的}for (auto &i : str1) {cout << i;i = 's'; // 修改有效}return 0;
}

        看完上面的四个基本程序，相信你对 C++ 在蓝桥杯中常用的一些编程语法基础已经有了正确的认识。本小节内容到此结束，希望大家打起精神，继续开始下一节的学习叭！

1.2 竞赛常用库函数

        本节中我们会讨论一些在蓝桥杯中常用到的函数或是模板程序。这些内容需要记忆，最好多写多练。

1.2.1 sort 函数

        首先我们要讨论的是排序函数 sort。它包含在头文件 <algorithm> 中，使用前需要导入库，或是使用万能头文件。sort 函数主要用于对指定范围内的元素进行排序，具有较好的时间复杂度，一般为 O(nlogn)。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int a[1000];int n; cin >> n;for (int i = 0; i < n; ++i) cin >> a[i]; // 输入数组// 对数组排序sort(a + 1, a + n + 1); // [1, n + 1)左闭右开排序// 输出for (int i = 0; i < n; ++i) cout << a[i];return 0;
}

        以上就是一个基本的数组排序。sort 默认使用小于号进行排序，如果想要自定义比较规则，可以传入第三个参数，可以是函数或 lambda 表达式。下面我们来讲解一下自定义比较函数的过程。

#include <bits/stdc++.h>
using namespace std;bool cmp(const int &u, const int &v) {return u > v; // 如果 u > v,就把 u 放在 v 前面
}struct Node {int u, v;bool operator < (const Node &m)const {// 以 u 为第一关键字，以 v 为第二关键字return u == m.u ? v < m.v : u < m.u;}
};int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int a[1000];int n; cin >> n;for (int i = 0; i < n; ++i) cin >> a[i]; // 输入数组// 对数组排序，使用cmp函数// 最终排序结果是以比较函数为真作为目的的// 在这里将会是降序排列sort(a + 1, a + n + 1, cmp); // [1, n + 1)左闭右开排序int b[1000];int n; cin >> n;for (int i = 0; i < n; ++i) cin >> b[i]; // 输入数组// 对数组排序，使用lambda表达式// 这如果一下子无法理解，可以跳过，很少用到sort(a + 1, a + n + 1, [](const int &u, const int &v){return u > v;});// 结构体重载<后进行排序// 结构体形式见上Node num[1000];for (int i = 0; i < n; ++i) {cin >> num[i].u >> num[i].v;}sort(num, num + n + 1); // 使用结构体重载的<进行比较// 输出for (int i = 0; i < n; ++i) cout << a[i];return 0;
}

1.2.2 最值查找

        在一个数组中寻找一个最大值或是最小值是常见要求，那么除了遍历，有没有可以直接使用的库函数呢？当然是有的！

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int a, b; cin >> a >> b;cout << min(a, b) << " " << max(a, b) << endl;return 0;
}

        上面的函数有一定的缺陷，只能求两个数的最小值和最大值。如果在一个数组中寻找最小值的下标或最大值的下标有没有什么库函数呢？也是有的！

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int v[10] = {5, 1, 3, 9, 11};// 返回 11 1cout << *max_element(v, v + 5) << endl << *min_element(v, v + 5);return 0;
}

        还有一个函数，虽然用的不多，但在这里也做一下解释。nth_element 这个函数在处理某个数在数组中的相对大小时非常好用！

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int v[10] = {5, 1, 3, 9, 11, 2, 10, 8, 8, 5};// 传入的三个参数为地址或是迭代器// 第二个参数位置的元素将处于正确位置，其它位置的元素的顺序可能是任意的// 但在第二个参数位置之前的元素都比它小，在它之后的元素都比它大// 时间复杂度为 O(n)nth_element(v, v + 4, v + 10);for (auto &i : v) cout << i << " ";return 0;
}

1.2.3 二分查找

        在蓝桥杯中有一类问题是在一个有序数组中查找某个目标值。二分法是专门为了解决这类问题的高效查找方法。它将问题的搜索范围一分为二，迭代地缩小搜索范围，直到找到目标为止。

        我们需要注意的是，二分查找的前提是查找范围是一个有序数据集合，一般可以将 O(n) 转换为 O(logn)。

        最简单的二分查找问题是整数二分 。这里我们直接来分析模板代码：

#include <bits/stdc++.h>
using namespace std;// v[]要查找数组，n数组长度，k要查找值
int midSearch(int v[], int n, int k) {// 目标是找到升序数组中第一次出现k的位置int left = 0, right = n - 1; // 这里的判断条件可以保证最终能够正确退出循环while (left + 1 != right) {// 这种写法对于数据范围很大时，不会出现整数溢出的情况int mid = left + (right - left) / 2;// 如果中间值大于等于 k，那么 k 在 mid 的左边或就是 midif (v[mid] >= k) right = mid;else left = mid;  // 注意这里left,right更新时要保证始终在可能出现k的所属区域}// 检查找到的值是否等于 kif (v[right] == k) {return right;} else {return -1; // 如果没有找到，返回 -1}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int v[100]; int n; cin >> n;for (int i = 0; i < n; ++i) cin >> v[i];sort(v, v + n); // 从小到大排序数组// 我们的目标是查找某个值 k 在数组中是否出现int k; cin >> k;int pos = midSearch(v, n, k);cout << pos << '\n';return 0;
}

        除了整数二分，由于数据类型有可能是浮点数，因此也就出现了浮点二分。浮点二分和整数二分唯一的不同就是判断条件不能用 left + 1 < right，因为浮点数并没有整数的离散性！

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
// v[]要查找数组，n数组长度，k要查找值
int midSearch(double v[], int n, double k) {// 目标是找到升序数组中第一次出现k的位置int left = 0, right = n - 1; // 这里的判断条件可以保证最终能够正确退出循环while (right - left >= eps) {// 这种写法对于数据范围很大时，不会出现浮点溢出的情况int mid = left + (right - left) / 2;// 如果中间值大于等于 k，那么 k 在 mid 的左边或就是 midif (v[mid] >= k) right = mid;else left = mid;  // 注意这里left,right更新时要保证始终在可能出现k的所属区域}// 检查找到的值是否等于 kif (v[right] == k) {return right;} else {return -1; // 如果没有找到，返回 -1}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);double v[100]; int n; cin >> n;for (int i = 0; i < n; ++i) cin >> v[i];sort(v, v + n); // 从小到大排序数组// 我们的目标是查找某个值 k 在数组中是否出现double k; cin >> k;int pos = midSearch(v, n, k);cout << pos << '\n';return 0;
}

1.2.4 大小写转换

        有些题目中会要求所有的字符输出都必须是小写字母或者是大写字母。这时，如果遍历整个字符串有点麻烦，我们就可以使用大小写转换的库函数一步到位。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);// islower和isupper用于检查一个字符是否为小写字母或大写字母char ch1 = 'A';char ch2 = 'a';cout << (islower(ch1) ? "ch1 is lowercase" : "ch1 is uppercase") << endl;cout << (isupper(ch2) ? "ch2 is uppercase" : "ch2 is lowercase") << endl;// isdigit用于检查一个字符是否为数字char ch3 = '5';cout << (isdigit(ch3) ? "ch3 is a digit" : "ch3 is not a digit") << endl;// isalpha用于检查一个字符是否为字母char ch4 = 'b';cout << (isalpha(ch4) ? "ch4 is an alphabet" : "ch4 is not an alphabet") << endl;// tolower和toupper用于将ch转换为小写字母或大写字母char ch5 = 'B';cout << "ch5 in lowercase: " << tolower(ch5) << endl;cout << "ch5 in uppercase: " << toupper(ch5) << endl;return 0;
}

1.2.5 全排列

        全排列按道理是一个高中数学知识点，这里主要是用来处理题目中要求生成所有可能的排列情况。我们会介绍两个函数，分别是用来生成按照字典序的下一个排列和按照字典序的上一个排列。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int nums[] = {1,2,3};cout << "The pernutation is: ";for (int num : nums) cout << num << " ";cout << endl;// next_permutation会将数组按照字典序重新排列// 如果存在下一个排列，则将当前序列更改为下一个排列，返回true;// 如果不存在下一个排列，则将当前序列更改为最小的排列，返回false;while (next_permutation(nums, nums + 3)) {cout << "Next permutation: ";for (int num : nums) cout << num << " ";cout << endl;}// prev_permutation会将数组按照字典序重新排列// 如果存在上一个排列，则将当前序列更改为上一个排列，返回true;// 如果不存在上一个排列，则将当前序列更改为最大的排列，返回false;while (prev_permutation(nums, nums + 3)) {cout << "Previous permutation: ";for (int num : nums) cout << num << " ";cout << endl;}return 0;
}

        基本上这两个函数的使用方法是固定的，就是用循环的方式不断寻找下一个序列，直至回到最开始的情况。

1.2.6 其它库函数整理

        这里我们整理一些除了上面已经提到过的库函数还经常使用的一些函数。这样可以帮助我们快速处理一些操作要求。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int nums[100];// memset函数主要用于给整个数组赋一个初值，这个初值一般为0// 第一个参数是数组名，第二个参数是赋值大小，第三个参数是数组空间大小// 其中第三个参数我们常用sizeof()这个函数来得到空间大小memset(nums, 0, sizeof(nums)); // swap函数可以交换两个变量的值nums[0] = 1; nums[1] = 2;swap(nums[0], nums[1]); // 交换nums[0]和nums[1]的值// reverse函数可以反转数组reverse(nums, nums + 3); // 反转nums数组的前3个元素// 从nums[0]nums[1]nums[2]变为nums[2]nums[1]nums[0]// unique函数用于去除容器中相邻重复元素int test[10] = {1,2,2,2,3,3,4,4,4,5};unique(test, test + 10); // 去除test数组中相邻重复元素// test变为{1，2，3，4，5}return 0;
}

1.3 STL的用法

        如果说 C++ 和 C 最大的不同，在竞赛层面就是 C++ 拥有 C 所没有的完备的 STL 容器。这些功能强大的容器让我们写程序的效率大大提升。

        这一节中，我们不再使用完整的程序，而是使用以展示知识为目的的部分程序。具体的代码结构请参考上文。

1.3.1 pair

        pair 用于表示一对值的组合。它有两个成员变量，可以很方便地将这两个值组合在一起，并进行一系列操作。

pair<int, double> p1(1, 13.14);
pair<char, string> p2('h', "Hello");

        如果我们想单独得到某个pair的第一个变量或第二个变量，可以通过访问 first 和 second 成员变量。

cout << p1.first << " " << p1.second << endl;

        pair 固定只能是两个值的组合。如果我们想要对多个不同的值进行组合，就要用到 pair 的嵌套。例如：对于三维的数学问题，就可以用 pair 嵌套。

// (x,y,z)是一个三维坐标
// make_pair()可以将两个值组合成一个pair赋给一个pair对象
pair<int, pair<int, int>> p1(x, make_pair(y, z));

        最后我们说一下 pair 的排序规则。在 C++ 内置中，pair 排序规则是先按照 first 排列，如果 first 相同，再按照 second 排序。当然，也可以根据自己的需求定义排序规则。

1.3.2 vector

        毫不夸张地说，这是最常用一种容器。它是一个动态数组容器，可以存储一系列相同类型的元素，最大的优点在于可以自动调整大小，根据元素的数量动态分配内存空间。下面我们来介绍一些 vector 中常用的函数。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);// 创建一个vectorint n; cin >> n;vector<int> vec = {1, 2, 3, 4, 5};vector<int> vec1(n, 0); // n个重复的元素0// 将元素添加到vector的末尾vec.push_back(6);// 删除vector末尾的元素vec.pop_back();// 使用迭代器遍历vector// begin() 返回指向第一个元素的迭代器// end() 返回指向最后一个元素之后位置的迭代器for (auto it = vec.begin(); it != vec.end(); ++it) {cout << *it << " ";}// vector的排序去重sort(vec.begin(), vec.end()); // 排序函数vec.erase(unique(vec.begin(), vec.end()), vec.end()); // unique函数将重复的元素移动到末尾，并返回一个指向重复元素的迭代器// erase函数将重复元素从vector中删除return 0;
}

1.3.3 stack和queue

        栈和队列是常用的数据结构。这里STL中已经帮我们内置了实现栈和队列的函数，这让我们可以很方便地使用这两种数据结构。

        首先我们介绍栈。这是一种后进先出的数据结构，它的功能相对比较简单。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);stack<int> myStack;// 向栈中添加元素myStack.push(10);myStack.push(20);myStack.push(30); // {10，20，30}// 检查栈是否为空if (myStack.empty()) {cout << "栈为空" << endl;}// 获取栈的大小cout << "栈的大小为: " << myStack.size() << endl; // 3// 获取栈顶元素cout << "栈顶元素为: " << myStack.top() << endl; // 39// 从栈中移除元素myStack.pop(); // {10，20}// 获取栈顶元素cout << "移除元素后，栈顶元素为: " << myStack.top() << endl; // 20return 0;
}

        接着是队列。队列最主要的特征是先进先出（类比排队打饭）。队列分为几种类型，分别是普通队列、优先队列。我们先讲解普通队列常用的函数。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);queue<int> myQueue;// 在队尾插入元素myQueue.push(1);myQueue.push(2);myQueue.push(3);// 访问队首元素cout << "队首元素: " << myQueue.front() << endl;// 访问队尾元素cout << "队尾元素: " << myQueue.back() << endl;// 移除队首元素myQueue.pop();// 访问队首元素cout << "移除队首元素后的队首元素: " << myQueue.front() << endl;// 检查队列是否为空if (myQueue.empty()) {cout << "队列为空" << endl;}// 获取队列的大小cout << "队列的大小: " << myQueue.size() << endl;return 0;
}

        接着是优先队列中常用的函数。

#include <bits/stdc++.h>
using namespace std;struct Compare {bool operator() (int a, int b) {return a < b; // 如果返回真，就将a放到b后面}
};int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);priority_queue<int, vector<int>, Compare> pq; // 这里如果不用Compare,默认是最大元素位于队列最前面// 插入元素pq.push(1);pq.push(2);pq.push(3);// 取出最大元素cout << pq.top() << endl; // 输出3// 删除最大元素pq.pop();// 判断队列是否为空cout << pq.empty() << endl; // 输出0cout << pq.size() << endl; // 输出2return 0;
}

1.3.4 set

        在高中数学第一章中我们就讲了集合的概念。它将同一类元素放在一起，并且保证没有重复元素存在。在STL中也为我们准备了这个特定集合，帮助我们处理问题。

#include <bits/stdc++.h>
using namespace std;struct Compare {bool operator() (const int& a, const int& b) const {return a > b; // 如果a>b，则将a放到b的左边}
};
int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);set<int, Compare> mySet; // 如果不用Compare就默认升序排列// 插入元素mySet.insert(1);mySet.insert(2);mySet.insert(4);mySet.insert(5);mySet.insert(3);mySet.insert(7);mySet.insert(6);mySet.insert(8);// 移除元素mySet.erase(3);// 查找元素if (mySet.find(7) != mySet.end()) {cout << "7 is in the set" << endl;}// 返回最后一个不大于给定值的迭代器auto it = mySet.lower_bound(4);if (it != mySet.end()) {cout << "The largest element less than or equal to 4 is " << *it << endl;}// 返回第一个大于的迭代器it = mySet.upper_bound(6);if (it != mySet.begin()) {it--;cout << "The smallest element larger than or equal to 6 is " << *it << endl;}return 0;
}

1.3.5 map

        最后我们介绍一种键值对结构map。它可以存储一组键值对，其中每个键都是唯一的。map容器根据键自动排序，并可通过键快速查找对应的值。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);map<int, string> myMap;// 插入元素myMap[1] = "apple";myMap[2] = "banana";myMap[3] = "cherry";myMap.insert(make_pair(4, "grape"));// 遍历mapfor (auto it = myMap.begin(); it != myMap.end(); ++it) {cout << it->first << ": " << it->second << endl;}// 查找元素auto it = myMap.find(2);if (it != myMap.end()) {cout << "Found: " << it->first << ": " << it->second << endl;}// 修改元素myMap[2] = "orange";cout << "2: " << myMap[2] << endl;// 删除元素myMap.erase(3);// 清空mapmyMap.clear();cout << "Size: " << myMap.size() << endl;return 0;
}

二、基础算法

       在本文中基础算法其实指的是一些常见，却又没什么系统性分类的算法。这些算法可能更适合称为方法，因为它们更多地是一些处理数据的手段，一种思维的体现。本章将从递归、前缀和、差分、贪心、双指针和位运算这六部分来讲解。

2.1 递归算法

        用一句话概括：递归是指函数直接或间接调用自身的过程。什么意思呢？

int a(int num) {if (num == 0 || num == 1) return 1;else {return a(num - 1) + a(num - 2);}
}

        上面这个函数中我们判断参数 num 是否等于 0 或 1，如果是则直接返回 1；如果不是，则返回 a(num - 1) + a(num - 2) 的值。其中就用到了函数调用自身的过程。实际上，这也是赫赫有名的斐波那契数列的通项求法。

        如果非要给递归一个可借鉴的模板代码的话，我们也可以参考下面这个程序：

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);// 递归终止条件// 注意，终止条件应该在整个函数最开始的地方if (满足终止条件) {// 返回终止条件下的结果}// 递归调用else {// 在原问题的基础上，将问题规模减小// 递归调用// 处理递归调用返回的结果}return 0;
}

        不得不说，递归这个词会让人想到高中学的数列，如果用数列的思维来考虑递归，就会发现递归很容易理解了。

2.2 前缀和

        说完了递归，我们来看第二个基础算法——前缀和。假设现在有一个数组 a[]（下标从 1 开始），我们定义它的前缀和数组 prefix[] 满足 prefix[ i ] = a[ 1 ] + a[ 2 ] + ... + a[ i ]。

        prefix[] 的一个特性就是方便生成，因为 prefix[ i ] = prefix[ i - 1] + a[ i ]。所以可以很容易地得到某个数组的前缀和数组。

        前缀和数组有什么用呢？它最大的用处在于可以在 O(1) 的时间复杂度下求出 a[] 的一段区间的和，因为 a[ l ] + a[ l + 1] + ... + a[ r ] = prefix[ r ] - prefix[ l - 1 ]。但要注意，数组 a[] 中的元素在查询过程中不能进行修改，或者说，必须先完成所有修改，再进行查询。

        下面我们用一道例题展示一下前缀和的用法：3260 最大数组和

【解答思路】

        这道题目我们最开始的考虑是使用贪心，每次比较两个最小的宝石和最大的宝石的大小，选择总价值小的从宝石组中删除。但事实上，这种方法是错的！！

        

1
6 2
15 22 12 10 13 11

        比如上面的数据，本来应该去除两个最大值，但是两个最小值的和是比第一个最大值要小的，所以贪心会直接把两个最小值删除，答案有误。因此，我们干脆用最基本的想法来解决问题。

        我们每次查找去掉 j - i 个最大元素和 2 * i 个最小元素的情况下的和，从中寻找剩余元素和最大的一种情况。在此过程中，为了快速求出剩余元素最大值，我们使用前缀和数组存储数组元素和。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;int main() {int t; cin >> t;while (t--) {int n, k; cin >> n >> k;int a[N] = {0};for (int i = 0; i < n; ++i) cin >> a[i];int prefix[N] = {0};for (int i = 1; i <= n; ++i) prefix[i] = a[i] + prefix[i-1];// 不能用贪心，查找去除 k-i 个最大元素和 2*i 个最小元素后数组元素和的最大值 int res = 0;for (int j = 0; j <= k && k + j <= n; j++) {res = max(res, prefix[n - (k - j)] - prefix[2 * j]);}cout << res << endl;}return 0;
}

 2.3 差分

        一些问题会要求修改数组中一段区间中所有的值，并且这些值的改变大小一样。如果用循环遍历会很消耗时间，所以我们需要学习使用差分数组。

        对于一个数组 a[]，差分数组 diff[] 的定义是：diff[ i ] = a[ i ] - a[ i - 1 ]。差分数组做前缀和可以还原成原数组：diff[ 1 ] + diff[ 2 ] + diff[ 3 ] + ... + diff[ i ] = a[ i ]。

        回到开始我们提出的问题：如何快速修改数组某个区间上的所有值呢？其实我只需要进行下面两步即可：

// 希望将区间[l, r]都加上x
diff[i] += x;
diff[r - 1] -= x;

        在所有修改完成后，只需要做前缀和就可以恢复为原数组。但是也要注意，差分数组不能实现“边修改边查询（区间和）”，必须“多次修改完成后多次查询”。

        下面我们用一道例题展示一下差分的用法：小蓝的操作

【解答思路】

        每次操作可以让区间 [l, r] 所有数字减 1，我们自然会想到差分数组。对区间 [l, r] 中的所有数字减 1，相当于对 a 数组的差分数组 diff 进行操作 diff[ l ] -= 1; diff[r + 1] += 1。最终要求 a 数组全为 1，那么相当于差分数组 d 的第一个元素为 1，后面的元素全为 0。因为数据保证有解，因此最快的操作方式就是将 diff 数组的第一个减为 1，后面所有正数减为 0。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{int n; cin >> n;vector<int> a(n, 0);vector<int> diff(n, 0);ll res = 0;for (int i = 0; i < n; i++) cin >> a[i];diff[0] = a[0]; res += diff[0] - 1;for (int i = 1; i < n; i++) {diff[i] = a[i] - a[i - 1]; // 构造差分数组if (diff[i] > 0) res += diff[i];}cout << res;return 0;
}

 2.4 贪心算法

        在一类策略游戏中，我们每一步都选择局部最优解，从而使最终结果达到最优，这就是“贪心”的思路。但事实上，很多策略问题都不能用贪心来解决，比如说我们上面在前缀和里使用的那道例题就不能用贪心来解决，尽管看上去很像贪心。总而言之，这是一个看上简单，但需要勤加练习的算法。

        下面我们用一道例题展示一下贪心的用法：训练士兵

【解题思路】

        我们先按照每个士兵需要的训练次数来排序，从小到大排序。很明显，如果剩余需要训练的士兵数量越多，使用组团训练就越划算。我们会发现，组团训练的次数必定为：

        a[ 0 ].c

        a[ 0 ].c + a[ 1 ].c

        ...

        a[ 0 ].c + a[ 1 ].c + a[ 2 ].c + ... + a[n - 1].c

中的其中一个。因此，我们可以遍历所有可能的组团次数，从中筛选出最划算的训练方式。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node{long long p , c;bool operator < (const node &x) const{return c < x.c;}
}a[N];
int n;
long long C, sum_p[N] , sum_cp[N];
// 方便使用前缀和处理问题
long long getP(int l , int r){return sum_p[r] - sum_p[l - 1];
}
long long getCP(int l , int r){return sum_cp[r] - sum_cp[l - 1];
}
int main(){cin >> n >> C;for(int i = 1 ; i <= n ; i ++) cin >> a[i].p >> a[i].c;sort(a + 1 , a + 1 + n);for(int i = 1 ; i <= n ; i ++) sum_p[i] = sum_p[i - 1] + a[i].p , sum_cp[i] = sum_cp[i - 1] + a[i].p * a[i].c;// 这是最大的long long数，需要记忆long long ans = 0x3f3f3f3f3f3f3f3fll;for(int i = 0 ; i <= n ; i ++){long long now = C * a[i].c + (getCP(1, n) - getP(i + 1 , n) * a[i].c - sum_cp[i]);ans = min(ans , now);}cout << ans << '\n';return 0;
}

 2.5 双指针

        双指针算法属于是一种思维方式，通常用于在数组或字符串中进行快速查找、匹配、排序或移动等操作。事实上，双指针并非一定是两个指针的移动实现，一般而言是用两个变量来表示下标，并根据问题要求移动这些指针。常见的双指针模型有对撞指针、快慢指针两种。

2.5.1 对撞指针

        我们令指针 left、right 分别指向序列的第一个元素和最后一个元素。然后 left 指针不断递增，right 指针不断递减直至两者相撞或错开。最明显的就是回文字符串的判断。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);string str; cin >> str;int n = str.size();int left = 0, right = n - 1;// 判断对撞指针是否相遇while (left < right) {// 不同直接结束if (str[left] != str[right]) {cout << "NO" << endl;return 0;}// 否则指针分别左移和右移left++;right--;}return 0;
}

        上面的代码也可以看成是对撞指针的模板。但事实上，对撞指针中的两个指针并不一定同时移动，可能是在满足某一条件时左侧指针右移，而满足另一条件时，右侧指针左移。因此，我们还需要视情况而定。

2.5.2 快慢指针

        快慢指针比对撞指针更难写也更难想。它是让两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的叫快指针，移动慢的叫慢指针。

        如果说现在还不明白它的含义，我想我们最值得做的就是循环链表这道题目了！LCR 022. 环形链表 II - 力扣（LeetCode）

【解题思路】

        我们使用快慢指针来解决这个问题。首先令快指针每次移动两个位置，慢指针每次移动一个位置。如果存在环，则快慢指针最终一定会相遇。此时，令另外一个指针从链表头开始移动，慢指针从与快指针相遇的地方开始同步移动，当两者相遇时，恰好会在进入环形链表的地方。（这里需要数学证明，在本复习笔记中我们不做过多解释）

ListNode *detectCycle(ListNode *head) {ListNode *slow = head, *fast = head;while (fast != nullptr) {slow = slow->next;if (fast->next == nullptr) return nullptr;fast = fast->next->next;// 此时快慢指针相遇if (fast == slow) {ListNode *ptr = head;// 定义一个新指针开始移动    while (ptr != slow) {ptr = ptr->next;slow = slow->next;}return ptr;}}return nullptr;
}    

 2.6 位运算

        众所周知，在计算机中数都是以二进制的形式进行存储和运算的。因此，抛弃掉现实世界中的十进制运算思维，在二进制中也有需要新的计算技巧亟待我们去学习。位运算指的就是直接对二进制数的位进行运算。

        由于是对二进制数的每一位独立运算，因此，寻找位运算规律往往就是直接从数的每一位入手。在蓝桥杯中常用到一些位运算的性质包括异或的性质等等。下面我们以此说明：

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int x; cin >> x;cout << (x & 1); // 如果为1说明是奇数，如果为0说明是偶数int i; cin >> i;// 下面两种获取方式有什么区别？cout << (x >> i & 1); // 获取二进制的某一位cout << (x & (1 << i)); // 获取二进制的某一位cout << (x | (1 << i)); // 修改二进制中某一位为1cout << (x & (x-1)); // 快速判断一个数是否为2的幂次方// 如果是2的幂次方，则二进制表示只有1个1，两者运算结果为0cout << (x & -x); // 获取二进制中最低位的1cout << (x ^ x); // 一个数和自身异或结果为0cout << (x ^ 0); // 一个数和0异或结果为自身return 0;
}

        学到这里，我们已经讲完了基础算法的部分，希望大家都还有毅力继续学下去。我们即将开启的是搜索算法的篇章。这一部分本来应该在图论中再提及，但是考虑到图的遍历和图的搜索有一定区别，我们决定单独分析一下。

算法知识点整理 · 考前突击（上）就到此为止了，之后我也会尽快整理好之后的内容哒。完成后链接会放在这里：（请等等哦，马上来）。谢谢大家的阅读！