网站建设前期开发,做付费网站站长全自动年赚30万,宁波pc营销型网站制作,手机网站报价单模板下载这里的笔记是关于蓝桥杯关键知识点的记录#xff0c;有别于基础语法#xff0c;很多内容只要求会用就行#xff0c;无需深入掌握。 文章目录 前言一、编程基础1.1 C基础格式和版本选择1.2 输入输出cin和cout#xff1a; 1.3 string以下是字符串的一些简介#xff1a;字符串… 这里的笔记是关于蓝桥杯关键知识点的记录有别于基础语法很多内容只要求会用就行无需深入掌握。 文章目录 前言一、编程基础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; //全局引用stdstd里面包含了cincout和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需要在头文件包含该库 #includestring
以下是字符串的一些简介
字符串管理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(a1, an1); //[1, n1) 左闭右开
// a[1], a[n1]//输出
for(int i 1; i n; i) cout a[i] ;
return 0;
}sort(起始地址, 结束地址的下一位, *比较函数);
#includebits/stdc.h
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//初始化v
//这里是模板类vector需要使用万能头文件或#include vector
vectorint 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);//初始化vvectorint v {5, 1, 3, 9, 11};//对数组进行排序降序排序sort(v.begin(), v.end(), cmp);// 传入函数名//输出for(int i 0; iv.size(); i) cout v[i] ;return 0;
}使用lambda自定义比较函数
#include bits/stdc.h
using namespace std;
int main(){//初始化vvectorint 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; iv.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
vectorint 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
vectorint 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;
//注意这里的判断条件这样可以保证lr最终一定收敛到分界点
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;
//注意这里的判断条件这样可以保证lr最终一定收敛到分界点
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;
}
//最后返回lr差别不大
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;//具体输出的内容需要根据题意判断总结
