写在前面
本文章面向第十四届蓝桥杯考生，在最后考前几天，方便自己总结与回顾，同时将其分享给大家，希望我们都能取得心仪的成绩。
本文章主要给出代码模版，对算法具体流程不会具体讲解，所以不太适合零基础的同学，适用于有一定算法基础，在考前想要进行复习与总结的同学。
文章大部分代码模版参考于y总，同时自己添加了一些常考知识点，y总代码模版参考处。
由于时间紧迫，给出了部分选看内容，如果学有余力的同学可以了解一下，在考试中可以多过一些测试点，多拿一些分。
一、年份日期问题
1、闰年判定
闰年：年份能够被4整除但不能被100整除或者能被400整除的为闰年。
代码模版
bool isryear(int n){
return n%400==0||(n%4==0&&n%100!=0);
}
2、月份天数
口诀：一三五七八十腊，三十一天永不差。闰年2月29天，平年2月28天。
代码模板
//也可以将数组第一个位置空出来，即填上一个随意的值，这样就可以将月份和数组下标对应了，方便访问
int pmonths[]={31,28,31,30,31,30,31,31,30,31,30,31}; //平年每月天数
int rmonths[]={31,29,31,30,31,30,31,31,30,31,30,31}; //闰年每年天数
二、简单算法
1、前缀和
一维前缀和
预处理出s[]，s[i]存储前i个数的和
s[i]=a[1]+a[2]+...+a[i]
计算[l,r]区间和=s[r]-s[l-1]
二维前缀和
左上角坐标为(1,1)，右下角坐标为(i,j)的前缀和（区域内所有数的和）
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]
求左上角坐标为(x1,y1)，右下角坐标为(x2,y2)的前缀和
s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]
参考例题：这里
2、差分
一维差分
int b[N]; //b为差分数组，直接定义为全局即可，如果要对某个数组进行差分操作，直接先将该数组中每个数进行insert(i,i,a[i])操作即可得到a的差分数组b
//对区间[l,r]进行差分操作时
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
//差分完后对b数组求前缀和即可，求完前缀和后的b数组即进行完对某些区间加减某个数操作后的原数组
二维差分
int b[N][N]; //差分数组
//对左上角坐标为(l1,r1)，右下角坐标为(l2,r2)的矩阵进行差分操作时
void insert(int l1,int r1,int l2,int r2,int c){
b[l1][r1]+=c;
b[l1][r2+1]-=c;
b[l2+1][r1]-=c;
b[l2+1][r2+1]+=c;
}
//同样，差分操作完成后对b数组求前缀和，即可得到对原数组某些区域加减某个数后操作的原数组
参考例题：这里
3、二分
//首先确定区间的二段性：二部分分别满足不同的性质。以任意一部分的性质作为check条件，如果mid满足check判断区间应该缩小到哪部分，如果在[l,mid]利用模板1，如果在[mid,r]利用模板2
//模版1
int l=0,r=n; //二分区间[l,r]
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
//模版2
int l=0,r=n; //二分区间[l,r]
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
//算法结束l=r,l、r均为结果
参考例题：这里
4、并查集
代码模板
int p[N]; //祖宗结点数组
for(int i=1;i<=n;i++) p[i]=i; //初始化
int find(int x){ //查找祖宗结点
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
p[find(a)]=find(b); //合并a,b集合
参考例题：这里
二、简单数论
1、质数判定
试除法判定质数：时间复杂度O(n2)
代码模板
bool isprimes(int n){
if(n<2) return false;
for(int i=2;i<=n/i;i++){
if(n%i==0) return false;
}
return true;
}
2、筛质数
埃氏筛法：时间复杂度O(nloglogn)
代码模板
bool st[N]; //存储每个数是否被筛掉
int primes[N],cnt; //primes[]存储每个质数，cnt记录质数的数量
void getprimes(int n){
st[0]=st[1]=true;
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i){
st[j]=true;
}
}
}
}
线性筛法：参考我的该篇博客
参考例题：这里
3、进制转换
（1）其他进制转十进制
利用秦九韶算法O(n)时间计算n进制数转十进制的结果（n小于10，n大于10时特殊判断A~Z字母即可）
//传入为string类型
int ntoten(string s,int n){ //n表示传入的是多少进制数，s为n进制数
int ans=0;
for(int i=0;i<s.size();i++){
ans=ans*n+s[i]-'0';
}
return ans;
}
//传入为数组，num为数组中元素个数
int ntoten(int a[],int num,int n){
int ans=0;
for(int i=0;i<num;i++){
ans=ans*n+a[i];
}
}
刚刚比完的AcWing第97场周赛正好考到了，可以关注我明天发的周赛题解，我发布之后也会在此补上链接（补在下面了）。
参考例题：这里
（2）十进制转其他进制
短除法：先得到的余数为低位，即使用短除法直到商为0，余数从下往上排列即为转换后的进制的数。
十进制转n进制（n小于10，n小于10，n大于10时需传入字符串思路大同小异，注意特殊处理字母A~Z即可）
//利用栈
void tenton(int nums,int n){ //nums为需要转换的数，n为需要转换的进制数
stack<int> s;
while(nums){
s.push(nums%n);
nums/=n;
}
while(!s.empty()){
cout<<s.top();
s.pop();
}
}
//用数组存储，然后反转数组
int a[N];
void tenton(int nums,int n){ //nums为需要转换的数，n为需要转换的进制数
int cnt=0; //记录数组中元素个数
while(nums){
a[cnt++]=nums%n;
nums/=n;
}
reverse(a,a+cnt);
for(int i=0;i<cnt;i++) cout<<a[i];
}
4、保留小数
头文件#include <iomanip>，利用fixed和setprecision()来实现四舍五入保留任意位数小数。
代码模板
//例：对a保留两位小数
cout<<fixed<<setprecision(2)<<a;
5、最大公约数
欧几里得算法：a与b的最大公约数等于b与a%b的最大公约数。
代码模版
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
参考例题：这里
6、最小公倍数
a与b的最大公约数与最小公倍数的乘积=a * b，所以最小公倍数=a*b/gcd(a,b)
7、快速幂
代码模板
typedef long long LL; //需要快速幂的值一般较大，所以开long long
//返回a^b%p的结果
int qmi(int a,int b,int p){
LL res=1%p;
while(b){
if(b&1) res=res*a%p;
b>>=1;
a=(LL)a*a%p;
}
return res;
}
参考例题：这里
三、常用STL
1、string
#include <string> //头文件
size() //返回大小
empty() //判断是否为空
clear() //清空
substr(起始下标，子串长度) //返回指定长度子串
find() //查找字符第一次出现的位置，如果没有出现过则返回string::npos
//非成员函数
stoi() //将字符串转化成int类型，传入string类型字符串
atoi() //将字符串转化为int类型，传入char类型字符串
2、vector
#include <vector> //头文件
size() //返回元素个数
empty() //判空
clear() //清空
push_back() //在尾部添加一个元素
pop_back() //删除最后一个元素
begin()/end() //首迭代、尾迭代
front()/back() //返回第一个/最后一个元素
3、queue/priority_queue
注：还有deque，由于本人不怎么使用没有总结，感兴趣的朋友有时间了解一下。
#include <queue> //头文件
//queue
size() //返回队列中元素的个数
empty() //判空
push() //在末尾加入一个元素
pop() //删除第一个元素
front()/back() //返回第一个/最后一个元素
//priority_queue
size() //返回优先队列中元素的个数
empty() //判空
push() //加入一个元素
pop() //删除堆顶元素
top() //返回堆顶元素
默认定义为大根堆
//定义成小根堆方法：
priority_queue<int,vector<int>,greater<int>> q;
4、stack
#include <stack> //头文件
size() //返回栈元素个数
empty() //判空
push() //入栈
pop() //出栈
top() //返回栈顶元素
5、set/multiset
#include <set> //头文件
set去重,multiset不去重，均默认升序排序
底层红黑树
size() //返回集合中元素个数
empty() //判空
clear() //清空所有元素
insert() //在集合中插入元素
find() //查找一个数，如果找到则返回该数第一次出现位置的迭代器，否则返回尾迭代
count() //返回某个值元素的个数
6、map/multimap
#include <map> //头文件
map去重，multimap不去重，均默认以key值(第一属性)升序排序
底层红黑树
size() //返回map中元素个数
empty() //判空
insert() //插入元素
find() //同上
count() //同上
7、unordered_set/unordered_map
#include <unordered_set> //头文件
#include <unordered_map>
底层哈希
操作与set、map基本一致，参考上面即可
8、pair<int,int>
#include <utility> //头文件
first //第一个元素
second //第二个元素
//适用sort对其排序时默认以第一个元素升序排序
9、algorithm
#include <algorithm> //头文件
sort() //传入首、尾地址（或首、尾迭代）排序，默认升序
//若要降序排序或对结构体按其属性排序，需手写cmp函数
bool cmp(int a,int b){
return a>b;
}
sort(a,a+n,cmp);
//对结构体指定属性排序，例：
struct Student{
string name;
double score;
}stu[N];
bool cmp(Student A,Student B){
return A.score>B.score;
}
//按成绩降序排序
sort(stu,stu+n,cmp);
max() //取最大值
min() //取最小值
swap() //交换两个元素的值
reverse() //传参和sort一致，反转区间内的元素顺序
unqiue() //传参和和sort一致，去重相邻的相同元素，若原序列无序首先需排序，返回去重后原序列尾迭代
