蓝桥杯1.语言基础

蓝桥杯 1.语言基础

文章目录 蓝桥杯 1.语言基础编程基础C++版本和基础格式输入输出string的使用编程1-5 竞赛常用库函数sort()最值查找二分查找大小写转换全排列其他库函数 STLpairvectorliststackqueuesetmap总结编程6-10

编程基础 C++版本和基础格式

版本:

蓝桥杯使用C++11

基础格式

#include <bits/stdc++.h> // 万能头文件, VS中不支持使用 using namespace std; int main(){ cout << "Hello, World!" << endl; // 利用cout将字符串输出 printf("Hello, World!"); // 利用printf将字符串输出 return 0; }

万能模板

#include <bits/stdc++.h> // 万能头文件, VS中不支持使用 using namespace std; using ll = long long; // 开long long const ll MAXN = 2e5 + 5; // 防止数组大小开太大或者太小 ll n, a[MAXN]; // 变量尽量使用全局 int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 关闭同步流, 提升cin和cout的速度, 如果使用scanf, printf, getchar一定要注释掉 return 0; } 输入输出

scanf和printf

格式化输入输出效率高

cin和cout

效率低

scanf和cin遇到空格和回车都会结束

取消同步流

// 由于cin和cout需要自动判断变量类型等内部原因, 读写效率比scanf和printf更低, 当数据量较大时, 可能导致程序运行超时. 我们可以通过取消同步流来加速cin和cout, 加速后效率相差无几 // 取消同步流 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); string的使用

string简介

字符串管理: 自动处理字符串的内存分配和释放, 避免了手动管理内存的麻烦动态大小调整: string可以根据需要自动调整字符串的大小迭代器支持

string的声明和初始化

#include <bits/stdc++.h> using namespace std; int main(){ // 取消同步流 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); string str1; string str2 = "Hello, World"; string str3 = str2; string str4 = str2.substr(0, 5); // substr(起始位置, 长度) const char* charArray = "Hello"; string str5(charArray); // string(个数, 字符) string str6(5, 'A'); string str7; // cin >> str7; // cin遇到空格或者回车就会结束 getline(cin, str7); // 而getline()不会 cout << "str1: " << str1 << endl; // 空白 cout << "str2: " << str2 << endl; // Hello, World cout << "str3: " << str3 << endl; // Hello, World cout << "str4: " << str4 << endl; // Hello cout << "str5: " << str5 << endl; // Hello cout << "str6: " << str6 << endl; // AAAAA cout << "str7: " << str7 << endl; }

各种基本操作

string转换成char[] (c_str()) #include <bits/stdc++.h> using namespace std; int main(){ // 取消同步流 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); char buf[100]; scanf("%[^\n]", buf); // [^\n] 正则表达式, 排除空格和换行 string str(buf); printf("%s", str.c_str()); // 在进行printf 输出时, 需要将string转换成c风格的字符串进行输出, 即string->char[] } 获取字符串长度(length/size) // length string str = "Hello, World!"; int length = str.length(); // int length = str.size(); cout << length << endl; 拼接字符串(+或append) // + append string str1 = "Hello"; string str2 = "World!"; string result1 = str1 + str2; string result2 = str1.append(", ").append(str2); cout << result1 << endl; cout << result2 << endl; 字符串查找(find) // find: 查找成功则返回第一个出现的字符的位置或者子串的位置，查找失败则返回string::npos即为-1 string str = "Hello, World!"; size_t pos = str.find("World"); // 查找子字符串的位置 if(pos != string::npos){ cout << "Substring found at positions:" << pos << endl; } else { cout << "Substring not found." << endl; } 字符串替换(replace) // replace string str = "Hello, World!"; str.replace(7, 5, "Universe"); // (起始位置, 替换的长度, 替换字符串) cout << str << endl; 提取子字符串(substr) // substr string str = "Hello, World!"; string str3 = str.substr(7, 5); // substr(起始位置, 长度(不要越界)) cout << str3 << endl; 字符串比较(compare) // compare string str1 = "Hello"; string str2 = "World!"; int result = str1 pare(str2); // 比较字符串, 比较的方法是从小到大一个一个比较, 一旦遇到不相等的字符就确定大小关系 if(result == 0){ cout << "Strings are equal." << endl; } else if(result < 0){ cout << "String 1 is less than String 2." << endl; } else { cout << "String 1 is greater than String 2." << endl; } 常用的遍历string的方法有两种 循环枚举下标auto枚举(其中&表示取引用, 如果对i修改将会改变原来的值) // 下标遍历 string s = "Hello"; int i; for(i = 0; i < s.length(); i++){ cout << s[i]; } cout << endl; // auto枚举 for(auto i : s){ // 这里的i是复制s中对应的字符串 cout << i; i = 'a'; } cout << endl; cout << s << endl; // 此时的s为"Hello" for(auto &i : s){ // 这里的i就是s, 它们的地址相同 cout << i; i = 'a'; } cout << endl; cout << s << endl; // 此时的s为"aaaaa" 逆序输出字符串

#include <bits/stdc++.h> using namespace std; int main(){ // 取消同步流 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 手写的 // string str; // getline(cin, str); // int i; // for(i = 0; i < str.length() / 2; i++){ // char tmp = str[i]; // str[i] = str[str.length() - i - 1]; // str[str.length() - i - 1] = tmp; // } // cout << str << endl; // 调用函数reverse(), begin(), end() // string str; // getline(cin, str); // reverse(str.begin(), str.end()); // cout << str << endl; // 调用函数swap() string str; getline(cin, str); int i; for(i = 0; i < str.length() / 2; i++){ swap(str[i], str[str.length() - i - 1]); } cout << str << endl; return 0; } 编程1-5 编程1 妮妮的翻转游戏0

#include <bits/stdc++.h> using namespace std; int main(){ // 取消同步流 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int x; cin >> x; int result = 0; if(x == 0){ result = 1; } else if(x == 1) { } else { cout << "输入错误" << endl; return 0; } cout << result << endl; return 0; } 编程2 妮妮的蓝桥果园

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; // 原本的数量 int a; // 摘下的数量 int b; // 挂上的数量 cin >> n; cin >> a; cin >> b; int result = n - a + b; cout << result << endl; return 0; } 编程3 蓝桥镇的月饼节

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, w; // 承重量, 每个月饼的重量 cin >> n; cin >> w; int result = n / w; cout << result << endl; return 0; } 编程4 妮妮的蓝桥果园2

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; // 种类数 int a[n]; // 每个水果的价值 cin >> n; int i; int result = 0; for(i = 0; i < n; i++){ cin >> a[i]; } // for(i = 0; i < n; i++){ // result += a[i]; // } // cout << result << endl; cout << accumulate(a, a + n, 0) << '\n'; // 计算a到a+n之间的和, 初始值为0 return 0; } 编程5 小蓝的决议

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; // 测试用例的数量 int n, x; // 成员总数, 赞成的成员数量 cin >> t; int i; for(i = 0; i < t; i++){ // cin >> n; // cin >> x; // string result; // if((n % 2 == 0 && x >= n / 2) || (n % 2 != 0 && x > n / 2)){ // result = "YES"; // } else { // result = "NO"; // } // cout << result << endl; // } for(int i = 0; i < t; i++){ cin >> n >> x; cout << (x >= (n + 2 - 1) / 2 ? "Yes" : "No") << "\n"; // a / b向上取整 等价于 (a+b-1)/b } return 0; } 竞赛常用库函数 sort()

简介

需要引用头文件<algorithm>使用的是快速排序, 具有较好的平均时间复杂度, 一般为O(nlogn)

用法

sort(起始地址, 结束地址的下一位, *比较函数(*表示可写可不写)) #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int arr[1000]; int n; cin >> n; int i; for(i = 0; i < n; i++){ cin >> arr[i]; } sort(arr, arr + n); // 左闭右开, 默认升序 for(i = 0; i < n; i++){ cout << arr[i] << " "; } return 0; } #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 初始化v vector<int> v = {5, 1, 3, 9, 11}; // 对数组进行排序 sort(v.begin(), v.end()); // v[0], v[5]左闭右开 int i; for(i = 0; i < v.size(); i++){ cout << v[i] << ' '; } return 0; }

自定义比较函数

sort默认使用小于号进行排序(升序), 如果想要自定义比较规则, 可以传入第三个参数, 可以是函数或lambda表达式 #include <bits/stdc++.h> using namespace std; bool cmp(int u, int v){ // 比较函数 return u > v; } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 初始化v vector<int> v = {5, 1, 3, 9, 11}; // 对数组进行排序 sort(v.begin(), v.end(), cmp); // 传入函数名, 以降序的形式排序 int i; for(i = 0; i < v.size(); i++){ cout << v[i] << ' '; } return 0; } 升序降序

#include <bits/stdc++.h> using namespace std; bool cmp(int u, int v){ return u > v; } const int N = 5e5 + 3; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; int a[N]; int i; for(i = 0; i < n; i++){ cin >> a[i]; } sort(a, a + n); for(i = 0; i < n; i++){ cout << a[i] << ' '; } cout << endl; sort(a, a + n, cmp); for(i = 0; i < n; i++){ cout << a[i] << ' '; } cout << endl; return 0; } 最值查找

min和max函数

可以传入两个值或者一个数组传入两个值的时候时间复杂度为O(1), 传入数组时时间复杂度为O(n), n为数组的大小 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << min(3, 5) << endl; // 3 cout << min({1,2,3,4}) << endl; // 1 cout << max(3, 5) << endl; // 5 cout << max({1,2,3,4}) << endl; // 4 return 0; }

min_element和max_element

min_element(st, ed)返回地址[st, ed)中最小的那个值的地址(迭代器), 传入参数为两个地址或迭代器时间复杂度均为O(n), n为数组大小 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); vector<int> v = {5, 1, 3, 9, 11}; // 初始化v // 输出最大的元素, *表示解引用, 即通过地址(迭代器)得到值 cout << *max_element(v.begin(), v.end()) << endl; // 11 return 0; }

nth_element函数

nth_element(st, k, ed)进行部分排序, 返回值为void()其中第二个位置参数对应的元素处于排序后的正确位置, 其他位置元素的顺序可能是任意的, 但前面的都比它小, 后面的都比它大时间复杂度为O(n) #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); vector<int> v = {5, 1, 7, 3, 10, 18, 9}; // 初始化v // 输出最大的元素, *表示解引用, 即通过地址(迭代器)得到值 nth_element(v.begin(), v.begin() + 3, v.end()); // 这里的v[3]将会位于排序后的位置, 其他的任意 for(auto &i : v){ cout << i << ' '; // 3 1 5 7 9 18 10 } return 0; } 求最大值, 最小值和平均数

#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 9; int a[N]; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for(int i = 0; i < n; i++){ cin >> a[i]; } // 法一, 使用max_element // cout << *max_element(a, a + n) << endl; // 传入起始地址和末尾地址 // cout << *min_element(a, a + n) << endl; // 法二, 使用max和min遍历 int mn, mx; for(int i = 1; i < n; i++){ mn = min(a[0], a[i]); mx = max(a[0], a[i]); } cout << mx << endl; cout << mn << endl; long long sum = 0; for(int i = 0; i < n; i++){ sum += a[i]; // 求和 } // 先让sum变成浮点数再运算, 最后保留两位小数 cout << fixed << setprecision(2) << 1.0 * sum / n << endl; return 0; } 二分查找

二分法简介

通过将问题的搜索范围一分为二, 迭代的缩小搜索范围, 知道找到目标或确定目标不存在适用于有序数据集合, 每次迭代可以将搜索范围缩小一半本质上也是枚举, 利用数据结构的单调性减少了很多不必要的枚举, 一般可以将O(n)的枚举优化到O(logn)常见的二分类型 整数二分浮点二分二分答案(最常见) 若以 r r r 作为答案, 那么答案区间在 [ l + 1 , r ] [l + 1, r] [l+1,r], 若以l作为答案, 那么答案区间在 [ l , r − 1 ] [l, r - 1] [l,r−1]中点 m i d = ( l + r ) / 2 mid = (l + r) / 2 mid=(l+r)/2

整数二分

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int data[200]; for(int i = 0; i < 200; i++){ data[i] = 4 * i + 6; // 6 10 14 18 22 26 ... } int findNum; cin >> findNum; int left = 0, right = 199; int mid; while (left + 1 != right) { // 如果l和r相邻, 则说明l和r当中带等于号的是结果, 不相邻则继续循环 mid = (left + right) / 2; if (data[mid] >= findNum){ // 哪个地方有=就输出哪个 right = mid; } else { // 这个地方没有= left = mid; } } cout << right << endl; // right上面有=, 则输出right return 0; }

浮点二分

在某个实数范围内进行查找不常用

二分答案

最常见最重要二分框架(时间复杂度O(logm)) + check函数(时间复杂度O(n))将答案进行二分, 然后再枚举出某个可能解后判断其是否可以更优或者是否合法

#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 9; int a[N]; int L, n, m; // 起点到终点的距离, 起点和终点之间的岩石数量, 移走的岩石数量 // 返回当最短距离为mid时需要移除的最少石头数量(贪心法) int check(int mid){ int res = 0, lst = 0; for(int i = 1; i <= n; i++){ // 将i移除 if(a[i] - a[lst] < mid){ res++; } else { lst = i; } } // 将lst移除 if(L - a[lst] < mid){ res++; } return res; } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> L >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; // 第i块岩石与起点的距离 } int l = 0, r = 1e9 + 5; while(l + 1 != r){ int mid = (l + r) / 2; if(check(mid) <= m){ l = mid; } else { r = mid; } } cout << l << '\n'; return 0; }

#include <bits/stdc++.h> using namespace std; long long n, m, k; // n*m矩阵, 第k大的元素 long long rnk(long long mid){ long long res = 0; for(int i = 1; i <= n; i++){ res += min(m, mid / i); } return res; } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m >> k; long long l = 0, r = 1e14; while(l + 1 != r){ long long mid = (l + r) / 2; if(rnk(mid) >= k){ r = mid; } else { l = mid; } } cout << r << '\n'; return 0; } 大小写转换

islower和isupper函数

检查一个字符是否是小写或大写包含头文件<cctype>函数返回值为bool类型 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); char ch1 = 'A'; char ch2 = 'b'; if(islower(ch1)){ cout << ch1 << " is a lowercase letter." << endl; } else { cout << ch1 << " is not a lowercase letter." << endl; } if(isupper(ch2)){ cout << ch2 << " is an uppercase letter." << endl; } else { cout << ch2 << " is not an uppercase letter." << endl; } return 0; }

tolower和toupper函数

tolower(char ch)将ch转换为小写字母, 如果ch不是大写字母则不进行操作, toupper同理 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); char ch1 = 'A'; char ch2 = 'b'; char lowercaseCh1 = tolower(ch1); cout << "Lowercase of " << ch1 << " is " << lowercaseCh1 << endl; char uppercaseCh2 = toupper(ch2); cout << "Uppercase of " << ch2 << " is " << uppercaseCh2 << endl; return 0; }

ascii码

‘A’(65), ‘Z’(90)‘a’(97), ‘z’(122) #include <bits/stdc++.h> using namespace std; char convertedCh(char ch){ if(islower(ch)){ ch = toupper(ch); } else if(isupper(ch)){ ch = tolower(ch); } return ch; } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // char ch = 'a'; // char convertedCh; // // if(ch >= 'A' && ch <= 'Z'){ // convertedCh = ch - 'A' + 'a'; // cout << convertedCh << endl; // } else { // convertedCh = ch - 'a' + 'A'; // cout << convertedCh << endl; // } string s; getline(cin, s); // for(auto &i : s){ // i = convertedCh(i); // } for(int i = 0; i < s.length(); i++){ s[i] = convertedCh(s[i]); } cout << s << endl; return 0; } 全排列

next_permutation()函数

permutation(排列)用于生成当前序列的下一个排列. 按照字典序对序列进行重新排列, 如果存在下一个排列, 则将当前序列更改为下一个排列, 并返回true, 如果当前序列已经是最后一个排列, 则将序列更改为第一个排列, 并返回false例如 123, 132, 213, 231, 312, 321abc, acb, bac, bca, cab, cba #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); vector<int> nums = {1, 2, 3}; // 初始排列 for(int num : nums){ cout << num << " "; } cout << endl; // 生成下一个排列 while(next_permutation(nums.begin(), nums.end())){ // for(int num : nums){ cout << num << " "; } cout << endl; } return 0; }

prev_permutation()函数

与next_permutation()函数相反

用于生成当前序列的上一个排列. 按照字典序对序列进行重新排列, 如果存在上一个排列, 则将当前序列更改为上一个排列, 并返回true, 如果当前序列已经是第一个排列, 则将序列更改为最后一个排列, 并返回false

例如

321, 312, 231, 213, 132, 123 // 以数组的形式 int a[10]; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 初始化 int j = 0; for(int i = 4; i >= 1; i--){ a[j] = i; j++; } bool tag = true; while(tag){ for(int i = 0; i < 4; i++){ cout << a[i] << ' '; } cout << endl; tag = prev_permutation(a, a + 4); } return 0; } 其他库函数

memset()

用于设置内存块值(初始化数组)

头文件<cstring>

函数原型void* memset(void* ptr, int value, size_t num);

ptr: 指向要设置值的内存块的指针value: 要设置的值(通常是一个整数, 8bit位(1byte)二进制数)num: 要设置的字节数 例如: // 将数组arr中的所有元素全部设置为0 int arr[10]; memset(arr, 0, sizeof(arr)); 注意: 该函数对于非字符类型(非char类型)的数组可能会产生为定义行为, 因为char类型是8bit(1byte), 而比如说int类型, 是32bit(4byte), 它会将该数字分为4部分, 对每一部分的最后一位二进制取value, 所以此时形成的数字会不固定.

swap()

swap(&a, &b)接收两个参数, 可以交换任意类型的变量, 包括基本数据类型和自定义类型 int a = 10; int b = 20; swap(a, b);

reverse()

用于反转容器中元素顺序头文件**<algorithm>**函数原型template<class BidirIt> void reverse(BidirIt first, BidirIt last)接收两个参数 first: 指向容器中要反转的第一个元素的迭代器last: 最后一个元素的下一个位置(左闭右开)的迭代器 可以用于反转各种类型的容器, 包括数组, 向量, 链表只能用于支持双向迭代器的容器, 因为它需要能够向前和向后遍历容器中的元素 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); vector<int> v = {1, 2, 3, 4, 5}; reverse(v.begin(), v.end()); for(int num : v){ cout << num << ' '; // 5 4 3 2 1 } cout << endl; return 0; }

unique()

用于去除容器中相邻重复元素

如果需要去除所有重复元素, 可以先对容器进行排序, 然后再使用unique()

头文件<algorithm>

函数原型template<class ForwardIt> ForwardIt unique(ForwardIt first, ForwardIt last)

接收两个参数

first: 指向容器中要反转的第一个元素的迭代器last: 最后一个元素的下一个位置(左闭右开)的迭代器

返回一个指向去重后范围的尾后迭代器

时间复杂度O(n), 但是一般去重之前都需要进行排序O(nlogn), 所以一般都是以排序的时间复杂度作为依据

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); vector<int> v = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5}; auto it = unique(v.begin(), v.end()); // 此时的it指向的是尾后迭代器, 也就是v中的第二个3 for(int num : v){ cout << num << " "; // 1 2 3 4 5 3 3 4 4 5 } cout << endl; v.erase(it, v.end()); // 将v中的[it, end)范围内的元素删除 for(int num : v){ cout << num << " "; // 1 2 3 4 5 } cout << endl; return 0; } #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int a[] = {3, 1, 2, 2, 3}; sort(a, a + 5); // 对于重复但不相邻的数组, 就需要先进行排序, 然后去重 int n = unique(a, a + 5) - a; // unique()返回一个指向去重后尾后的迭代器it, it - a返回给n(这是两个地址进行运算, 为了将后面多余的元素忽略) for(int i = 0; i < n; i++){ cout << a[i] << ' '; } return 0; } STL pair

定义和结构

是一个模板类, 用于表示一对值的组合头文件<utility>有两个模板参数T1和T2, 分别表示第一个值和第二个值的类型 template<class T1, class T2> // 两个模板参数, 分别表示第一个和第二个值的类型 struct pair{ T1 first; T2 second; // 成员变量, 分别表示第一个和第二个值 // 构造函数 pair(); pair(const T1& x, const T2& y); // 比较运算符重载 bool operator==(const pair& rhs) const; bool operator!=(const pair& rhs) const; // 其他成员函数和特性 }; #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); pair<int, double> p1(1, 3.14); pair<char, string> p2('a', "hello"); cout << p1.first << ", " << p1.second << endl; // 1, 3.14 cout << p2.first << ", " << p2.second << endl; // a, hello return 0; }

嵌套

可以将一个pair对象作为另一个pair对象的成员 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); pair<int, int> p1(1, 2); pair<int, pair<int, int>> p2(3, make_pair(4, 5)); pair<pair<int, int>, pair<int, int>> p3(make_pair(6, 7), make_pair(8, 9)); cout << p1.first << ", " << p1.second << endl; cout << p2.first << ", " << p2.second.first << ", " << p2.second.second << endl; cout << p3.first.first << ", " << p3.first.second << ", " << p3.second.first << ", " << p3.second.second << endl; return 0; }

自带排序规则

按照first成员进行升序排序, 如果first成员相等, 则按照second成员进行升序排序 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); vector<pair<int, int>> vec; vec.push_back(make_pair(3, 2)); vec.push_back(make_pair(1, 4)); vec.push_back(make_pair(2, 1)); sort(vec.begin(), vec.end()); for(const auto& p : vec){ cout << p.first << ", " << p.second << endl; } /* 1, 4 2, 1 3, 2 */ return 0; }

代码示例

#include <bits/stdc++.h> using namespace std; // 人结构体 struct Person{ string name; int age; }; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 创建一个存储Person对象的向量 vector<Person> people; // 添加一些Person对象到向量中 people.push_back({"Alice", 25}); people.push_back({"Bob", 30}); people.push_back({"Charlie", 20}); // 创建一个存储pair的向量, 每个pair包含一个Person对象和一个评分 vector<pair<Person, int>> scores; // 添加一些pair到向量中 scores.push_back({people[0], 90}); scores.push_back({people[1], 85}); scores.push_back({people[2], 95}); // 姓名, 年龄, 评分 for(const auto& pair : scores){ cout << "Name: " << pair.first.name << endl; cout << "Age: " << pair.first.age << endl; cout << "Score: " << pair.second << endl; cout << endl; } return 0; } vector

定义和特性

vector是一个动态数组容器, 它会根据元素的数量动态调整大小, 可以存储一系列相同数据类型的元素头文件<vector>语法vector<T类型> vec;元素访问: []元素添加 push_back()在末尾添加元素insert()在指定位置 元素删除 pop_back()在末尾删除元素erase()在指定位置 大小管理 size()获取容器大小empty()检查容器是否为空resize()调整容器大小, 一般在程序的开头clear()清空容器 迭代器 begin()获取指向第一个元素的迭代器end()最后一个

常用函数

push_back()pop_back(), 一定要保证vector非空begin()end()

排序去重

sort()unique()配合erase()

代码示例

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); vector<int> nums; // 在末尾添加元素 nums.push_back(1); nums.push_back(6); nums.push_back(8); nums.push_back(2); nums.push_back(6); nums.push_back(1); for(int num : nums){ cout << num << " "; // 1 6 8 2 6 1 } cout << endl; // 排序 sort(nums.begin(), nums.end()); for(int num : nums){ cout << num << " "; // 1 1 2 6 6 8 } cout << endl; // 去重 nums.erase(unique(nums.begin(), nums.end()), nums.end()); for(int num : nums){ cout << num << " "; // 1 2 6 8 } cout << endl; // 在指定位置插入元素 nums.insert(nums.begin() + 2, 3); // 在nums.begin() + 2位置插入元素3 for(int num : nums){ cout << num << " "; // 1 2 3 6 8 } cout << endl; // 删除指定位置的元素 nums.erase(nums.begin() + 4); for(int num : nums){ cout << num << " "; // 1 2 3 6 } cout << endl; // 检查是否为空 if(nums.empty()){ cout << "为空" << endl; } else { cout << "非空" << endl; // 非空 } // 获取大小 cout << nums.size() << endl; // 4 // 清空 nums.clear(); if(nums.empty()){ cout << "为空" << endl; // 为空 } else { cout << "非空" << endl; } return 0; } list

定义和结构

使用频率不高, 在做题时几乎遇不到是一种双向链表容器, 以节点的形式存储元素, 并使用指针将这些节点链接在一起, 形成一个链表结构(不能随机访问list容器中的对象, 可以从两端顺序访问元素)双向性: 每个节点都包含指向前一个和后一个节点的指针动态大小: 因为是容器不连续存储: 链表中的节点可以在内存中任意位置分布, 不要求连续存储, 因此插入和删除操作不会导致元素的移动提供了一系列成员函数和迭代器来操作和访问链表中的元素注意: list是双向链表, 因此插入和删除操作的时间复杂度是O(1), 但访问和查找操作的时间复杂度是O(n), 因此需要频繁进行随机访问操作, 可能更适合使用支持随机访问的容器, 例如vector或deque(双端队列) #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); list<int> myList; // 在链表尾部插入元素 myList.push_back(1); myList.push_back(4); myList.push_back(3); myList.push_back(6); // 在链表头部插入元素 myList.push_front(9); for(int num : myList){ // int也可以写成auto cout << num << " "; } cout << endl; return 0; }

常用函数

push_back()在末尾插入push_front()在开头插入pop_back()删除末尾pop_front()删除开头size()empty()clear()front()返回链表中第一个元素的引用back()最后一个begin()end()insert()erase()

代码示例

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); list<int> myList; // 插入元素 for(int i = 1; i <= 5; i++){ myList.push_back(i); } // 输出 for(auto num : myList){ cout << num << ' '; // 1 2 3 4 5 } cout << endl; // 反转 reverse(myList.begin(), myList.end()); for(auto num : myList){ cout << num << ' '; // 5 4 3 2 1 } cout << endl; // 插入 myList.insert(++myList.begin(), 0); for(auto num : myList){ cout << num << ' '; // 5 0 4 3 2 1 } cout << endl; // 删除 myList.erase(++ ++ myList.begin(), -- myList.end()); for(auto num : myList){ cout << num << ' '; // 5 0 1 } cout << endl; // 大小 cout << myList.size() << endl; // 3 return 0; } stack

定义和结构

是一种后进先出LIFO(Last In First Out)的数据结构头文件<stack>时间复杂度O(1)不能遍历如果将一个数组的元素依次放入栈, 再依次取出, 则可以将数组翻转

常用函数

push(x)在栈顶插入元素xpop()弹出栈顶元素top()返回栈顶元素empty()size()

代码示例

#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(4); myStack.push(2); myStack.push(6); myStack.push(1); myStack.push(7); // 获取栈顶元素 cout << myStack.top() << endl; // 7 // 弹出栈顶元素 myStack.pop(); cout << myStack.top() << endl; // 1 // 检查是否为空 if(myStack.empty()){ cout << "为空" << endl; } else { cout << "非空" << endl; // 非空 } // 获取大小 cout << myStack.size() << endl; // 4 return 0; } queue

queue队列

先进先出(FIFO)时间复杂度O(1)push(x)在队尾插入元素xpop()弹出队首元素front()返回队首元素back()返回队尾元素empty()size()

priority_queue优先队列

按照一定的优先级进行排序, 默认情况下, 按照降序进行排序, 即最大元素位于队列的前面如果队列中的元素类型比较简单, 可以直接使用**greater<T>**来修改比较方法 函数描述时间复杂度push()在优先队列插入元素xO(logn)pop()弹出优先队列的顶部元素O(logn)top()返回优先队列的顶部元素O(1)empty()O(1)size()O(1) #include <bits/stdc++.h> using namespace std; struct Compare{ bool operator()(int a, int b){ return a > b; } }; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); priority_queue<int, vector<int>, Compare> pq; return 0; }

deque双端队列

允许在两端进行高效插入和删除操作, 其他的和queue一样

push_back(x)

push_front(x)

pop_back()

pop_front()

front()

back()

empty()

size()

clear()

例题讲解

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int m; cin >> m; queue<string> V, N; while(m--){ string op; cin >> op; if(op == "IN"){ string name, q; cin >> name >> q; if(q == "V"){ V.push(name); // 添加` } else { N.push(name); } } else if(op == "OUT"){ string q; cin >> q; if(q == "V"){ V.pop(); // 删除 } else { N.pop(); } } } while(V.size()){ // 队列不能遍历, 应该将队首的元素依次输出弹出并再次输出下一个队首元素 cout << V.front() << endl; V.pop(); } while(N.size()){ cout << N.front() << endl; N.pop(); } return 0; }

#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; priority_queue<ll, vector<ll>, greater<ll>> pq; // 修改比较函数, 默认为降序, 使用greater修改为升序, 同时要使用vector容器 // 输入 for(int i = 0; i < n; i++){ ll num; cin >> num; pq.push(num); } // 结果 ll result = 0; while(pq.size() >= 2){ // 保证队列元素大于等于2 ll x = pq.top(); pq.pop(); // 取出顶部元素再弹出 ll y = pq.top(); pq.pop(); // 取出顶部元素再弹出 result += x + y; // 将队列前两个元素相加并加到结果中 pq.push(x + y); // 最后放回队列中以便下一次使用 } cout << result << endl; return 0; } set

set集合

用于存储一组唯一的元素(不允许重复的元素存在, 当插入一个重复元素时, set会自动忽略该元素), 并按照一定的排序规则进行排序, 默认为升序

内部实现使用了红黑树(一种自平衡的二叉搜索数)来存储元素, 并保持元素的有序性, 这使得在set中插入, 删除和查找元素的时间复杂度都是对数时间, 即O(logn)

函数描述时间复杂度insert()插入O(logn)erase()删除O(logn)find()查找O(logn)lower_bound()返回第一个不小于给定值的迭代器O(logn)upper_bound()返回第一个大于给定值的迭代器O(logn)size数量O(1)empty检查是否为空O(1)clear清空O(n)begin()起始位置O(1)end()末尾O(1)rbegin()返回指向集合末尾位置的逆向迭代器O(1)rend()返回指向集合起始位置的逆向迭代器O(1) #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); set<int, greater<int>> mySet; // 修改set比较函数 mySet.insert(5); mySet.insert(2); mySet.insert(7); mySet.insert(1); mySet.insert(9); for(auto num : mySet){ cout << num << " "; } cout << endl; return 0; }

multiset多重集合

和set一样, 不同的是, multiset容易允许存储重复的元素

函数也和set一样

unordered_set无序集合

作为了解即可用于存储一组唯一的元素, 并且没有特定的顺序

代码示例

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); set<int> mySet; // 插入元素 mySet.insert(5); mySet.insert(2); mySet.insert(8); mySet.insert(2); // 重复元素 mySet.insert(1); // 遍历集合 for(auto num : mySet){ cout << num << " "; } cout << endl; // 查找元素 int searchValue = 5; auto it = mySet.find(searchValue); if(it != mySet.end()){ cout << searchValue << " found in the set." << endl; } else { cout << searchValue << " not found in the set." << endl; } // 移除元素 int removeValue = 2; mySet.erase(removeValue); for(auto num : mySet){ cout << num << " "; } cout << endl; // 清空 mySet.clear(); if(mySet.empty()){ cout << "Set is empty." << endl; } else { cout << "Set is not empty." << endl; } return 0; } #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); multiset<int> myMultiset; // 插入元素 myMultiset.insert(5); myMultiset.insert(2); myMultiset.insert(8); myMultiset.insert(2); // 允许重复元素 myMultiset.insert(1); // 遍历集合 for(auto num : myMultiset){ cout << num << " "; } cout << endl; // 移除元素 int removeValue = 2; myMultiset.erase(removeValue); // 将重复元素全部移除 // myMultiset.erase(myMultiset.find(removeValue)); // 移除一个 for(auto num : myMultiset){ cout << num << " "; } cout << endl; return 0; } map

map

是一种关联容器, 用于存储一组键值对(key-value pairs), 其中每个键(key)都是唯一的根据键来自动进行排序, 并可以通过键快速查找对应的值使用**红黑树(Red-Black Tree)**数据结构来实现, 具有较快的插入, 删除和查找时间复杂度, O(logn) 函数描述时间复杂度insert()插入O(logn)erase()删除O(logn)find()查找O(logn)lower_bound()返回第一个不小于指定键的迭代器O(logn)upper_bound()返回第一个大于指定键的迭代器O(logn)count(key)统计key的个数O(logn)size整个的数量O(1)empty检查是否为空O(1)clear清空O(n)begin()起始位置O(1)end()末尾O(1)

​

multimap

几乎不用类似于map, 但允许存储多个具有相同键的键值对erase删除元素时和mutiset类似

unordered_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 = { {1, "Apple"}, {2, "Banana"}, {3, "Orange"} }; // 插入元素 myMap.insert({4, "Grapes"}); // 查找和访问元素 cout << myMap[2] << endl; // 打印 for(auto num : myMap){ cout << "key: " << num.first << ", value: " << num.second << ' '; } cout << endl; // 删除元素 myMap.erase(3); // 判断元素是否存在 if(myMap.count(3) == 0){ cout << "key 3 not found." << endl; } // 清空 myMap.clear(); // 判断是否为空 if(myMap.empty()){ cout << "Map is empty." << endl; } return 0; } 总结

3226宝藏排序II

#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n; cin >> n; vector<ll> vec; // 输入 for(int i = 0; i < n; i++){ int x; cin >> x; vec.push_back(x); } // 排序 sort(vec.begin(), vec.end()); // 输出 for(auto num : vec){ cout << num << " "; } cout << endl; return 0; }

1624小蓝吃糖果

// 自己写的 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; priority_queue<int> pq; // 输入 for(int i = 0; i < n; i++){ int x; cin >> x; pq.push(x); } while(pq.size() >= 2){ int x = pq.top(); pq.pop(); int y = pq.top(); pq.pop(); while(x != 0 && y != 0){ x--; y--; } pq.push(x + y); } // 输出 if(pq.top() == 1){ cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }

// 解析 #include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n; cin >> n; ll sum = 0, mx = 0; for(int i = 0; i < n; i++){ ll x; cin >> x; mx = max(mx, x); sum += x; } // 不连续吃到两种同样的糖果 等价于 sum - mx >= mx - 1 if(sum - mx >= mx - 1){ // sum - mx: 其他的数量 // mx - 1: mx-1个空隙 // 其他的数量要大于等于空隙数量(也就是这些数的和必须得足够插入到空隙里面) cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }

2490小蓝的括号串1

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; string str; cin >> str; stack<int> stk; bool flag = true; for(int i = 0; i < n; i++){ if(str[i] == '('){ // 是'('则压栈 stk.push('('); } else { if(stk.size() && stk.top() == '('){ // 长度不为0并且栈顶为'('则弹栈(说明此时栈顶的元素是'('且匹配到的是')') stk.pop(); } else{ flag = false; // 此时说明长度不为0或者栈顶不是'(', 则')'无法匹配, 所以flag改为false } } } if(stk.size()){ // 栈中还有元素, 说明还有括号未配对, 则要将flag改为false flag = false; } cout << (flag ? "Yes" : "No") << endl; return 0; }

1531快递分拣

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; map<string, vector<string>> m; vector<string> citys; // 输入 for(int i = 0; i < n; i++){ string s, p; cin >> s >> p; if(!m.count(p)){ citys.push_back(p); } m[p].push_back(s); } // 输出 for(auto city : citys){ cout << city << m[city].size() << endl; for(auto i : m[city]){ cout << i << endl; } } return 0; } /* 10 1234 北京 5432 上海 asdf 天津 5674 北京 12345 上海 234sda 济南 346asd 成都 345678765 武汉 123425677 沈阳 123qwesd 成都 */ 编程6-10

#include <bits/stdc++.h> using namespace std; using ll = long long; ll n, x; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); map<ll, ll> cnt; cin >> n; for(int i = 0; i < n; i++){ cin >> x; cnt[x]++; } ll ans = 0; for(auto it : cnt){ if(it.second >= it.first){ ans += it.second - it.first; } else { ans += it.second; } } cout << ans << "\n"; return 0; }

#include<bits/stdc++.h> using namespace std; using ll = long long; const ll MAXN = 2e3 + 5; bitset<MAXN> b[MAXN]; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n; cin >> n; ll ans; string s; for(int i = 1; i <= n; i++){ cin >> s; s = " " + s; for(int j = i + 1; j <= n; j++){ b[i][j] = s[j] - '0'; } } /* 4 0011 0011 1101 1110 */ for(int i = 1; i <= n; i++){ for(int j = i + 1; j <= n; j++){ if(b[i][j]){ ans += (b[i] & b[j]).count(); } } } cout << ans << "\n"; return 0; }

#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n; cin >> n; map<string, ll> mp; for(int i = 0; i < n; i++){ string str; cin >> str; if(str == "find"){ string author; cin >> author; cout << mp[author] << "\n"; } else if(str == "add"){ string bookname, author; cin >> bookname >> author; mp[author]++; } } /* 7 find author1 add book1 author1 find author1 add book1 author1 find author1 add book1 author2 find author2 */ return 0; }

#include<bits/stdc++.h> using namespace std; using ll = long long; const ll MAXN = 2e5 + 5; ll a[MAXN]; map<ll, ll> mp; ll calc(ll x){ return mp[x] + mp[x - 1] + mp[x + 1]; } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for(int i = 0; i < n; i++){ cin >> a[i]; mp[a[i]]++; } /* 1: 0 1 2 2: 1 2 3 3: 2 3 4 */ ll ans = 0; for(int i = 0; i < n; i++){ ans = max(ans, calc(a[i])); ans = max(ans, calc(a[i] + 1)); ans = max(ans, calc(a[i] - 1)); } cout << ans << "\n"; return 0; }

#include<bits/stdc++.h> using namespace std; using ll = long long; const ll MAXN = 2e5 + 5; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n, q; cin >> n >> q; string s; cin >> s; // 010011 s = " " + s; set<ll> st; for(int i = 0; i < n; i++){ if(s[i] == '1'){ st.insert(i); } } while(q--){ ll ch, x; cin >> ch; if(ch == 1){ if(!st.size()){ cout << -1 << "\n"; } else { cout << (*st.begin()) << "\n"; } } else { cin >> x; if(s[x] == '1'){ st.erase(x); s[x] = '0'; } else { st.insert(x); s[x] = '1'; } } } /* 6 5 010011 1 2 2 1 2 6 1 */ return 0; }