蓝桥杯 1.语言基础
文章目录
- 蓝桥杯 1.语言基础
- 编程基础
- C++版本和基础格式
- 输入输出
- string的使用
- 编程1-5
- 竞赛常用库函数
- sort()
- 最值查找
- 二分查找
- 大小写转换
- 全排列
- 其他库函数
- STL
- pair
- vector
- list
- stack
- queue
- set
- map
- 总结
- 编程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, Worldcout << "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)
// lengthstring str = "Hello, World!";int length = str.length();
// int length = str.size();cout << length << endl;
- 拼接字符串(+或append)
// + appendstring 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即为-1string 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)
// replacestring str = "Hello, World!";str.replace(7, 5, "Universe"); // (起始位置, 替换的长度, 替换字符串) cout << str << endl;
- 提取子字符串(substr)
// substrstring str = "Hello, World!";string str3 = str.substr(7, 5); // substr(起始位置, 长度(不要越界)) cout << str3 << endl;
- 字符串比较(compare)
// comparestring str1 = "Hello"; string str2 = "World!"; int result = str1.compare(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之间的和, 初始值为0return 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); // 初始化vvector<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); // 初始化vvector<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; // 3cout << min({1,2,3,4}) << endl; // 1cout << max(3, 5) << endl; // 5cout << max({1,2,3,4}) << endl; // 4return 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; // 11return 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上面有=, 则输出rightreturn 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中的第二个3for(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.14cout << p2.first << ", " << p2.second << endl; // a, helloreturn 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, 42, 13, 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位置插入元素3for(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也可以写成autocout << 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; // 3return 0;
}
stack
定义和结构
- 是一种后进先出LIFO(Last In First Out)的数据结构
- 头文件
<stack> - 时间复杂度O(1)
- 不能遍历
- 如果将一个数组的元素依次放入栈, 再依次取出, 则可以将数组翻转
常用函数
- push(x)在栈顶插入元素x
- pop()弹出栈顶元素
- 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; // 4return 0;
}
queue
queue队列
- 先进先出(FIFO)
- 时间复杂度O(1)
- push(x)在队尾插入元素x
- pop()弹出队首元素
- front()返回队首元素
- back()返回队尾元素
- empty()
- size()
priority_queue优先队列
- 按照一定的优先级进行排序, 默认情况下, 按照降序进行排序, 即最大元素位于队列的前面
- 如果队列中的元素类型比较简单, 可以直接使用**
greater<T>**来修改比较方法
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
| push() | 在优先队列插入元素x | O(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){ // 保证队列元素大于等于2ll 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 - 1if(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改为falseflag = 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;
}/*101234 北京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]++;}}/*7find author1add book1 author1find author1add book1 author1find author1add book1 author2find 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 22: 1 2 33: 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; // 010011s = " " + 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 501001112 212 61*/return 0;
}