【第十四届蓝桥杯考前速成】必考知识点及代码模板总结，看完至少多拿50分

文章目录

• 写在前面
• 一、年份日期问题
• • 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 //模版1int l=0,r=n;    //二分区间[l,r] while(lint mid=l+r>1;if(check(mid)) r=mid;else l=mid+1;} //模版2int l=0,r=n;    //二分区间[l,r] while(lint 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(nif(n%i==0) return false;}return true;}st[0]=st[1]=true;for(int i=2;iif(!st[i]){primes[cnt++]=i;for(int j=i+i;jst[j]=true;}}}}   //n表示传入的是多少进制数，s为n进制数 int ans=0;for(int i=0;ians=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;ireturn 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;je[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;}int spfa(){memset(dist,0x3f,sizeof dist);queueint 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;jif(i==j) d[i][j]=0;else d[i][j]=0x3f3f3f3f;}}void floyd(){for(int k=1;kfor(int i=1;ifor(int j=1;jd[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;iint 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.wfor(int i=1;iint 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;kdp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);}}}