比赛环境:网盘资源分享 通过网盘分享的文件:蓝桥杯比赛环境 链接: https://pan.baidu.com/s/1eh85AW-y83ibCmEo8ByBwA?pwd=1234 提取码: 1234
1 常见问题答疑
1.1 蓝桥杯含金量高不高?
说起蓝桥杯,不得不提ACM。 ACM是国际大学生程序设计竞赛(ACM-ICPC),被誉为计算机领域的“奥运会”,是世界上,规模最大、水平最高、最具影响力的国际大学生程序设计竞赛。 ACM难度较高,当然含金量也更高, 那么蓝桥杯的含金量肯定比不过ACM,但是其具有独特的优势。 蓝桥杯难度更低,更易拿奖,同时在计算机行业具有较高认可度。 ACM适合那些智商高或者编程经验丰富(学习算法1年以上)的选手参赛。而蓝桥杯适合小白,适合期望快速获得编程领域一个认可证书而没有太多时间投入的参赛者。
1.2 获奖到底难不难?
蓝桥杯分为省赛和国赛。 省赛时: 与你竞争的是同省的人,所以获奖难度与你所在的省份有一定关系。 强省(指获奖难度较高的省份):北京、四川、山东 弱省(指获奖难度较低的省份):云南、甘肃、广西、青海、海南、贵州、宁夏、西藏 没有在上述行列的省份一律归为中省,不是太难,也不是很易。此处的判断依据是根据历年的国赛的奖杯属于哪省,还有该省的优质大学的数量。该省优质大学越多,和你同台竞争的人的水平越高,越难获奖。 省一获奖比例为占10%,省二占20%,省三占30%,加起来获奖比例为60%,不获奖比例为40%。 国赛时: 是所有省份的省一,同台竞争,此时只按照成绩排名,不分省份。获奖比例为,国一占5%,国二占20%,国三占35%,获奖比例为60%,不获奖比例为40%。
1.3 官网300报班值不值?
相信不少小伙伴报名后会被焦虑裹挟,此时遇到官网宣传各种课程,可能会犹豫要不要花钱,我的答案是不需要花钱。可能每个人的答案不同,我在此给出几点判断依据,你们可以根据自身情况判别。
①蓝桥杯B站官方 你们可以去B站官方听他们的一些直播公开课,你觉得他们的讲课水平如何,自己判断。如果觉得讲的不错,那么你么可以考虑买他们的课;如果觉得讲的不怎么地,那么请谨慎,因为你花300买的课大概率也是这种讲课风格和水平。
②尝试自我学习 其实算法没有非常全面的课程,B站有很多优质的算法视频,但是都是散着的,很多人可能不适应,因为缺乏一个明确的学习方向,那么你可以根据下面我的一些分享,学习几天,如果找到了学习方向,那么就不需要花钱报班了。
1.4 现在学还来不来得及?
蓝桥杯的报名时间为12月份,省赛时间为4月份,大部分小白在学校报完名,大概率计划着寒假开始学。 但很大一部分人寒假学不了什么东西,因为寒假假期短,期间还穿插着春节,春节前几天帮着干家务,买新衣服,春节后几天,忙着和一年不见的亲朋好友聚餐、谈笑等等。总之,一开学,一堆人才着急忙慌的开始学习算法。 实不相瞒,我本人,双非一本,大二上学期报名蓝桥杯,以此激励自己寒假学习。其实起了一定效果,我寒假试着自律:打开一道算法题--------不会写--------翻题解--------看不明白题解--------找视频--------看几遍视频看明白了--------再看题解--------看了好几遍似乎看懂了--------试着自己写--------还是不会写。 算法有着一种天生让人放弃的能力。初碰算法,一道题可能使你钻研一天也钻研不明白,这时请不要怀疑自己的智商,请不要怀疑自己是不是不适合计算机专业。寒假在家,本来不强的自制力在如此强大的对手面前,真的招架不住。 以上,总结为如果寒假真的没学,或者学了似乎觉得什么也没学明白,请不要焦虑,请不要放弃,我也是二月底开学后真正开始沉下心来钻研的,最后拿到了河北赛区C/C++B组省级一等奖。 我不是什么智商超高的人,否则也不会在双非上学,我可以,那么你们也可以。
1.5什么是ACM、OI、IOI赛制?
目前算法竞赛常用的赛制是ACM赛制、OI赛制、IOI赛制,那么这些赛制分别代表什么意思呢? 这块我参考了这篇博文,ACM、OI、IOI编程竞赛模式介绍,想了解更多信息的可以跳转查看。
2 主要算法(纯小白指南)
2.1 算法知识图谱
这里的算法比较全面,考试范围一般不超过图上的内容,但是有些考试概率很低,所以该图只作学习参考即可,不必全部学完。
2.2 必考算法
这里推荐的算法一定会考,是你备考路上最先、最该、最明智的学习选择。
2.2.1 回溯法
推荐学习视频---------------------------------代码随想录–回溯法 算法模板
void backTracking(参数){
if(终止条件){
收集结果 ;
return;
}
for(集合的元素集){
处理结点;
backTracking(结点);
回溯;
}
}
2.2.2 DFS算法
推荐学习视频-----------------------------DFS算法讲解
2.2.3 BFS算法
推荐学习视频---------------------------- BFS算法讲解
2.3 高频算法
这里的算法是大概率会考的,不敢说100%,但80%的概率。
2.3.1 图论
2.3.1.1最短路径
单源最短路径Dijistra视频求某一个顶点(源点)到各个顶点的最短距离
多源最短路径Floyed视频求任意一个顶点到各个顶点的最短距离
单源最短路径代码模板
两个本质思想是一样的,只是存储方式不同。 邻接矩阵法存储是用e[N][N]存储,邻接表法存储是用vector v[N]存储。 算法思想: ①从没有选中的点中找到最短路径,加入到选中点中 ②更新选中点的临近点到原点距离 结束条件:当以上步骤实行n次后 初始化条件:visit[i]=0;dis[i]=0x3f3f3f3f;dis[1]=0; 目标:dis[i]是原点到i点的最短路径
/*
邻接矩阵版本
*/
int n,m;//n顶点数,m边数
int visit[MAX];
int dis[MAX];
int e[MAX][MAX];//存储图
void DigkstraA(){
//1初始化visit和dis数组
memset(visit,0,sizeof(visit));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
//2核心代码
int u=0;//离1号顶点最近的顶点下标
for(int k=1;k<=n;k++){
//①寻找dis最小值
int myMin=INF;
for(int j=1;j<=n;j++){
if(visit[j]==0&&dis[j] myMin=dis[j]; u=j; } } //②更新 visit[u]=1; for(int i=1;i<=n;i++){ if(visit[i]==0&&dis[i]>dis[u]+e[u][i]){ dis[i]=dis[u]+e[u][i]; } } } } /* 邻接表版本 */ int n,m; int visit[MAX]; int dis[MAX]; struct Node{ int index; int weight; }; vector void DigkstraB(){ //1初始化 memset(visit,0,sizeof(visit)); memset(dis,0x3f,sizeof(dis)); dis[1]=0; //2核心代码 //①寻找dis最小值 int u=0; for(int k=1;k<=n;k++){ int myMin=INF; for(int j=1;j<=n;j++){ if(visit[j]==0&&dis[j] myMin=dis[j]; u=j; } } //②更新 visit[u]=1; for(int i=0;i if(visit[arr[u][i].index]==0&&dis[arr[u][i].index]>dis[u]+arr[u][i].weight){ dis[arr[u][i].index]=dis[u]+arr[u][i].weight; } } } } 多源最短路径 算法思想: 通过三重for循环,k为中转点,i为起点,j为终点不断更新矩阵 int n,m;//n代表顶点数量,m表示边数量 int e[MAX][MAX];//存储数据 void Floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ e[i][j]=min(e[i][j],e[i][k]+e[k][j]); } } } } 2.3.1.2 最小生成树 最小生成树视频 /* prim算法 ①选出dis中最短边 ②更新被选结点附近的结点的dis 终止条件:当添加的边数量==n-1 初始化条件:visit数组,判断是否已经被选; dis数组存储未被选顶点到已被选顶点的最短距离 parent数组(选) */ int n,m;//n顶点数,m边数 int visit[MAX]; int dis[MAX]; int parent[MAX]; void prim(){ //1初始化 memset(visit,0,sizeof(visit)); memset(dis,0x3f,sizeof(dis)); memset(parent,-1,sizeof(parent)); dis[1]=0; //2核心代码 int u=0; for(int i=1;i<=n-1;i++){ int myMin=INF; for(int j=1;j<=n;j++){ if(dis[j] myMin=dis[j]; u=j; } } visit[u]=1; for(int k=1;k<=n;k++){ if(visit[k]==0&&dis[k]>e[u][k]){ dis[k]=e[u][k]; } } } } 并查集教程 /* 算法思想kruskal ①把图中所有边取出,排序 ②取出top边,判断是否成环 终止条件:当添加的边数量==n-1(有答案)或者遍历完了所有边(无答案) 初始条件:fa数组 */ int n,m;//n顶点数,m边数 int sum=0;//存答案 int num=0;//存次数 struct edge{ int u,v,w; }a[MAX];//存储边 //这步不理解的,可以查看上面推荐的并查集教程 int findRoot(int t){ if(fa[t]!=t) fa[t]=findRoot(fa[t]); return fa[t]; } bool cmp(edge a,edge b){ return a.w } int Kruskal(){ //1初始化 //并查集初始化 int fa[MAX]; for(int i=1;i<=n;i++){ fa[i]=i; } //2算法核心 //①排序 sort(a+1,a+m+1,cmp); //②取边,并判断是否成环 for(int i=1;i<=m;i++){ //如果不成环 if(findRoot(a[i].u)!=findRoot(a[i].v)){ //合并祖先 fa[findRoot(a[i].u)]=findRoot(a[i].v)]; ans+=a[i].w; num++; } if(num==n-1){ cout< return 0; } } cout<<"error"<<'\n'; return 0; } 2.3.2 前缀和差分 声明一下,前缀和、差分是两个算法 一维、二维的前缀和、差分教学视频 2.3.3 二分法 二分法教程 2.4 中频算法 2.4.1 动态规划 之所以将动态规划划分到这里,是不想让你们死扣动态规划,动态规划考察的方法千变万化,很不容易掌握, 可能你学了之后,考试考到了一个别的,你还是不会,按照学习的性价比来说,动态规划的性价比没有前面的高。 动态规划有:线性DP,区间DP,背包问题,树形DP,数位DP,前三种相对于后两种来说,算是容易的,后两种比较难,考试基本不考,考到了也需要很熟练才能拿分,故在此处不展开叙述。 2.4.1.1 线性DP 数字三角形 /* dp[i][j]表示从顶部走到第i行第j列经过的数字最大和 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+aij 目标: dp[n][j]的最大值 (可以一维数组优化) */ dp[1][1]=a[1][1]; for(int i=2;i<=n;i++){ for(int j=1;j<=i;j++){ dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]; } } 最大连续子段和 /* 定义:dp[i]代表前i个元素的最大子段和的值 转移:if(dp[i-1]>0) dp[i]=dp[i-1]+a[i] else dp[i]=a[i] 初始化:dp[i]=a[i];//可以优化a[i] 目标:max(dp[i]) */ 最长公共子序列 /* 给定两个序列x和y,求x和y的最长公共子序列的长度 定义:dp[i][j]表示x[1~i],y[1~j]的最长公共子序列长度 转移:if(x[i]==y[j]) dp[i][j]=dp[i-1][j-1]+1 else if(x[i]!=y[j]) dp[i][j]=max(dp[i][j-1],dp[i-1][j]) 初始化:dp[i][0]=0,dp[0][j]=0; 目标: dp[n][m] */ for(int i=0;i<=len1;i++) dp[i][0]=0; for(int j=0;j<=len2;j++) dp[0][j]=0; for(int i=1;i<=len1;i++){ for(int j=1;j<=len2;j++){ if(s1[i-1]==s2[j-1]){ dp[i][j]=dp[i-1][j-1]+1; }else{ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } 最长上升子序列 /* 定义:dp[i]表示前i个元素中的最长上升子序列 转移:if(a[i]>a[j]) dp[i]=max(dp[j]+1,dp[i]); 初始化:dp[0]=0 目标: max(dp[i]) */ for(int i=1;i<=n;i++){ dp[i]=1; for(int j=1;j