1.准备蓝桥杯需要做什么，有哪些需要学习的算法？

熟悉比赛环境

比赛使用的编辑环境，c/c++ 组使用的是 dev-c++ , python 组使用 IDLE , java 组使用 Eclipse，建议平时练习多使用对应的编辑器，如果不熟悉编译环境，在比赛时可能会带来不必要的麻烦，尤其是 python 组的 IDLE 非常简陋，由俭入奢易，由奢入俭难。

喜讯：官方通知第十二届蓝桥杯 c/c++ 组增加了 CodeBlocks 20.03 编程环境，支持 C++ 98 和 C++11， 终于可以用上 c++ 的新特性了。

写竞赛风格的代码

大学的课程大都是偏向使用工程风格的代码，重视可读性，写竞赛风格的代码可能会受到批评。但在蓝桥杯中，使用工程风格只会浪费时间，还可能增加出错的概率。

变量名命名的问题，可以参考黄学长的这篇博客：http://hzwer.com/9160.html，总体来说风格比较自由。平时也可以积累一些常见算法的简洁写法，如下面的辗转相除法代码就很经典。短，在竞赛中意味着节省时间，同时更不容易出错。

int gcd(int a,int b) {
    return b==0?a:gcd(b,a%b);
}

数据结构也没必要像课上那样进行封装，遵从简单实用的原则，比如栈

int st[MAX],top = 0; // 定义
st[top++] = a;   // a入栈
b = st[--top];   // 出栈

建议尽量不用指针，用指针动态分配速度慢，而且空指针处理不好可以出现运行时崩溃。竞赛中数据范围是确定的，没必要动态分配内存。

对数据范围要敏感

同样的题面，不同的数据范围，将是2个难度完全不同的题，数据范围不只是告诉你数组开多大，还可以大致推算算法的时间复杂度，比如n<=10，应该是阶乘级别的算法，比如全排列的暴力枚举；n<=1000, 可能是$O(n^3)$ 的算法，可能是动态规划，递推等等；n<=50000，可能是$O(n \log(n))$ 的算法，比如线段树，分治之类；n<=1e9, 说不定是$O(\log(n))$ 的，如二分等等。这些推测不一定准确，但可以提示题解的一些信息。

程序的空间复杂度通常是电灯泡，不用担心，管够。但有些题目还是要关心关心的，这里给个例题：给你一个元素个数是10000的无序数列，求中位数，怎么做？如果加上内存限制连10000个元素的数组都装不下，只能开5000个元素的数组，怎么做？是不是解题方法完全不一样了。如果竞赛中内存超出限制会导致直接0分。当空间不充裕时，可以用sizeof()先看看用了多少内存，防止超出题目要求。

2147483247，这个数你熟悉吗？它是 int 可以表示的最大数，再大记得开 long long。

推荐一些算法

官方其实是有竞赛大纲的：https://upload.lanqiao.cn/file/20180207/1517983424205832.pdf

不过内容不太具体，下面给出一些个人见解：

数据结构

  • 基础数据结构：数组，栈，队列，链表，树，图，堆
  • 中等数据结构：并查集，Trie树，hash表，线段树，二叉搜索树，单调栈，单调队列

算法

  • 暴力穷举，搜索算法（dfs，bfs，回溯，迭代加深搜索，双向搜索，记忆化搜索，最优性剪枝 ，可行性剪枝 ）

  • 动态规划（背包问题，区间dp，树形dp，状压 dp， 数位dp，单调队列 / 单调栈优化，矩阵快速幂优化等等）

  • 排序（桶排序，归并排序，快速排序等等）

  • 前缀和，差分：常用的小技巧。

  • 模拟：模拟就是用计算机来模拟题目中要求的操作，主要考验代码能力。

  • 二分法，倍增法：二分法，也称折半搜索，必须会。

  • 贪心：局部最优到达全局最优，比较常用。对不会做的题可以试试用贪心骗分。

  • 分治，递归：非常重要的算法。

  • 高精度：随着python的流行，高精度算法的题目越来越少见，不过蓝桥杯py和c++组是分开的，不排除。

  • 字符串：字符串hash有必要学一下。此外很多字符串的题其实找规律，动态规划，排列组合，贪心等等，感觉kmp的题不是很多。

  • 二进制处理技巧，位运算

图论

  • 最短路（堆优化Dijkstra算法， SPFA算法，Floyd算法）
  • 最小生成树（Kruskal算法，Prim算法）
  • 二分图 判定（黑白染色） 二分图的最大匹配（匈牙利算法）
  • 有向无环图，拓扑排序，DAG 上的动态规划
  • 欧拉图和哈密顿图的性质

数学：

  • 快速幂
  • 辗转相除法，扩展欧几里得算法
  • 组合数学 ，博弈论，概率论，解析几何的基础知识
  • 数论：素数筛（欧拉筛），乘法逆元，费马小定理，素数判定，质因数分解，求欧拉函数等等

想参加省赛不需要把上面的知识全学完，毕竟蓝桥杯是比较全民向的竞赛，真正必要的算法：贪心，分治，dp，搜索，数论只要gcd，再多刷刷题，省二没问题。想要省一的话，还是有必要多学一点的，上面提到的算法最好都掌握。

一定要了解STL

这条建议只针对c/c++组，选手只要学习c语言就可以参加，不需要完成大学的c++课程，面向对象的思想在竞赛中基本没什么用处，但是，如果不会用 c++ 的 STL 的话，那就实在太可惜了。C++ STL 也就是 C++ 标准模板库，它实现了常用的数据结构和算法。STL 学习难度非常低，只要调库就行，可以节省你大量时间和精力。

比如竞赛题中经常需要对一组数据进行排序，有了 STL ，你只需要在加入algorithm头文件中，直接调用 sort(a, a+n); 即可完成对数组a从小到大的排序，非常方便。完全不需要自己写排序算法，而且时间复杂度是 $O(n \log n)$ 的，即使没学过快速排序的人，也可以进行高效的排序了。

下面的列举了常用的 STL ：

  • string 字符串
  • vector 动态数组
  • set / multiset 集合
  • map / multimap / unordered_map 关联容器
  • queue 队列
  • priority_queue 优先队列（堆）
  • algorithm 算法库，常用的有sort，偶尔用的lower_bound/upper_bound(二分), nth_element(找第n大)，next_permutation(排列组合中求下一个序列)等
  • bitset 二进制相关，偶尔用

多练习使用 SLT 的效益是非常高的，比如使用邻接表建图时

vector<int> g[MAX_NODE]; // 定义
g[a].push_back(b); 
g[b].push_back(a); // 添加一条a与b的无向边 
for (int i = 0; i < g[a].size(); i++) 
    cout << g[a][i]; // 遍历与a相连的点

是不是非常简洁，既节约时间，代码逻辑也清晰，在竞赛中经常使用。另一种竞赛中常用来表示图的数据结构是链式前项星，大家在网上找题解时应该会经常看到这种写法。

2.国赛和省赛有什么区别？

  • 蓝桥杯省赛一等奖可以获得报名国赛的资格。

  • 省赛，国赛的报名费都是300元。

  • 蓝桥杯的国赛无论报名流程，还是参赛过程，都和省赛基本一致。

我认为大家没必要太纠结省赛和国赛的不同，国赛的吸引力不算太大，有不少省一的同学没有继续参加国赛。但是，我推荐尽量参加一下，毕竟300块钱还不算太离谱。

3.国赛需要学习哪些算法？

准备国赛不如准备 ACM ，有对算法非常感兴趣的同学，一点要尝试一下 ACM 。

如果仅仅是为了蓝桥杯的国赛的话，其实没有必要学习太多新的算法，多刷题就行了。重点还是分治，搜索，动态规划，这些算法难度上限很高，甚至无上限，比方说动态规划，有的状态非常难确定，很难看出是dp题，有的状态转移需要写单调栈/队列，线段树甚至平衡树等数据结构来加速，有的从前往后行不通，从后往前就可以，我还见过一个动态规划的状态转移是另一个动态规划问题。这个阶段，应该从题目中积累经验，而不是按标签刷题了。

我没找到蓝桥杯真题的数据，题目和野生的题解网上可以搜到，但没数据就没法判断自己写的对不对，这点就要批评@蓝桥杯了。蓝桥杯官网的评测系统，题目也是不全的。刷题的OJ，我后面会推荐一些。

下面补充一下 ACM 可能用到的算法，为什么不是蓝桥杯，因为没的可讲啊。

数据结构

  • 树状数组，ST表（倍增法），分块思想（块状数组，树分块，块状链表），树链抛分。
  • 平衡树：STL的set/map封装了平衡树，但是有些情况还是需要手写平衡树，比如动态第k大的问题，STL封装太死，只能手写，常见的有 Treap，Splay，替罪羊树，AVL等 ，其中Splay比较特殊，它是唯二可以维护序列的平衡树，经典例题：文艺平衡树。吊炸天的数据结构Link-Cut-Tree也需要Splay为基础）
  • 可持久化数据结构，最重要的是可持久化线段树，特殊用法：主席树
  • 树套树, K-D Tree等等。
  • 字符串相关：字符串匹配算法kmp，AC自动机，后缀三姐妹（后缀数组的倍增法构建可以学学，hihocoder有相关资料，后缀树，后缀自动机，我也不会hahaha），回文串（马拉车，回文树）

算法

  • 搜索算法（启发式搜索A* ， IDA* ， Dancing Links）
  • 动态规划（空间优化：滚动数组，插头 DP，斜率优化，四边形不等式优化等等，经典算法：悬线法）
  • 树分治（点分治，边分治），cdp分治/整体二分，莫队算法。
  • LCA问题（欧拉序+ST表/倍增法/tarjan算法/树链抛分）

图论

  • tarjan 求强连通分量 + 缩点 + 割点 / 桥。
  • 网络流 最大流算法dinic和isap中至少会一个，费用流算法推荐 spfa费用流，网络流关键在于建模，经典题目有"网络流24题”。
  • 最小树形图，次小生成树，k短路，差分约束，Prufer序列等。

数学

  • BSGS，卢卡斯定理，中国剩余定理，莫比乌斯反演（扩展：杜教筛，min25筛）等数论知识。
  • 牛顿迭代法，自适应辛普森公式等恶心的高数。
  • 维护凸包，旋转卡壳，半平面交等恶心的几何题。
  • 康托展开，卡特兰数，容斥原理，置换群（Burnside 引理，Pólya 定理）等组合数学知识。
  • 高斯消元，线性基，线性规划（单纯型）
  • 生成函数，原根，快速傅立叶变换（fft），快速数论变换（ntt）

4.除了蓝桥杯，还有哪些算法比赛值得参加？

PAT

计算机程序设计能力考试（Programming Ability Test，简称 PAT ） 旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力， 科学的评价计算机程序设计人才， 为企业选拔人才提供参考标准。

PAT值得参加的是甲级和顶级，甲级难度应该小于蓝桥杯，需要英文阅读能力。对于考研生来说，PAT成绩可能在部分学校会给予免机试的优待。

ACM-ICPC

国际大学生程序设计竞赛（英文全称：International Collegiate Programming Contest（简称 ICPC））是由国际计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。

ACM与蓝桥杯的主要区别有

  • 难度不同，ACM 获奖难度和题目难度都高于蓝桥杯，考察范围更广。
  • 参与方式不同，ACM 是团体赛，一队3人一台电脑，讲求分工合作，蓝桥杯是个人赛。
  • 赛制不同，ACM题目可以提交多次，如果代码不通过会有罚时，可以修改后继续提交，直到通过。蓝桥杯只有一次判题的机会。ACM没有部分分，必须通过所有数据才能得分，蓝桥杯则有部分分。

ACM 是程序设计方面的顶级赛事，含金量高，需要付出的努力也更大。

CCPC

中国大学生程序设计竞赛（China Collegiate Programming Contest， CCPC），与ACM类似。

其他

可以了解一下百度之星，计蒜之道之类的网络赛，有难度，主要可以锻炼能力。

5.有哪些推荐的OJ平台？

vjudge

vjudge不是真正的OJ，它通过爬取其他 OJ 的题目，让我们可以直接在 VJ 上查找并提交各种 OJ 的题目，然后通过它在其他OJ的账号，提交代码并把结果反馈给我们。因此VJ上的题目非常全，有很多ACM选手也在使用。

VJ上有一个kuangbin 带你飞专题，适合作为专项训练使用。

luogu

洛谷的最大特点是辛勤的管理员了，同类型的codevs，tyvj，甚至bzoj都凉凉了，luogu能保持活跃离不开运营团队。目前，luogu题目很多，难度从入门到入土一应俱全，题解区由于审核的存在保持着较高的质量。题目有比较准确的难度分级，可以根据算法标签找题。

leetcode

leetcode的定位是帮助程序员准备算法面试，与竞赛类的OJ相比，题目考察的知识点比较单一，整体上题目难度偏低，适合入门或者养老使用，如果想提高的话不建议只刷这个。

其他

hdu,poj 杭电和北大的OJ，可以说是大学ACM题库中最为知名的两个。

codeforces 俄罗斯的竞赛网站，有着高质量的题目和高密度的比赛，唯一可惜的是由于时间差，大部分比赛要熬到凌晨1点。

hihocoder 有大量模板题，有些题自带教程，刷模板的好去处。

LibreOJ 一个有自由精神的开源OJ，你可以查看任意人提交的代码，下载任意题目数据。

上面5个OJ的题目都可以在vjudge上提交。

6.比赛的时候有哪些注意事项？

时间，一定要注意时间，写完一定要先提交。国赛时，我最后写的是一个填空题，写完想验算一下，当时一直注意电脑右下角的时间，准备最后一分钟提交，结果打开提交页面，居然已经结束了。后来才明白赛场提前3分钟开始的，提前3分钟结束，没想到居然还有这种情况。比赛系统不讲武德，我大意了，没有闪，以后好自为之，好好反思。

合理分配时间，题目量大，不要一直抓住一个题不放，不保证题目难度是递增的，不会的可以先跳过，至少每个题都看一遍，把能拿的分先拿了。最好抽出时间检查，会做的题却写错并不少见，这些错误往往简单复查一下就可以发现，当最后有可做的题没写完时，就需要取舍了，有时候放弃做新题去检查，反而收益更高。