蓝桥杯乱杀
一、STL 一些常见算法用到
一、各个容器
一、vector动态容器
vector<int> v;
vector.push_back(1);
vector.push_back(2);
vector.pop_back(1);
vector.clear();
vector<int> mat[10005]; //10005个数 每个数是vector类型锯齿形矩阵
二、set集合
| 函数 | 复杂度 | |
|---|---|---|
| insert | 插入一个 | O(logn) |
| erase | 删除一个 | O(logn) |
| count | 统计个数 (set不能重复所以返回1) | O(logn) |
| size | 长度 | O(1) |
| clear | 清除内容包括空间 | O(n) |
最主要的是set能够去重而且能够从小到大排序
for(set<int>::iterator it=x.begin(); it!=x.end(); it++)
cout<<*it<<endl;multiset
最主要的是multiset不去重而且能够从小到大排序
三、map映射
map中按照key值排序
map<string,int> dict;
dict.insert(make_pair("Tom",1)); //不能改变原先已存在的key-value
dict.insert(make_pair("Lisi",1));
dict["Tom"]=2; //可以改变原先已存在的key-value
a=dict.count("Tom"); //a=1; 判断是否存在
for(map<string,int>::iterator it=dict.begin(); it!=dict.end(); it++){ //迭代器遍历
cout<<it->first<<" "<<it.second<<endl;
}
dict.clear();四 、stack栈
| 函数 | 功能 |
|---|---|
| push() | 入栈，从栈顶放入一个元素在里面 |
| pop() | 出栈，从栈顶拿出一个元素 |
| top() | 获取栈顶元素 |
| empty() | 判断是否为空 为空返回1 |
| size() | 计算元素个数 |
五、queue队列
出队从第一个出，进队加在最后面
| 函数 | 功能 |
|---|---|
| push() | 入队，在队尾插入一个元素 |
| pop() | 出队，从队首拿出一个元素 |
| first() | 获取队首元素 |
| empty() | 判断是否为空 为空返回1 |
| size() | 计算元素个数 |
六、 pair模版类型
个人理解相当于一个结构体吧 有两个变量 ,在bfs中经常用到
typedef pair<int,int> P
P start(1,2),end(7,8);
cout<<start.first<<" "<<start.second<<endl; //输出1 2
start={3,4};
cout<<start.first<<" "<<start.second<<endl; //输出3 4
start.first=5;
start.second=6;
cout<<start.first<<" "<<start.second<<endl; //输出5 6
queue<P> q;
q.push({1，2})赋值方式如上 最好用的一点就是pair能不用实例化就调用 {a,b}就是一个pair类型的数据 两个数据 第一个为first，第二个为second
常常用#define x first 和#define y second 代替
二、 dp算法 （动态规划）（未完成）
最重要的是找到状态转换方程 一般根据最后一步想前面的步骤
#include<bits/stdc++.h>
using namespace std;
long long d[25][25];
int main()
{
int f[25][25],a,b,c,e;
cin>>a>>b>>c>>e;
d[c][e]=1;
if(c-1>=0)
{
d[c-1][e+2]=1;
if(e-2>=0)
d[c-1][e-2]=1;
}
if(c-2>=0)
{
d[c-2][e+1]=1;
if(e-1>=0)
d[c-2][e-1]=1;
}
if(e-2>=0)
d[c+1][e-2]=1;
if(e-1>=0)
d[c+2][e-1]=1;
d[c+1][e+2]=1;
d[c+2][e+1]=1;
for(int i=0;i<=a;i++)
{
for(int j=0;j<=b;j++)
{
if(d[i][j]==1)
f[i][j]=0;
else
{
if (i==0&&j==0)
f[0][0]=1;
else if (i==0&&j!=0)
f[0][j]=f[0][j-1];
else if(j==0&&i!=0)
f[i][0]=f[i-1][0];
else
f[i][j]=f[i-1][j]+f[i][j-1];
}
}
}
cout<<f[a][b];
return 0;
} 三、深度优先搜索（dfs）（未完成）
未完待续
dfs可以找到所有方案
不仅仅是迷宫的搜素 ，其实深搜更常用的是暴力枚举
四、广度优先搜索（bfs）（未完成）
bfs可以找到最小步数 最优解
五、双指针
六、贪心
怎样一个方法 思维得到最优解 一般看出来 可以证明
七、背包问题
八、图
二 、 一些需要注意的地方
- 当你需要用2的n次方时，不建议使用pow(2,n)，建议使用(1LL<<n) 表示左移n位，因为前者数字过大之后会不准确
- scanf(“%lf”,)和printf(“%llf”,n) 或者printf(“%I64d”,n) 注意 前面的l是小写的L,l 后面一定要用i的大写I 表示输出的为long long,不过建议用后者，因为是官网的推荐
- 用scanf时一定要注意后面的取地址符 &，使用if时()中一定是==注意细节
- cout<<std::fixed<<a<<endl; 表示输出的a不用科学计数法 这样来输出一些很大或者是double小数位很多
- 必须要吐槽的一点devc++ 数组越界特别是轻微的越界 可能不会影响结果 而且正常编译出正确结果，但蓝桥杯测评中会报错直接0分，真是吐啦。
三、一些很有用的知识&特定技巧&实用模板
一、string与int的相互转换
1.string转int
int a;
string str;
a = atoi(str.c_str());
cout<<typeid(a).name()<<endl; //输出结果为i 表示int利用atoi()函数可直接将字符串类型转换成int类型 ，该函数定义在stdlib.h头文件中，若输入的不是数字字符，那么返回值为0.
值得注意的是如果为数字加其它的混合则取前面的数字 eg：str=”20LZH45” 最后 a=20
2.int转string
void i2s(int i,string &s){
stringstream ss;
ss<<i;
ss>>s;
}
int a=10;
string _a;
i2s(a,_a);
cout<<typeid(_a).name()<<endl; //输出结果为A3_c 表示一个长度为2的字符串利用stringstream字符串流去实现转换，它将流与存储在内存中的string对象绑定起来。不仅是int， double，long long 等都可以根据此函数去改写即可 ,记住需要加入头文件
二、关于sort()函数
1.从小到大
int a[5]={2,1,3,5,4};
sort(a,a+5);
//或者是 sort(&a[0],&a[5])；
for(int i=0;i<5;i++)
cout<<a[i]<<" "; //输出结果为 1 2 3 4 5sort(a,b) sort函数中a值为需要排序的第一个数的地址,而b值为最后一个数的地址的下一位 在上述代码中为 a+5或者是&a[5]。
2.从大到小
bool complare(int a,int b){
return a>b;
}
int a[5]={2,1,3,5,4};
sort(a,a+5,complare);
//或者是 sort(&a[0],&a[5])； //greater<int>()
for(int i=0;i<5;i++)
cout<<a[i]<<" "; //输出结果为5 4 3 2 1规则如上从小到大相同，只是在sort()里内第三位需要添加bool类型的函数，如上代码即可
这里既然提到添加bool函数 其实自己也能进行改写从而灵活运用 eg:比较两个结构体stu学生的年龄age如下
`bool comlare(stu a,stu b) {return a.age>b.age; //从大到小为>,从小到大为< } `- 若为string排序 也可以为sort(s.begin(),s.end())；
三、关于全排列的枚举
string s="7215436";
sort(s.begin(),s.end());
do{
cout<<s<<endl;
}while(next_permutation(s.begin(),s.end()));先从小到大排序，用next_permutation()函数，这样输出的s是1234567的所有全排列。
四、关于字符串的切片
string s1="0123456789";
string s2=s1.substr(4,5);
cout<<s2<<endl; //最后输出为45678注意s.substr(a,b)并不是更新s的内容，而是生成新的字符串，a是起始的位置，b是包括a开始的长度 而不是末位置。
不能反复的截取字符串，特别是在一些时间复杂度很高的循环里面，重新生成字符串在拷贝很费时间，因为要扫描原串
五、关于组合数
int ans=0;
int a[]={0,0,0,0,0,0,0,1,1,1,1,1};
do{
ans++;
} while(next_permutation(a,&a[12]));
cout<<ans<<endl; //输出792 为C12 5的组合数使用全排列进行组合数的枚举 先声明一个数组Cm n 有m-n个0，n个1 用next_permutation()进行枚举。排列中1的位置代表选的数的位置
六、关于进制转换
a=17;
printf("%d",a); //十进制输出 17
printf("%o",a); //八进制输出 21
printf("%x",a); //十六进制输出 11
//而对于其他进制推荐使用itoa()函数
char s[10];
itoa(a,s,3);
printf("%s",s); //3进制输出 122
//或者直接手写其他进制使用printf()进制输入 只能输出八、十、十六进制, itoa转换可以任意 但注意不要超过字符数组界限 值得一提的是 itoa函数并不是标准库当中的，不知道蓝桥杯可不可以，可能会属于c++11的新特性？,以防万一遇到二进制编程大题等建议手写
七、关于时间
if((double)clock()/1000>=0.95){
puts("NO");
exit(0);//return 0;用来显示你最后是否超过时间，虽然根据数据规模复杂度一看就知道 ，emm 还是可以用用，自己直接读取几个大的数据试试时间
八、关于快速幂
long long pow_a(int a,int b){
int x=a;
long long res=1;
while(b>0){
if(b&1)
res*=x;
b>>=1; //右移一位
x=x*x;
}
return res;
}
cout<<pow_a(2,10)<<endl; //输出1024因为pow函数返回的是double 用于整型的运算可能会出问题 ，干脆自己写一个 注意不要超过longlong 否则返回值为0；如果是2的n次方 那么直接用2<<(n-1)就行
九、关于最大公约数 gcd
int gcd(long long a,long long b){
if(b==0) return a;
else return gcd(b,a%b);
}四、特定思维
遇到区间和 想前缀和的思想去优化
遇到最优解 1.暴力枚举 dfs，bfs 2.动态规划 3.背包 4.贪心
全排列+连通性检测 (走过就记0，走完就+1，看结果是否为1 )此dfs可以检测T字形
五、一些建议
- 做题时一定要仔细，多出几个测评结果，最好能有边界等特殊的例子来测评可以进一步来检验自己的结果
cout<<count(s2.begin(),s2.end(),’8’)<<endl;;
cout<<s2.find(‘8’,8); //后面的表示从第多少个位置开始找 缺省表示从头开始
- str.erase (10,8);
- cout << str << endl;
（1）erase( pos, n); 删除从pos开始的n个字符，例如erase( 0, 1)，删除0位置的一个字符，即删除第一个字符
int n1=strlen(a[1]);
char s[100];
sprintf(s,”%x”,n);
.std::ios::sync_with_stdio(false);
#define endl “\n”
如果这个返回值不是 00 ，说明程序出了问题。
3221225477 (0xC0000005): 访问越界，一般是读或写了野指针指向的内存。
3221225725 (0xC00000FD): 堆栈溢出，一般是无穷递归造成的。
3221225620 (0xC0000094): 除0错误，一般发生在整型数据除了0的时候。
一句话总结：这些特别大的数，一般说明程序 RERE 了，要好好检查。
1.lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。
2.upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。
3.binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。
