这里的笔记是关于蓝桥杯关键知识点的记录,有别于基础语法,很多内容只要求会用就行,无需深入掌握。
文章目录
- 前言
- 一、编程基础
- 1.1 C++基础格式和版本选择
- 1.2 输入输出
- cin和cout:
- 1.3 string
- 以下是字符串的一些简介:
- 字符串的基本操作:
- 二、竞赛常用库函数
- 2.1 排序
- sort函数:
- 使用传入第三个参数自定义比较函数:
- 使用lambda自定义比较函数:
- 2.2 最值查找
- min和max函数:
- min_element和max_element:
- nth_element函数:
- 2.3 二分查找
- 整数二分查找模板
- 浮点二分查找模板
- 二分答案模板
- 跳石头题目
- 总结
前言
持续更新,千里之行始于足下
一、编程基础
1.1 C++基础格式和版本选择
这里只需要记住使用一个万能头文件即可:
#include <bits/stdc++.h> //什么都能用这个头文件
using namespace std;
基本数据类型:
int x = 3; //整数x
double d = 3.14; //浮点数(小数)
char ch = 'A'; //字符常量'A'
char s[] = "Hello"; //字符串
bool b = true; //布尔值,即真假值b。非0为真,0为假
1.2 输入输出
cin和cout:
#include <bits/stdc++.h> //万能头文件
using namespace std; //全局引用std,std里面包含了cin,cout和endl等等东西
int main(){double a,b;cin >> a >> b;//cin会自动判断变量类型cout << fixed << setprecision(3) <<a << '' << b << '\n';//fixed << setprecision(3)的意思是保留浮点数后面3位return 0;//记住最后return 0
}
fixed << setprecision(3) 意思是保留浮点数后3位
在字符或字符串中直接使用cin:
#include <bits/stdc++.h>
using namespace std;
int main(){char ch;cin >> ch;cout << ch;return 0;
}
以上代码中: 输入:a b 输出:a
#include <bits/stdc++.h>
using namespace std;
int main(){char s[10];cin >> s;cout << s;return 0;
}
以上代码中: 输入:hi nihao 输出:hi
注意!!cin无论是在字符或字符串中输入空格或者换行符就会结束
#include <bits/stdc++.h>
using namespace std;
int main(){string s;getline(cin, s);cout << s;return 0;
}
以上代码中: 输入:hi nihao 输出:hi nihao
所以我们可以结合使用string和getline来消除掉这个cin的缺点
取消同步流:
由于cin和cout自动判断变量的关系,它们的读写效率要比scanf和printf更低。
当数据量大的时候,可能导致程序运行超时,我们可以通过取消同步流来加速cin和cout,加速后效率就差不多了。
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); //取消同步流
1.3 string
使用string需要在头文件包含该库 #include<string>
以下是字符串的一些简介:
- 字符串管理:string封装了字符串的存储和管理。它自动处理字符串的内存分配和释放,避免了手动管理内存的麻烦。
- 动态大小调整:string可以根据需要自动调整字符串的大小,在添加或删除字符时,string会自动调整内部的存储容量,确保足够的空间来容纳字符串。
- 安全性:它提供了越界访问检查,以避免访问超出字符串范围的字符。
- 迭代器支持:string支持迭代器,可以使用迭代器遍历字符串中的字符,进行字符级别的操作。
- 兼容性:string是C++标准库的一部分,因此广泛使用。
string的声明和初始化:
#include <bits/stdc++.h>
#include <string>
int main(){//声明并初始化一个字符串std::string str1;//使用字符串字面量初始化字符串std::string str2 = "hello, world!";//使用另一个std::string 对象来初始化字符串std::string str3 = str2;//使用部分字符串初始化字符串std::string str4 = str2.substr(0, 5);//substr(起始位置,长度)//使用字符数组初始化字符串const char* charArray = "Hello";std::string str5(charArray);//使用重复的字符初始化字符串std::string str6(5, 'A');//"AAAAA"重复5次A
}
在C++中,std::string类提供了一个成员函数c_str(),用于返回一个指向以空字符结尾的C风格字符串(即const char*类型)。
字符串的基本操作:
1、获取字符串长度:
std::string str = "Hello, world!";
int length = str.length(); //或者 int length = str.size();
std::cout << "Length: " << length << std::endl;
2、拼接字符串(+或append):
std::string str1 = "Hello";
std::string str2 = "world";
std::string result1 = str1 + "," + str2;//使用+运算符
std::string result2 = str1.append(",").append(str2);//使用append函数
std::cout << "Result1 = " << result1 << std::endl;
std::cout << "Result2 = " << result2 << std::endl;
3、字符串查找(find):
std::string str = "Hello, world";
size_t pos = str.find("world"); //查找子字符串位置
if(pos != std::string::npos){ //判断是否不等于-1std::cout << "Substring found at position: " << pos << std::endl;
}
else{std::cout << "Substring not found." << std::endl;
}
4、字符串替换(replace):
std::string str = "Hello, world";
str.replace(7,5, "Universe"); //替换子字符串
//7是子串起始位置,5是要替换掉的长度
std::cout << "Result: " << str << std::endl;
5、提取子字符串(substr):
std::string str = "Hello, world";
std::string subStr = str.substr(7,5); //提取子字符串
std::cout << "Substring: " << subStr << std::endl;
6、字符串比较(compare):
std::string str1 = "Hello";
std::string str2 = "World";
int result = str1.compare(str2);//比较字符串
if(result == 0){std::cout << "String are equal." << std::endl;
} else if(result < 0){std::cout << "String 1 is less than String 2." << std::endl;
} else{std::cout << "String 1 is greater than String 2." << std::endl;
}
string重载了不等号,所以也可以直接使用s1 < s2的方式来比较string的大小,比较的规则是按照字典序大小进行比较。
字典序的比较方法是从小到大一个一个比较,一旦遇到不相等的字符就确定大小关系。
例如:
aaaa < bbbb
azz < baaa
常用的遍历string方法一共有两种:
- 循环枚举下标
- auto枚举(其中&表示取引用类型,如果对i修改将会改变原来的值)
string s = "Hello";for(int i = 0; i < s.length(); ++i) cout << s[i];//枚举循环遍历一遍string的对象s
cout << '\n';
for(auto i : s)
{cout << i;i = 'a';//此处的修改无效,因为这个i是拷贝出来的,而不是引用s的//所以这里只是赋值到拷贝出来的i里面,而这个i是在局部变量内,这个for循环结束就消亡了
}
cout << '\n';
//此时s = "Hello"
for(auto &i : s)
{cout << i;//此时再遍历输出s字符串还是Helloi = 'a';//此处修改会改变s的字符值
}
cout << '\n';
//此时s= "aaaaa"
cout << s << '\n';
二、竞赛常用库函数
2.1 排序
sort函数:
sort函数包含在头文件<algorithm>中
在使用前需要使用#include <algorithm>或万能头文件#include <bits/stdc++.h>
sort是C++标准库中的一个函数模板,用于对指定范围内的元素进行排序。
sort算法使用的是快速排序或者类似快速排序的改进算法,具有较好的平均时间复杂度,一般为O(nlogn)。
sort的用法:
sort(起始地址, 结束地址的下一位, *比较函数);
比较函数一般默认用的小于号(<)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int a[1000];
int n;
//读取数组大小
cin >> n;
//读取元素
for(int i = 1; i <= n; ++i) cin >> a[i];//对数组进行排序
sort(a+1, a+n+1); //[1, n+1) 左闭右开
// a[1], a[n+1]//输出
for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
return 0;
}
sort(起始地址, 结束地址的下一位, *比较函数);
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//初始化v
//这里是模板类vector,需要使用万能头文件或#include <vector>
vector<int> v = {5, 1, 3, 9, 11};//对数组进行排序
sort(v.begin(), v.end());//输出
for(int i = 0; i < v.size(); ++i) cout << v[i] << ' ';
//for (auto i : v)cout << i << ' ';//使用auto进行排序也可以
return 0;
}
由于sort默认用小于号进行排序,如果想要自定义比较规则,可以传入第三个参数,这个参数可以是函数或者lambda表达式。
使用传入第三个参数自定义比较函数:
#include <bits/stdc++.h>
using namespace std;
bool cmp(const int &u, const 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);// 传入函数名//输出for(int i = 0; i<v.size(); ++i) cout << v[i] << ' ';return 0;
}
使用lambda自定义比较函数:
#include <bits/stdc++.h>
using namespace std;
int main(){//初始化vvector<int> v = {5, 1, 3, 9, 11};//对数组进行排序,降序排序,这里使用lambda表达式sort(v.begin(), v.end(), [](const int &u, const int &v){return u > v;});for(int i = 0; i<v.size(); ++i) cout << v[i] << ' ';return 0;
}
在[ ]里面不写东西代表把数组内的东西以拷贝的形式放进去,如果在[ ]内加上&后( [&] )就会变成把v里面的变量都以引用(&)类型的格式放进去。
下面是一个本人觉得很妙的操作:
for(int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
首先,这里我们需要意识到字符串其实就是一个字符数组。在这段代码行中的" \n"[i == n]巧妙的利用了判断符号来确认for循环是否到结尾了,如果到结尾了此时判断会返回1(真),就会自动输出\n换行。如果没到结尾,即i不等于n,此时返回的是0(假),则输出空格。
在这个字符串中下标为0对应的是" “(空格),下标为1对应的是”\n"(回车换行符)
以下是使用了这个操作的题目:
2.2 最值查找
min和max函数:
min(3, 5) = 3
min({1, 2, 3, 4}) = 1
max(a, b)返回a和b中较大的那个值,只能传入两个值,或传入一个列表。
例如:
max(7, 5) = 7
max({1, 2, 3, 4}) = 4
时间复杂度为O(1),传入参数为数组时时间复杂度为O(n),n为数组大小。
min和max函数是在最值操作时最常用的操作。
min_element和max_element:
min_element(st, ed)返回地址[st, ed)中最小的那个值的下标(迭代器),传入参数为两个地址或迭代器。
max_element(st, ed)返回地址[st, ed)中最大的那个值的下标(迭代器),传入参数为两个地址或迭代器。
时间复杂度均为O(n),n为数组大小(由传入的参数决定)
//初始化v
vector<int> v = {5, 1, 3, 9, 11};//输出最大的元素,*表示解引用,即通过地址(迭代器)得到值
cout << *max_element(v.begin(), v.end()) << '\n';
nth_element函数:
nth_element(st, k, ed)
进行部分排序,返回值为void()
传入参数为三个地址或迭代器。其中第二个参数位置的元素将处于正确位置,其他位置元素的位置可能是任意的,但前面的都比它小,后面的后比它大。时间复杂度O(n)。
//初始化v
vector<int> v = {5, 1, 7, 3, 10, 18, 9};//输出最大的元素,*表示解引用,即通过地址(迭代器)得到值
nth_element(v.begin(), v.begin() + 3, v.end());
//这里v[3]的位置将会位于排序后的位置,其他的任意
for(auto &i : v) cout << i << ' ';
课后题目:
2.3 二分查找
二分法是一种高效的查找方法,它通过将问题的搜索范围一分为二(两边有明显的区别),迭代地缩小搜索范围,直到找到目标或确定目标不存在。
二分法适用于有序数据集合,并且每次迭代可以将搜索范围缩小一半。
二分法本质也是枚举,但和暴力枚举不同,二分法利用数据结构的单调性减少了很多不必要的枚举,从而极大的提高了效率,一般可以将O(n)的枚举优化到O(logn)。
常见的二分类型有:
- 整数二分
- 浮点二分
- 二分答案(最常见)
整数二分查找模板
//找到升序数组a中的x第一次出现的位置
int l = 0, r = 1e9;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while(l + 1 != r)//l,r相邻的话退出
{int mid = (l + r) / 2;//如果a为升序,说明mid偏大了,需要减小mid,就只能将r变小,即r = midif(a[mid] >= x) r = mid;else l = mid;//否则l = mid,始终保持在所属区域
}
cout << r << '\n';
浮点二分查找模板
//计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e-6;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while(r - l >= eps)//eps是一个极小量,设置为1e-6比较适合
{double mid = (l + r) / 2;//f(x)单调递增,f(mid) >= 0,说明mid偏大了,需要减小mid,就只能将r变小,即r = midif(f(mid) >= 0) r = mid;else l = mid;
}
//最后返回l,r差别不大
cout << r << '\n';
二分答案模板
bool check(int mid)
{bool res = true;//其他内容return res;
}
int main()
{int l = 0, r = 1e9;while(l + 1 != r){int mid = (l + r) / 2;//具体写法需要根据题意修改if(check[mid] >= x) l = mid;else r = mid;
}
cout << l << '\n';//具体输出的内容需要根据题意判断
跳石头题目
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 9;
int a[N];
int L,n,m;
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];int l = 0,r = 1e9 + 5;while(l + 1 != r){int mid = (l + r) >> 1;// >> 1等价于/2。使用这个的原因是因为位运算比除法运算更快,且可以避免溢出if(check(mid) <= m) l = mid;else r = mid;}cout << l << '\n';return 0;
}
解题思路:
这里我们要先假设最短跳跃距离的最大值是从0~L