蓝桥杯赛前突击
1.大纲精读
官方只支持 Dev-cpp 5.11 (和平时用的差不多)。
C++11的使用,在Dev-cpp 工具 里面选择 编译选项 输入 -std=c++11
并选择 编译时加入以下命令。
是支持使用 unordered_map
和 auto
的,还有 __int128
。
一定要记得 return 0;
去年听说是没 return 0;
直接省四,但一些人没 return 0;
又没事,不管是不是真的都要 return 0;
毕竟是一个好习惯。
提取出考点:
计算机算法:枚举、排序、搜索、计数、贪心、动态规划、图论、数论、字符串算法等。
数据结构:数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树等。
2.考点分析
枚举,排序,搜素,贪心感觉都可以规划为(优雅的)暴力。
刷题可能刷到原题,原题可能来自于以下平台:洛谷题单,codeforces(英文题翻译成中文),牛客小白月赛,牛客周赛,atcoder ABC(翻译成中文)等。
省二+/省一-:
算法:
枚举:这个有难有简单的,近几年感觉有一个变难的趋势,但是差不多都离不开 日期和年份,多刷一点这方面的题就好了。
常用技巧:for循环, dfs, bfs, while 循环, next_permutation
偶尔也需要 eps控制精度(去年), 前缀和, 差分, 双指针等
方式优化。
排序: 一般和贪心一块考,一定要学会自定义结构体排序 cmp
。
常用技巧:sort, cmp, merage_sort(求逆序对,基本没遇上过,遇到了也可以用离散化+树状数组水过去)
。
搜索:也是有难有简单,前年有一道扫雷(官网那个扫雷不是原题)可以说非常的阴间,多写题就会了。
常用技巧:染色, dfs, bfs
,染色的技巧还是挺重要的,一定要掌握。
贪心:对于这种题其实就是多练+猜结论,这种题又一般和思维,前缀和,差分,排序,区间问题,一同出现,多练典题就行了。
常用技巧:cmp + sort, 前缀和, 差分, 双指针, 区间处理
。
数据结构:
数组,结构体,队列,栈,这些都是基础,一定要会。
链表:这个可能会考,对于一些插入次数多以及删除次数多的可能会用到,大部分情况可以用三个数组模拟链表。
字符串:主要掌握STL string
的常用函数就行了,比如 s.substr, stoll, to_string
等。
树:这个考的比较少,大多数直接用存图的方式就可以模拟一棵树,所以直接去看图。
图:这个比较重要,一般掌握邻接表存图就行了,简单的拓扑排序
要会写。
堆:就是 priority_queue
,要掌握怎么重载结构体的 <
自定义大根堆和小根堆。
讲完了暴力,现在再讲一些其他的(其实掌握前面这些加一些简单数据结构就已经能够蓝桥杯省二甚至说蓝桥杯省一的水平了,前面有不会的一定要去补)。
省一+:
想稳定省一,前面提到的知识一定都要会,还有就是更难得部分。
算法:
动态规划:一定得掌握背包问题,其他一般都是考 线性DP
,动态规划的题不太好总结,总之多刷题就会了。
二分:非常经典的算法,难在能不能看出这是一道二分。
计数:考得简单就是前缀和双指针乱水就过了,难的话可能就和动态规划联系在一起。
图论:最短路算法 dijkstra, floyd
, 最小生成树 克鲁斯卡尔 prim
, 最近公共祖先(LCA)tarjan
等算法。
数论:欧几里得算法,扩展欧几里得算法,质数筛等。
字符串:字符串哈希,字典树,01trie,KMP等常见算法。
数据结构:
并查集:必须得掌握的数据结构。
树状数组:会简单用法就行,进阶用法掌握用维护差分数组 和 差分*i 数组 区间求和区间修改。
线段树:会解决基础的在线RMQ问题就行。
平衡树:会写一种就行。