algorithm introduction

本蒟蒻的一些竞赛准备分享，持续更新ing

1.蓝桥杯

赛制简要介绍

首先给大家介绍一下编程比赛的三大赛制

1.ACM赛制

ACM赛制：每道题提交之后都有反馈，可以看到“通过”、“运行错误”、“答案错误”等等结果，但看不到错误的测试样例（leetcode周赛可以看到），每道题都有多个测试点，每道题必须通过了所有的测试点才算通过。每道题不限制提交次数，但没通过的话会有罚时，仅以最后一次提交为准。比赛过程中一般可以看到实时排名，通过题数相同的情况下按照答题时间+罚时来排名。

ACM赛制的比赛：ICPC、CCPC、codeforces比赛、leetcode周赛及全国编程大赛、牛客小白赛练习赛挑战赛、传智杯。

2.OI赛制

OI赛制：每道题提交之后都没有任何反馈，每道题都有多个测试点，根据每道题通过的测试点的数量获得相应的分数。每道题不限制提交次数，如果提交错误没有任何惩罚，仅以最后一次提交为准。比赛过程中看不到实时排名，赛后按照总得分来排名。

OI赛制的比赛：NOI全国青少年信息学奥林匹克竞赛、CCF CSP、考研机试、蓝桥杯、牛客OI赛、全国高校计算机能力挑战赛。

3.IOI赛制

IOI赛制：每道题提交之后都有反馈，可以看到“通过”、“运行错误”、“答案错误”等等结果，甚至可以实时看到自己每道题得了多少分，但看不到错误的测试样例。每道题都有多个测试点，根据每道题通过的测试点的数量获得相应的分数。每道题不限制提交次数，如果提交错误没有任何惩罚，仅以最后一次提交为准。比赛过程中一般可以看到实时排名（如果是考试，一般看不到排名），按照总得分来排名。可以说，IOI赛制是结合了OI赛制和ACM赛制的特点。

IOI赛制的比赛：PAT、团体程序设计天梯赛、CCF CCSP、洛谷月赛。

而蓝桥杯是属于OI赛制，所以蓝桥杯很伤感的就是每次交上去的题目得不到反馈，所以构造样例的能力就显得非常重要了，否则就会在耗费大量时间后却得不偿失。

蓝桥杯C++组比赛概况

蓝桥杯比赛共有10道题，前两题为填空题（每届数量不同，我们那届因为是线上考试，所以填空较少），填空题只需要填最后答案，程序设计要求提交完整程序，比赛过程中提交不判断对错，比赛结束后才判题，所以以最后一次提交为准。

比赛时间为4个小时，还是比较充足的，以我的经历来看全写暴力（可以省略思考过程）大概10题全写完只需要2.5h左右，所以不用太担心时间。（所以保证写对很重要！！！）

蓝桥杯比赛允许使用很多电脑自带的软件，例如计算器、EXCEL等等（EXCEL在微软公司的打造下其实功能非常强大，记得之前有一道日期类的题目，用EXCEL的内置函数可以秒解）。蓝桥杯官方支持的IDE是DEVC++，当然如果要使用CLion、VSCode也是可以的（反正比赛会录屏）。比赛理论上不允许使用模板，所有代码需要现场编写。

赛题难度概况

正常蓝桥杯比赛的题目都不算特别难懂，基本很快就可以理解题意，但蓝桥杯的题目基本都不会让你用简单的线性结构写对，数据范围正常在1$e{^5}$和1$e{6}$左右，就是那种卡在O($n{^2}$)得不到满分但O(nlog(n))可以的区间，当然有的题目除外（例如正常情况下编程第一题是高精度，就不会卡时间）。

当然，在这种情况下也不代表我们不能使用暴力，在用暴力求解的情况下，每道题正常可以获得百分之30的分数，在你全部暴力写对的情况下，省二还是很稳的，如果还想在进一步，就需要依靠巧解了。

比赛是也不是会碰到很难理解的题目，蓝桥杯赛制时间就是金钱，不要钻牛角尖，要学会放弃。

比赛准备

准备的话（以C++为例），首先是学习编程语言基本语法。

• 运算，包括逻辑运算和算术运算。
• 条件表达式，if， else条件判断。
• 数组，诸如数组定义的合适长度，边界细节，下标是从0开始还是从1开始等。
• 字符串，掌握字符串的删除，拼接，字符查找等，Java，C/C++，Python都封装了很多字符串的基本操作，学会使用即可。
• 循环，学会循环的开始和终结的判断，一般使用比较多的就是 for 和 while 。
• 函数，明白函数的返回类型和参数传递

其次，学习基础算法，数据结构和数学知识，

• 排序，这个在比赛中直接使用 sort() 就可以了，还要掌握结构体排序。
• 二分查找，也叫折半查找，在编程比赛经常会遇到。
• 贪心算法，贪心算法一般就是找到最优解的方法，比较灵活。
• DFS和BFS，图形搜索算法，都是经常使用的。
• Dijkstra, 最短路径算法。
• 动态规划，简称DP，DP题目难在公式的推导，可以先学习基础的背包问题。
• 计算几何，一般涉及较少。
• 树，二叉树的前、中、后序遍历，树状数组，最小生成树（Kruskal）。
• 栈和队列，在比赛中一般使用STL 封装好的容器来实现栈和队列，另外，map，set，vector，pair 都是经常使用的。
• 简单数学，最大公约数，最小公倍数，素数的筛选，三角形公式，等差数列等

在学习的过程中一定要刷题，一方面加强知识的理解，另一方面提高自己的代码能力（速度，Debug）。

以上这部分摘自网上，我觉得其中比较重要的部分有以下几点：

1.由于赛制是C/C组，所以对于北航学子而言，会C是十分必要的（当然会下学期的数据结构也是），如果你之前了解过C的话，就会知道C的STL是多么的强大，不夸张的说，会C的STL可以将这个禁止模板的比赛变得全是模板，毕竟它自身的功能太强大了。（反正C迟早会用到，不如趁寒假就早点学了）

2.对于上面列出的各种算法，我觉得比较重要的是——
(1).高精度，
(2).二分查找（改变“暴力杯”本质的利器，重点学习二分思想），
(3).DFS和BFS（下学期数据结构会教，但正常在快期末了，蓝桥杯可能来不及，但本身很重要，一定要学），
(4).动态规划（dp)（蓝桥杯那些不会用暴力的题基本都是动态规划，而且老师不教，很重要！！！），
(5).树状数组（O(nlog(n))的数组，是要学的）。

主要学会以上列出的几个基本就差不多了，剩下的任务就是多刷题。(不建议刷LeetCode，LeetCode基本是提供给找工作的人的，和OI赛制题目差异比较大)，下方是我当时刷题的两个链接：

蓝桥杯练习系统

洛谷题单广场

还有一个还不错的引路链接：《算法和数据结构》数据结构篇

对于洛谷，我本人更建议按照题单的顺序刷，每个题单刷几道就可以了（蓝桥杯的难度感觉大概是”普及+/提高“，当然也可以去刷真题自行了解），另外刷题后一定要总结，否则等于白刷！！！

最后给大家一点参赛动力，蓝桥杯只要获得三等奖就可以申请学校的科技竞赛奖学金，三等奖是500元，去掉报名费还有盈余，赢！！！

2.冯如杯

赛制简要介绍

冯如杯是北京航空航天大学 “冯如杯”学生学术科技作品竞赛的简称，每年4-5月举办，是由学校科学技术研究院 、教务处 、学生处 、科协、团委共同主办，科协、团委承办，在学校各学院党政领导的大力支持下开展的具有导向性、示范性和群众性并独具北航特色、彰显北航气韵、践行素质教育、弘扬创新精神的大学生学术科技活动 。以“冯如杯”竞赛为标志的校园科技文化节。

比赛情况简介

“冯如杯”竞赛通过展览学生近一年来的科技成果，评选并奖励优秀作品，表彰开展学生科技活动突出的系(院)、学生个人和优秀指导教师，交流开展科技活动的经验等，进一步推动学校的课外科技活动，培养艰苦朴素、勤奋好学、全面发展、勇于创新的良好学风和校风，引导学生走理论与实践相结合、面向社会经济建设的正确道路，激发为实现四化、振兴航空航天事业而奋斗的责任感，同时为参加“挑战杯”全国大学生课外学术科技作品竞赛作准备。

比赛准备

笔者截止本稿时，参加过大一下的冯如杯创意赛道和大二下的冯如杯主赛道制作组，并拿到了冯如杯主赛道制作组一作三等奖的成绩。

在我看来，创意赛道更像是论文查找大赛和PPT制作大赛，创意赛道需要我们创作出一个好的点子比赛也就成功了一半，如果真的想不出来好点子，可以试试将多种技术进行嫁接应用（当然这样是不得已而为之），当然也可以作为纯摆烂人选择社科组orz

相比之下主赛道组就复杂多了，如果你不幸被选为了院内推荐项目（比如我），可能最终需要参加四轮答辩才能结束，还会有老师隔几周就push你一次，很恶心。对于6系而言，如果不报冯如杯实践与展示是会挂科的，属于纯赶鸭子上架了。这里我就建议每周一次组会还是很必要的，PPT也需要迭代产生，当然好的idea同样必不可少。

冯如杯创新赛道获奖相对容易，主赛道就很难了，我们整个6系那年都没有一个冯如杯主赛道一等奖，只有三个二等奖，所以含金量还是很高的。

3.数学竞赛

赛制简要介绍

对于非数学类专业而言可以参考同济的高等数学课本，基本那就是主要考试内容，考试有选填和大题，难度较大，但获奖也较为容易。

比赛准备

经历了大一淑芬的洗礼，这不是手到擒来，我们需要做的主要任务是刷题，基本网上都会有真题流出，而且获奖很容易，笔者100分的卷子只考了三十多就得到了一等奖，属于靠难度压人的卷子了，基本只要努力刷题了，二等奖还是很容易的。