文章目录
- 写在前面
- 一、年份日期问题
- 1、闰年判定
- 2、月份天数
- 二、简单算法
- 1、前缀和
- 2、差分
- 3、二分
- 4、并查集
- 二、简单数论
- 1、质数判定
- 2、筛质数
- 3、进制转换
- （1）其他进制转十进制
- （2）十进制转其他进制
- 4、保留小数
- 5、最大公约数
- 6、最小公倍数
- 7、快速幂
- 三、常用STL
- 1、string
- 2、vector
- 3、queue/priority_queue
- 4、stack
- 5、set/multiset
- 6、map/multimap
- 7、unordered_set/unordered_map
- 8、pair
- 9、algorithm
- 四、简单图论
- 1、单源最短路径
- 2、多源最短路
- 3、最小生成树
- 五、动态规划
- 1、0-1背包
- 2、完全背包
- 3、多重背包
- 4、线性DP
- 总结
写在前面
- 本文章面向第十四届蓝桥杯考生，在最后考前几天，方便自己总结与回顾，同时将其分享给大家，希望我们都能取得心仪的成绩。
- 本文章主要给出代码模版，对算法具体流程不会具体讲解，所以不太适合零基础的同学，适用于有一定算法基础，在考前想要进行复习与总结的同学。
- 文章大部分代码模版参考于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 int mid=l+r>1; if(check(mid)) r=mid; else l=mid+1; } //模版2 int l=0,r=n; //二分区间[l,r] while(l 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 //查找祖宗结点 if(p[x]!=x) p[x]=find(p[x]); return p[x]; } p[find(a)]=find(b); //合并a,b集合 if(n if(n%i==0) return false; } return true; } st[0]=st[1]=true; for(int i=2;i if(!st[i]){ primes[cnt++]=i; for(int j=i+i;j st[j]=true; } } } } //n表示传入的是多少进制数，s为n进制数 int ans=0; for(int i=0;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 ans=ans*n+a[i]; } } //nums为需要转换的数，n为需要转换的进制数 stack s.push(nums%n); nums/=n; } while(!s.empty()){ cout //nums为需要转换的数，n为需要转换的进制数 int cnt=0; //记录数组中元素个数 while(nums){ a[cnt++]=nums%n; nums/=n; } reverse(a,a+cnt); for(int i=0;i return b?gcd(b,a%b):a; } LL res=1%p; while(b){ if(b&1) res=res*a%p; b=1; a=(LL)a*a%p; } return res; } return ab; } sort(a,a+n,cmp); //对结构体指定属性排序，例： struct Student{ string name; double score; }stu[N]; bool cmp(Student A,Student B){ return A.scoreB.score; } //按成绩降序排序 sort(stu,stu+n,cmp); max() //取最大值 min() //取最小值 swap() //交换两个元素的值 reverse() //传参和sort一致，反转区间内的元素顺序 unqiue() //传参和和sort一致，去重相邻的相同元素，若原序列无序首先需排序，返回去重后原序列尾迭代 memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i //迭代n次 int t=-1; for(int j=1;j //寻找距离最小的点 if(!st[j]&&(t==-1||dist[t]dist[j])) t=j; } st[t]=true; //标记为已确定 for(int j=1;j e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int spfa(){ memset(dist,0x3f,sizeof dist); queue int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(dist[j]dist[t]+w[i]){ dist[j]=dist[t]+w[i]; if(!st[j]){ st[j]=true; q.push(j); } } } } if(dist[n]==0x3f3f3f3f) return -3; else return dist[n]; } for(int j=1;j if(i==j) d[i][j]=0; else d[i][j]=0x3f3f3f3f; } } void floyd(){ for(int k=1;k for(int i=1;i for(int j=1;j d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } } } //注意，若图中存在负权边，所以1号点无法到n号点，d[1][n]也可能被更新也可能则d[i][j]若大于0x3f3f3f3f/2即可认为最短路不存在 memset(dist,0x3f,sizeof dist); int res=0; //存储最小生成树边权重之和 for(int i=0;i int t=-1; for(int j=1;j //寻找距离当前生成树最小的点 if(!st[j]&&(t==-1||dist[t]dist[j])) t=j; } if(i&&dist[t]==0x3f3f3f3f3) return 0x3f3f3f3f; //如果距离最小的点的距离仍然是正无穷说明无最小生成树 if(i) res+=dist[t]; for(int j=1;j //并查集find操作 if(p[x]!=x) p[x]=find(p[x]); return p[x]; } struct Edge{ //存储每条边 int a,b,w; }edges[M]; bool cmp(Edge A,Edge B){ //手写cmp，使sort能为结构体排序 return A.w for(int i=1;i int a=edges[i].a,b=edges[i].b,w=edges[i].w; if(find(a)!=find(b)){ //最小边权的起点和终点a,b不在一个连通块则合并他们 p[find(b)]=find(a); res+=w; cnt++; } } if(cnt //枚举每个物品 for(int j=m;j=v[i];j--){ //逆序枚举背包体积 dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } //枚举每个物品 for(int j=v[i];j //正序枚举背包体积 dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } //枚举每个物品 for(int j=m;j=v[i];j--){ //逆序枚举背包体积 for(int k=0;k dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]); } } }
- 参考例题：这里
- 参考例题：这里
- 参考例题：这里
- 口诀：一三五七八十腊，三十一天永不差。闰年2月29天，平年2月28天。
- 闰年：年份能够被4整除但不能被100整除或者能被400整除的为闰年。
