蓝桥杯乱杀

一、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 mu;

最主要的是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 5

sort(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值。

算法总结(蓝桥杯)