2021年hznu寒假集训第一天
对于常用语言c++的认识
绝大部分情况下用C++（效率高、code速度快），少数情况用Java（有大数）、Python（兼容度不高）
输入cin >>a
输出cout<<a
cout<<a<<endl = cout<<a<<"\n"
下面举一个比较常见的输出例子
cout<<i<<": "<<s1[i]<<endl
万能头文件 #include<bits/stdc++.h>
数组尽量放全局
数组尽量开大
时间（空间）复杂度
时间复杂度：又称时间复杂性，用来描述程序运行时间与输入数据规模的函数关系
算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
常见算法的复杂度O(n) O(n^2)
O(nlogn) O(2^n)
类比于高等数学的极限学习就是高阶与低阶同时存在，我们只需要看高阶的
STL
STL：C++标准模板库（Standard Template Library）
容器：string vector queue stack set map list
函数：sort reverse next_permutation
String
string即动态长度字符串。
在c语言之中，我们所用的字符串是一种字符数组，而在c语言当中，我们所用的才是真正意义上的字符串。
构造函数
string s1="123";//"123"
string s2("123456");//"123456"
string s3(5,'a');//"aaaaa"
string s4("123456",3);//"123"
string s5("123456",2,4);//"3456"
迭代器
本质就是指针
string::iterator it;
// string是stl里面的容器名称，指针的名称叫做it
string::iterator it=s2.begin();
it++;//即指向下一个
cout<<(*it)<<endl;
还有一种就是s2.end();
begin是首位置，end是末位置
不同的是 s2是指向末位置之后的那个位置，因为在工程里面，大部分写区间都是左闭右开。
因为string::iterator比较长，我们可以直接写auto，auto即自动，自动去识别右边类型，让左边的类型等于它。
常用函数
s2.clear();
//清空s2
s2.length();
//s2的长度
s2.append("123");
//在s2后面加上字符串"123" 等同于+="123"
//c++的字符串之间可以直接比较，这一点也区分与c语言
s2.push_back('1');
//与append不同，push_back只能加字符
//其实在更多时候，我们直接用+=就好
int p=s2.find("12");
//寻找s2中字符串"12"的位置，如果找到，输出位置，否则输出-1
s2.erase(s2.begin());
//把s2的首字符删除
s2.erase(s2.begin(),s2.begin()+3);
//s2的首位置到＋3的位置删除
vector
动态数组，内存连续
因为动态数组，无需设置大小，可以解决数组不够大的问题。
写法：
vector<int>v1;
vector<int>v2(2);
//v2数组里面全是2；
vector<int>v3({1,2,3,4,5});
//v3数组里面存放的就是1,2,3,4,5
vector<int>v4(v3);
//v4拷贝数组v3；
内部原理：
比如一开始放入一个1；
此时容量是1，大小也是1；
如果要再放一个2，肯定是放不下的，就要重新扩展一个空间，容量是2，大小也是2；
如果要再放一个3，又放不下，要重新扩展一个空间，容量是4，大小是3的
每次开辟都是翻一倍
常用函数
a=v3.size();
//v3里有几个元素，v3.size就是几
v3.push_back(7);
//在数组末尾添加一个数7
v3.pop_back();
//将尾部元素删除
v3.empty();
//如果v3为空，返回true，否则返回false
a=v3.front();
//a=v3(0);
a=v3.back();
//a=v3(v3.size()-1);
v3.insert(v3.begin(),4);
//在第一个位置之前插入4这个元素
v3.erase(v3.begin());
//把v3的首个元素删除
v3.erase(v3.begin(),v3.begin()+3);
//s2的首位置到＋3的位置的元素删除删除
queue
队列，先进先出（FIFO） 不支持下标访问
打印机，排队队伍都是队列模型
写法：
queue<int>qu;
//与前面的vector相同
常用函数：
qu.push(1);
//拉来一个1元素
qu.pop();
//走了1个元素
qu.front();
//队列中的第一个元素
qu.back();
//队列中的最后一个元素
qu.size();
//队列里共有几个元素
qu.empty();
//如果qu为空，返回true，否则返回false
也可以用数组来模拟
stack
堆栈，先进后出（FILO）
类似于人依次卡在井中，后卡住的人可以先出来
写法：
stack<int>st;
常用函数：
st.push(1);
st.push(2);
st.push(3);
//依次掉进来元素1,2,3
st.pop();
//那么3先出去
st.top();
//相当于front的东西，因为是掉进井里，所以用top
st.size();
st.empty();
set
集合，元素有序排列，不重复
写法：
set<int>se;
常用函数：
se.insert(1);
//集合se中插入一个元素1,不管插入几次1，集合中只会存在一个1
se.erase(1);
//把集合se中的1给删除掉
se.erase(se.begin());
//也可以使用迭代器,把se的第一个元素删掉
se.clear();
se.size();
//同上
se.count(1);
//返回集合中1的个数，因为集合中至多存在一个，所以常拿来判断是否存在该元素
se.find(1);
//如果存在，则返回迭代器位置；否则，se.find(1)=se.end()
lower_bound(x);
//大于等于x的第一个元素位置，不存在返回end()
upper_bound(x);
//大于x的第一个元素位置，不存在返回end()
erase在删除这个数之后，会把他之后的迭代器给返回。
如果erase删除的元素不存在，那其实还会正常运行，不过不影响罢了。
先举一个错误案例
int main(){
set<int>se;
for(int i=1;i<=10;i++){
se.insert(i);
}
for(auto it=se.begin();it!=se.end();it++){
if((*it)%2==1){
se.erase(it);
}
}
for(auto x:se){
cout<<x<<endl;
}
}
因为it的迭代器还指在这个位置，你就给他删了，接下来他就不知道跑哪里去了。
正确做法
int main(){
set<int>se;
for(int i=1;i<=10;i++){
se.insert(i);
}
for(auto it=se.begin();it!=se.end();){
if((*it)%2==1){
it=se.erase(it);
}
else{
it++;
}
}
for(auto x:se){
cout<<x<<endl;
}
}
查询、插入、删除O(logn）
map
字典，key-value键值对，按key有序排列
写法：
map<int,int>mp;
例子：
map<int,int>mp;
mp[6]=2;
mp[4]=123;
for(auto it=mp.begin();it!=mp.end();it++){
cout<<(it->first)<<" "<<(it->second)<<endl;
}
输出
6 2
4 123
常用函数：
mp.find();
mp.erase(6);
//可以直接用key来删除
mp.erase(mp.find(6));
//也可以通过找key的迭代器位置来删除；
mp.size();
//字典大小
lower_bound(x);
upper_bound(y);
//同集合，不过是对key来说
mp.count();
//同集合
在查询时直接输出很容易冗余，所以我们常用
if(mp.count(100))cout<<mp[100];
也可以像数组一样通过[]访问
插入删除O(logn）
list
双向链表，内容不连续
写法：
list<int>li;
例子：
li.push_back(5);
li.push_front(6);
for(int x:li)cout<<x<<endl;
输出
5
6
常用函数：
li.push_back(5);
//链表在尾部添加5；
li.push_front(6);
//链表在头部添加6；
li.insert(it,10);
//（使用前要先设置迭代器）在it位置前插入10
li.erase(it);
//把it位置上的数删掉
li.pop_back();
//删除最后一个元素
li.pop_front();
//删除第一个元素
不支持随机访问，插入、删除O(1)，与vector相反
list在acm比赛用到的不多，基本是用不到的
常见的三个函数
sort
写法：
sort(x+1,x+1+n);
//x+1首位置，x+1+n末尾位置，排完之后从小到大
sort(x+1,x+1+n，greater<int>());
//排完之后从大到小
//此外还有一种写法
bool cmp(int a,int b){
return a>b;
}
sort(x+1,x+1+n,cmp);
//
sort(x+1,x+1+n,[](int a,int b){
if(a%2==b%2)return a<b;
return a%2>b%2;
});
reverse
翻转数组，容器
写法：
int x[1005];
reverse(x+1,x+1+n);
vector<int>ve;
reverse(ve.begin(),ve.end());
next_permutation
求全排列中字典序更大的一个序列，不存在更大时返回false
int x[105];
int n=5;
for(int i=1;i<=n;i++)x[i]=i;
do{
for(int i=1;i<=n;i++)printf("%d ",x[i]);
puts("");
}while(next_permutation(x+1,x+1+n));
pre_permutation与之相反，是一个更小的序列