【背景說明】本文的作者是一名算法競賽小白，在第一次參加藍橋杯之前希望整理一下自己會了哪些算法，于是有了本文的誕生。分享在這里也希望與眾多學子共勉。如果時間允許的話，這一系列會分為上中下三部分和大家見面，祝大家競賽順利！
【文風說明】本文主要會用代碼＋注釋的方式來解釋內容。相信學過編程的人都會發現程序比長篇大論更易理解！
目錄
一、語言基礎
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;
}? ? ? ? 學到這里，我們已經講完了基礎算法的部分，希望大家都還有毅力繼續學下去。我們即將開啟的是搜索算法的篇章。這一部分本來應該在圖論中再提及，但是考慮到圖的遍歷和圖的搜索有一定區別，我們決定單獨分析一下。
算法知識點整理 · 考前突擊（上）就到此為止了，之后我也會盡快整理好之后的內容噠。完成后鏈接會放在這里：（請等等哦，馬上來）。謝謝大家的閱讀！
)
