【第十四届蓝桥杯考前速成】必考知识点及代码模板总结，看完至少多拿50分 |
您所在的位置：网站首页 › 希望数学考前必刷题 › 【第十四届蓝桥杯考前速成】必考知识点及代码模板总结，看完至少多拿50分 |
|
文章目录
写在前面一、年份日期问题1、闰年判定2、月份天数
二、简单算法1、前缀和2、差分3、二分4、并查集
二、简单数论1、质数判定2、筛质数3、进制转换（1）其他进制转十进制（2）十进制转其他进制
4、保留小数5、最大公约数6、最小公倍数7、快速幂
三、常用STL1、string2、vector3、queue/priority_queue4、stack5、set/multiset6、map/multimap7、unordered_set/unordered_map8、pair9、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>1; if(check(mid)) r=mid; else l=mid+1; } //模版2 int l=0,r=n; //二分区间[l,r] while(l>1; if(check(mid)) l=mid; else r=mid-1; } //算法结束l=r,l、r均为结果 参考例题：这里 4、并查集代码模板 int p[N]; //祖宗结点数组 for(int i=1;i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |