当前位置：首页 > article >正文

蓝桥杯 1.语言基础

article 2025/2/23 17:06:44

蓝桥杯 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, 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.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之间的和, 初始值为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$ 作为答案, 那么答案区间在 $[l + 1, r]$ , 若以l作为答案, 那么答案区间在 $[l, r - 1]$
中点 $mi d = (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, 321
- abc, 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)在栈顶插入元素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; // 4
    
    return 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){ // 保证队列元素大于等于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

是一种关联容器, 用于存储一组键值对(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;
}