XCPC_蓝桥杯_天梯赛算法类竞赛入门（完结）
XCPC/蓝桥杯/天梯赛 算法类竞赛入门（完结）
原本是一个读者的提问，由球友@炳源给出的入门学习路线和建议（二哥做了简
单的排版和少量修改），希望在算法方面更进一步的球友可以作为参考。
介绍
ICPC
(International Collegiate Programming Contest，国际大学生程序设计竞赛) 是由 ICPC 基
金会（ICPC Foundation）举办，是最具影响力的大学生算法竞赛。由于以前 ACM 赞助这
个竞赛，也有很多人习惯叫它 ACM 竞赛。
官网地址：https://icpc.global
CCPC
(China Collegiate Programming Contest，中国大学生程序设计竞赛)，原先是为了在国内
营造一个规范的大学生算法竞赛平台，与之前 ICPC 的混乱管理形成对比，但是近几年的
各种的利益牵扯，实际上也很难去评价是否真的做到了规范管理。
官网地址：https://ccpc.io
蓝桥杯
(蓝桥杯全国软件和信息技术专业人才大赛)，分为省赛和国赛，省赛中取得了一等奖可以
获得国赛参加资格，近两年题目难度逐渐从大众偏向竞赛，也就是逐渐变难。
天梯赛
(团体程序设计天梯赛)，主要由浙江大学的陈越教授负责，并且也使用其公司的评分系统
（PTA），是个人赛和团体赛的结合，分别计算分数，后文赛制部分详细说明。
赛制
ICPC/CCPC
采用 ACM 赛制，一般由三个人组成一队，使用一台机器，比赛时每道题目有多次提交机
会，实时评测，并返回结果，如果提交的结果错误，会有 20 分钟的罚时，每道题目只有
在所有的数据点正确后，才能得到该题的分数，最后根据通过的题目数量和总用时（实际
时间+罚时）来确定排名。
LeetCode 周赛以及牛客小白赛/月赛/挑战赛等也采用这种赛制。
蓝桥杯
采用 OI 赛制，个人参赛，是单人在五小时的时间内去解决题目，选手仅有一次提交机
会，比赛时无法看到评测结果，评分会在赛后公布。每道题有多个测试点，根据每道题通
过的测试点的数量获得相应的分数。
天梯赛
赛制比较复杂混乱，每只参赛队伍最多由 10 名队员组成，比赛时 10 名队员独立作答，
最后团队的分数为 10 名队员分数的总和，每道题目每名成员有多次提交机会，实时评测
并返回结果，每道题按照通过的数据点的数量获得相应的分数。在评了团队奖之后，还会
再给优秀的个人评个人奖。
题型
比赛在大体上分为三种大类型的题目：
传统题
选手需要提交源代码，评测系统会使用事先准备好一些输入数据和相应的输出数据作为测
试点，将选手提交的源代码编译后，让选手程序读入输入数据，通过将选手输出与事先准
备好的输出比较，来判断选手程序是否正确。这种评测方式被称之为 黑盒评测。
提交答案题
直接提交答案的题目。该种题目一般会给出输入文件，要求提交包含有 XXX1.out、
XXX2.out、XXX3.out…XXXn.out 的压缩包、文件夹或纯文件。
提交答案后，评测系统会比较答案文件与标准答案，根据选手答案的优劣情况和任务完成
度，给予一定的分数。
交互题
需要选手程序与测评程序交互来完成任务的题目。一类常见的情形是，选手程序向测评程
序发出询问，并得到其反馈。测评程序可能对选手的询问作出限制，或调整应答策略来尽
可能增加询问次数，这也给题目带来了更多变化。
学习路线
语言基础
算法竞赛中其实比较多使用的是 C++，这是在算法竞赛中比较通用的语言，当然一些比
赛也允许使用 Python、Java 等，但就论泛用性而言，还是 C++更为广泛使用，但无论
如何，坚实任何一门语言的基础，都方便你去学习其他的语言，也是你用这门计算机语言
来实现你的解决题目的算法的必需品。
算法基础
接着我们就需要开始学习一些较为基础的算法还有时间复杂度的计算，因为我们的题目往
往都有运行时间的要求，还有例如 枚举、模拟、递归&分治、贪心、排序、差分&前缀
和、二分等基础的一些算法，为之后的进阶内容做铺垫。
算法进阶
其实算法的海洋实在是太大了，我也只能是简单略说二三。
首先自然是搜索，就是穷举所有的可能来找到题目的解，不仅仅局限于 DFS 和 BFS，往
深入了说还有双向搜索、启发式搜索、迭代加深搜索以及各类的优化与剪枝。
接着就是动态规划了，从最基础的背包，到计数 DP，数位 DP……动态规划是一种通过把
原问题分解为相对简单的子问题的方式求解复杂问题的方法，它其实并不是某种具体的算
法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的
题目种类也更为繁杂。
再三就是字符串了，对于字符串的各种处理，还有匹配，以及各类统计，从入门的
Hash、Trie、KMP 到更高级的 AC 自动机、后缀自动机、后缀数组、回文自动机等等。
当然，数学也是必不可少的，不仅仅是数论，还有组合数学、线性代数、概率论、博弈
论、群论……数论的东西实在是太多。
数据结构也是大头，而且往往与其他的一并结合考察。数据结构是计算机中存储、组织数
据的方式。小到变量、数组，大到线段树、平衡树，都是数据结构。程序运行离不开数据
结构，不同的数据结构又各有优劣，能够处理的问题各不相同，而根据具体问题选取合适
的数据结构，可以大大提升程序的效率。不仅仅是我们课堂中学习的栈、队列、链表等基
础的数据结构、竞赛中更多考察的还有树状数组、线段树、平衡树、堆、ST 表、可持久
化数据结构等等等等。
还有图论，图论的话其实算做数据结构与数学的一个结合（？），因为图论是数学的一个
分支，但是其实现也要依靠数据结构，从基础的最短路、最小生成树到 Tarjan 求割点、
求割边，还有差分约束系统。
最后就是计算几何了，计算几何是利用计算机建立数学模型，来解决几何问题，从平面距
离、三角函数等，到凸包、扫描线、半平面交……
刷题 OJ
我这里收集了一些个人常用的 OJ（Online Judgement，在线评测平台），也就是算法训练
的常用平台。
洛谷
地址：https://www.luogu.com.cn/
LiberOJ
地址：https://loj.ac/
牛客竞赛
地址：https://ac.nowcoder.com/
BZOJ
地址：https://lydsy.com/JudgeOnline/
Codeforces
地址：http://codeforces.com/
Atoder
地址：https://atcoder.jp/
LeetCode
地址：https://leetcode-cn.com/
个人感想
其实近几年算法竞赛是越来越卷，而且，不得不承认，算法竞赛是需要天赋的，获奖了自
然是不错的一个体验，但是其实更重要的是对自己思维以及能力的锻炼。
随着时间的推移，各类算法竞赛的含金量也在降低，以及目前就业形势，还有一些竞赛的
管理环境非常混乱，与其一心想着获奖而把自己的一些学习计划扰乱了，倒不如踏踏实实
做事，提升自己的能力，我也相信，能力的提升，总会是对自己有用的东西。
