蓝桥杯备赛经验分享（三）

选手介绍

19计1班 王帅

• 第十一届蓝桥杯C/C++组 国赛优秀奖
• 第十二届蓝桥杯C/C++组 国赛二等奖

经验分享

关于蓝桥杯的经验总结

1.复习方面

算法实践重于理论，书方面建议算法笔记，边看就可以刷刷蓝桥杯题库，或者其他的一些oj题库(比如洛谷, pat，acwing等，而leetcode和蓝桥杯的代码考察方向不同，leetcode重于公司应聘，所以解答风格也和竞赛不一样，要注意)
而很多算法在看书的过程中可能不理解，像我以前学习排序算法，大概有十种，像快排，归并，第一次看根本无法理解，只能一遍遍的默写(基本每天都把十种算法自己实现一遍)，原本不会的算法渐渐理解，原本以为理解的算法渐渐有了新的理解，觉得似乎自己写的还有不完美的地方，可以写的更短，或者有不同的实现方式，差不多每个算法写了7遍后，自己都能理解算法的内核思想，当自己的能力不足以理解某个算法时都可以用这种方法，现在网上也有很多算法可视化的视频或者图片，也很推荐
另外的话有只会c语言的同学也建议学一下c++的stl(standard template library)，竞赛用很方便,很多算法里面都有，只是竞赛用不着你有看完c++ primer整本书的水平，要学好基本的string(比c语言的char*好用多了), map, set等就行了，vector竞赛不常用(定义一个全局的int[]更快)
还有java,python组的比较好拿奖，但算法上c++更常用(很多比赛都只能用c++写，其他的容易超时，爆内存)，自己根据条件选择
蓝桥杯最近考察的风格也在变，像上次国赛第一题考的100Mbps(Megabits per second )换算成12.5MB(Megabytes)，这方面没法预测，一般考的也只是平时的积累，不必特意准备

2.代码风格

很多人可能了解过工程方面的代码(像google的c++代码规范)，但在竞赛里规整的命名只会浪费时间(当然是怎么快怎么来了)，竞赛选手的代码往往只有自己看的懂
求公约数的竞赛写法

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

3.比赛环境

比赛方面c++组用的IDE是dev-c++(好像也可以用codeblocks了)，比赛前要知道怎么在dev中打开代码提示及c++11标准（提供了很多方便的新标准），怎么debug等

4.考前准备

建议在考试机上可以默写下来之前准备的算法模版
包括常用头文件(可用万能头)，宏，一些常用变量例如N（大部分题目都会用到）

#include <bits/stdc++.h>

typedef long long LL;

using namespace std;

const int N = 110;

算法模版简单的像求公约数，二分，复杂的像去年省赛第五题出了题dijkstra算法，有了模版直接带上去那题甚至不需要太多变换

5.考试中
对数据范围要敏感，往往可以从不同的数据范围中猜出题目考察的算法，像logn复杂度的题目一看就应该想到二分
蓝桥杯是按点给分，不像ACM之类的比赛要全对才能得分，也就是说有的题目是可以暴力破解的(不会的题目可以得部分分)
2147,483,247这个数(差不多2e9)你熟不熟悉，int类型的最大值，超过就要用long long(最大9,223,372,036,854,775,807)
蓝桥杯的题目往往也会给出很大数据，要注意方法
比如http://lx.lanqiao.cn/problem.page?gpid=T2687

斐波那契串由下列规则生成：
　　F[0] = “0”;
　　F[1] = “1”;
　　F[n] = F[n-1] + F[n-2] （n≥2，+表示连接）
　　给出一个由0和1构成的串S和一个数n，求出F[n]中S出现的次数。

嗯，看起来很简单是一个 斐波那契类型的题目
但是

n≤2^63-1，子串长≤10000，答案≤2^63-1。
当n=2^63-1时，F[n]有多少位？
f0 1位
f1 1位
f2 2位
f3 3位
…
f10 89
…
f100 573147844013817084101
…
f1000 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

可以看到当n=1000时，原字符串就长到爆内存了，花的时间也不敢想象，那当n=2^63-1呢？
很明显，我们应该想办法优化，
我先说个大概的思路，可以对fn当大于等于n-1时，取前n-1位和后n-1位,
以下记
f[n-1]:前n-1位A0，后n-1位B0，子串出现次数C0
f[n]:前n-1位A1，后n-1位B1，子串出现次数C1
f[n+1]:前n-1位A2，后n-1位B2，子串出现次数C2
A2 = A0
B2 = B1
C2 = C0 + C1 + B0和A1拼接后子串出现次数
并且要用long long存储出现次数
原本简单的题目在数据量很大的情况下竟变得如此复杂
最后写完题目，答案记得要填上去，别等最后几分钟填，遇到不会的题可以先放一放，不同题目用的算法不一样，有的算法可能你比较熟悉

总结：

关于蓝桥杯，其实只要刷好题，把书上的算法明白了，动规，二分，bfs，dfs之类可以专门一个个研究明白，有时候刷一道题可能就要半天
一定要有耐心，刷完要复盘，这样才能越来越熟练，很多人昨天刚做完，过一个星期就不会了，包括我以前也这样，坚持下来进国赛很容易
当然兼听则明，偏信则暗，也建议多去知乎，掘金和一些国外的平台去了解别的一些大牛的文章