（入门向）面向萌新的算法比赛入门指南

什么是算法

���法是指解决问题或完成特定任务的一系列明确指令或步骤集合。它是一个定义良好、逐步执行的操作序列，用于将输入转换为输出。算法可用于计算、数据处理、自动化控制、问题解决等各个领域。

算法通常由一系列简单的操作组成，这些操作可以是基本的数学运算、逻辑判断、条件分支、循环控制等。通过组合和重复执行这些操作，算法能够解决更加复杂的问题。

在计算机科学中，算法是程序设计的基础。程序员使用算法来描述和实现解决问题的步骤，从而使计算机能够按照指定的方式执行任务。不同的算法可能会根据问题的特性和要求产生不同的结果和效率。

算法的设计和分析是计算机科学的核心内容之一。好的算法应当具有正确性、可读性、高效性和可扩展性。算法的性能评估和优化是提高计算效率和解决问题的关键。

在算法比赛中，参赛者需要运用各种不同的算法来解决问题。一些常见的算法及其在比赛中的应用：

1. 贪心算法（Greedy algorithm）：贪心算法是一种每次选择当前最优解的策略。它通常适用于那些具有最优子结构性质的问题，每一步的选择都不会影响后续步骤的结果。贪心算法在某些场景下可以高效地找到近似最优解，如最小生成树、任务调度等。

2. 动态规划（Dynamic programming）：动态规划将复杂问题分解为相互重叠的子问题，并通过存储子问题的解来避免重复计算。它通常适用于具有重叠子问题和最优子结构性质的问题。动态规划在解决最短路径、背包问题、字符串匹配等方面有广泛应用。

3. 回溯法（Backtracking）：回溯法是一种通过递归地尝试所有可能的解空间来求解问题的方法。它在搜索问题、组合问题、迷宫问题等方面表现出色。回溯法通过深度优先搜索来穷举解空间，同时利用剪枝技术减少不必要的搜索。

4. 分治法（Divide and Conquer）：分治法将问题划分为独立的子问题，然后递归地解决每个子问题，并合并子问题的解来得到最终的解。它在排序算法（如快速排序、归并排序）、查找问题（如二分查找）以及一些优化问题中广泛使用。

5. 图算法：图算法用于解决与图相关的问题，如最短路径（Dijkstra算法、Floyd-Warshall算法）、最小生成树（Prim算法、Kruskal算法）、拓扑排序、图染色等。

此外，还有许多其他的经典算法和数据结构，如排序算法（冒泡排序、插入排序、堆排序）、搜索算法（深度优先搜索、广度优先搜索）、字符串匹配算法（KMP算法、Boyer-Moore算法）等，在算法比赛中都可能被使用。参赛者需要根据问题的特点选择合适的算法，并进行优化以达到更好的效果。

不同的比赛可能会有不同的限制和要求，参赛者也应该熟悉比赛规则和评测系统，针对性地选择和实现算法。

计算机系学生为什么要刷算法——— by 柳婼

很多⼈（尤其是⼀些初⼊⻔开发的计算机学⽣）可能会觉得算法在开发过程中的⽤处不⼤，甚⾄很多没有认真学过算法的⽼程序员都会这样认为，然⽽并不是这样～

⾸先，刷算法可以培养清晰的逻辑思维能⼒，改变⼈的思维⽅式，使⼈对待复杂的代码问题更容易看透本质～在未来做⼯程项⽬的过程中也会慢慢发现，当年认真学过的算法也并⾮当初想得那样毫⽆⽤处，反⽽能提⾼解决问题的效率，使⾃⼰能⽤更简单的⽅法、更精简的代码解决实际问题～

其次，看过很多IT公司招聘信息的⼈就会发现，他们都会优先选择有⼀定算法基础的⼈，尤其是⼀些⼤公司在⾯试过程中，对于应届⽣，更多考察的是数据结构与算法、计算机⽹络、操作系统等这些计算机基础课程，⽽并⾮都是在考察实际应聘岗位的相关技术、⼯具、知识等～

再者，提⾼算法能⼒不是⼀蹴⽽就的，需要静下⼼来⽤⼤⽚的时间去看书、学习、刷题、找bug或者参加竞赛，也许市⾯上有很多开发类的培训班，如前端、JavaWeb、安卓之类，但鲜有算法类的培训，因为学习算法是实实在在、需要⾃⼰付出努⼒的过程，⾃⼰对题⽬的思考、学习、钻研，别⼈⽆法替代，也不可能通过培训速成。所以这也是为什么很多公司会在应聘的笔试⾯试环节考察算法能⼒的原因，也许语⾔的特性、⼯具的使⽤、开发的技巧可以短期培训，但数据结构和算法的能⼒⾜以证明应聘者在计算机知识⽅⾯的硬实⼒～⽽且很多⼤公司在考察算法时都是⽩板编程，这⽐写代码更能考验应试者的⽔平～

最后，如果从短期⻆度来说，可能刷算法能带来的⼀些看得⻅的收益会给⾃⼰更多的动⼒，⽐如：PAT⼄级刷完可以让⾃⼰在C语⾔⼆级或者C语⾔期末考试中获得⼀个⾼分；PAT甲级能让⾃⼰在考浙⼤时候直接抵复试中机试的成绩；PAT甲级考⾼分能让⾃⼰收到⼀些⼤公司的⾯试邀请；LeetCode能够让⾃⼰在⾯试很多⼤公司尤其是国外⼀些公司（Google、微软、Facebook、Amazon等）时正确解答出笔试和⾯试的算法问题等…⽆论是⻓期还是短期来看，刷算法对于有追求的计算机学⽣都是必经之路～

什么是OJ，以及对AC、WA、TLE、CE、RE、MLE、PE等状态术语的解释

OJ（Online Judge）是指在线判题系统，将代码提交给OJ后，OJ会在线检测程序源代码的正确性，并返回结果～

国内著名的OJ系统有POJ（北京⼤学OJ）、杭电OJ（参加过ACM的⼈都知道）等，PAT的官⽅题库、蓝桥杯题库和LeetCode也是OJ系统，都可以在线提交代码并得到返回结果～

PAT考试过程中使⽤的就是和平时刷题题库⼀样的OJ判题系统，⽽蓝桥杯在考试的时候只能提交答案，不能实时看到提交的答案是否正确，但蓝桥杯平时刷题练习的题库是OJ～

相⽐⽽⾔，PAT和蓝桥需要的都是完整的有输⼊输出的代码段，⽽LeetCode并不需要输⼊输出，⽽是将需要填写的代码包在⼀个Solution类⾥，甚⾄会给好Solution类中的函数，涉及到树的题⽬还会给出树的定义，我们只需要在这个函数中填充代码并按照题⽬的要求返回相应类型的值即可～

刷算法OJ过程中提交答案后会返回的⼀些状态术语，

AC （Accepted = 答案正确），WA （WrongAnswer = 答案错误）， TLE （Time Limit Exceeded = 运⾏超时 / 时间超限）， CE （Compile Error =编译错误）， RE （Runtime Error = 运⾏时出错）， MLE （Memory Limit Exceeded = 内存超限）， PE （Presentation Error = 格式错误）

如果刷过leetcode的⼈对这些应该⽐熟悉～所以我们经常会说 AC 了几道题、 TLE 了或者 WA 了之类的～⽽PAT的OJ⾥返回的是中⽂反馈信息，例如答案正确、格式错误、内存超限、运⾏超时、段错误等～

相关链接：

算法竞赛从了解入坑到快速放弃指南

https://www.zhihu.com/tardis/zm/art/29598587?source_id=1005

算法竞赛并不是适合所有的人，需要坚持，坚持，再坚持，半途而废的人很多很多；入门不需要太深的数学能力，毕竟我们是工科生，并非理科生；入门的话，数理化没什么大碍；但是，想要一直深入走下去，走向ICPC——数学能力十分重要、数学专业的学生优势更大；走着走着，你会发现你的对手可能就是双一流大学的、信息学竞赛保送的、花式保送的、从小学开始学起计算机语言的（直接起点比你早五六年）等等。

零基础的大一新生如何学好算法

如果你是一个零基础的大一新生，想要学好算法，以下是一些建议：

1. 建立计算机基础知识：首先，确保你对计算机科学基础有一定的了解。学习计算机组成原理、数据结构和算法分析等基础概念。可以通过阅读相关教材、观看在线教育平台的视频课程或参加大学的计算机基础课程来学习。

2. 学习编程语言：选择一门常用的编程语言作为学习工具，如Python或Java。这些语言相对易于学习，拥有丰富的资源和社区支持。通过学习编程语言，你将能够理解和实现算法。

3. 掌握基本的数据结构：数据结构是算法的基础。学习各种常见的数据结构，如数组、链表、栈、队列、树和图等。理解它们的特点、操作和应用场景。可以使用教材、在线教程和练习题来巩固学习。

4. 学习基本的算法概念：了解各种基本算法的概念和原理，如排序、查找、递归、动态规划和贪心算法等。通过阅读教材、观看在线视频和参考实例代码来学习算法。

5. 刷题练习：通过刷题来提高算法能力。开始从简单的题目开始，逐渐增加难度。可以使用在线编程平台（如LeetCode、HackerRank等）提供的算法题库来进行练习。

6. 寻找合适的学习资源：在学习过程中，寻找一些优质的学习资源，如经典的算法教材、在线教程、博客和视频教程等。这些资源将为你提供更多的学习内容和实践经验。

7. 多与他人交流与合作：参加学习小组、参与在线算法社区或与同学进行讨论与交流。与他人分享知识和经验，共同解决问题，能够加深理解并拓宽思路。

8. 注重实践和项目经验：将所学的算法知识应用于实际项目中。尝试解决一些实际问题，或者参与一些开源项目。通过实际操作，加强对算法的理解和应用能力。

记住，学习算法需要时间和坚持。不要急于求成，要保持积极的学习态度，并通过不断地实践和挑战来提高自己的算法水平。

C语言入门强烈推荐浙江大学翁恺老师的课程

关于ICPC

ICPC的全程为International Collegiate Programming Contest，是世界上历史最悠久、规模最大、最负盛名的编程竞赛。因为在1977-2017期间该赛事由ACM（计算机协会）主持，所以也有人叫它ACM-ICPC。ICPC比赛主要面

向大一到研一的同学。

在中国还有一项赛事为CCPC（中国大学生程序设计竞赛）,主要面向国内高校，赛制与难度与ICPC持平，习惯上我们把ICPC与CCPC统称为XCPC。

如果要参加XCPC相关比赛，通常来讲需要先选拔进入校队，然后三人组队。每年每个人只能参加两次ICPC区域赛，根据比赛结果会角逐出进入EC final甚至World final的队伍。

XCPC相关比赛是一场关于智力与汗水的比拼，有着极高的难度上限，参赛者能享受到算法竞赛实时竞技无与伦比的乐趣。如果你也爱好解决难题，挑战自己的极限，请一定不要错过。

推荐给萌新的训练方法

刚刚入坑

学习算法竞赛其实不用太依赖于纸质资料，参考网上的资源已足够，XCPC涉及的算法可参见OI-wiki如果刚刚接触算法竞赛，请不要过分执着于学习过于复杂的算法，而是要着眼于提升分析问题，解决实际题目的基本能力。这里推荐大家参加Codeforces的p1-p4系列比赛（Codeforces游玩攻略）

但是Codeforces（以下简称为cf）的比赛多在晚上10点35分举行，如果时间安排不过来的，可以下来自己做题，也可使用virtual contest定时训练。

在这个阶段里，建议大家在做题过程中学习未掌握的算法。切记要多多阅读题解给出的标程，并学习标程的代码写法，这样大有裨益。在做题时，推荐大家要想清楚思路后再写，时刻牢记，Think twice,Code once

入门之后

当cf的rating来到1700之后，大家可以逐渐学习一些较复杂的算法，可以结合OI-wiki。其实cf的比赛题目码量和涉及到的算法复杂程度还是逊于常规ICPC区域赛的，所以大家还要多去cf的Gym中做做真题。

这里推荐一下笔者使用Virtual Judge的方法。

假如想要提升cf的rating，可以自己在Virtual Judge上拉一场比赛，主要选择在自己水平线或者之上的题目。例如，你的cf rating为1900，则可以拉3道p2D，3道p2E的题目，组成一场时长三小时的比赛，然后训练结束后再补完所有题目。训练完一场区域赛后，总会有题目没有做出来或者甚至没时间看。对于那些通过人数较少的题目，建议结合自身情况补题，希望大家有敢于与题目***磕的精神，其实一道题做一两天是很正常的当然，如果过于困难了还是要懂得放弃，君子报仇十年不晚。如果有些题目训练时没有看，但是通过的人数较多，是自己有可能独立做出的，可以记录下来，累计到3-4题后，可以用这些题目去Virtual Judge上拉一场二-三小时的比赛。

写在后

ICPC需要长期的付出与训练，并不是一个投资少见效快的“高性价比”比赛。但是这项赛事对于能力的提升是巨大的，特别是那些想要本科毕业就进入大厂就业的同学来说，ICPC的参赛经历是一块宝贵的敲门砖。但是不论你是为了毕业后更好的就业，还是说单纯喜欢学习算法与数学，你一定都能在比赛中收获良多。

计协大三学长建议：

省赛

如果你是从未接触过算法竞赛的小白,那你首先要考虑的内容是如何面对省赛,毕竟拿到省一等奖才有资格去参加国赛嘛,那你所需要准备的内容以及难度不算太难.

语法 思维（cf 800）

一.算法（序号表示优先级）

1.枚举

掌握枚举思想,就是写暴力,省赛会写暴力加一点点算法就能出线了,这里的枚举主要包括,循环遍历、DFS

Oi 蓝桥杯

Acm icpc 各种周赛

ioi 天梯赛 cccc gplt

2.排序

一般配合着枚举使用，一般来说会sort就好了，当然作为学习来说手写一下冒泡、选择、归并、快排、堆排 等都是可以的。（掌握sort、 priority_queue（堆））

Stl（c++）

3.双指针、前缀和、二分、差分、递推

常用得基本算法思想用来优化算法复杂度的入门算法（大量刷题、这是基本分）

4.最大公约数、最小公倍数、素数

掌握其中关系、素数筛（欧拉筛、埃氏筛）

5.动态规划（学到这就有机会省一了）

6.图论、字符串算法

最短路径（Dijktra、spfa、Floyd）、最小生成树（prim、Kruskal）、BFS、DFS、KMP、字典树

二.基础数据结构（无先后顺序）

其实在第一部分的内容里就会学到相关的内容了，主要配合着算法使用、作为一种思想

1.栈

单调栈

2.队列（BFS）

单调队列

3.堆（堆排序 priority_queue）

4.链表（邻接表的思想）

5.哈希表

6.并查集（Kruskal）

其实数据结构的实现在各种语言中都有封装好现成的可以使用（C++STL是必须要会用的）

具体训练：

首先是根据要学的内容去刷题,一题一题刷,这里首推洛谷题单，整理的很好,只要跟着写就好了.建议把入门也刷了,可以练一下基本功,否则要是被一些奇怪的输出输入卡了就不好了.其次可以去牛客,有条件的买课只推Acwing跟着练就完了.

在算法竞赛中，一定要记住，思维能力和直觉是核心驱动力，在思维能力达到一定层次以后，算法的学习能力也自然而然上来。

1、快速将语法过关，学习基础算法，如单调栈，动态规划，dfs，Ica, 二分，基础图论，整除，取余，尺取，贪心等，可以上洛谷官方题单板刷，然后去刷hdu入门题，也可以去acwing刷刷基础

2、打开codeforces, 千万不要没听过就害怕!只要尝试去做几道题，就会不断收益良多! ! !在problemset里选1000到1600级别题中找到适合自己难度的题，可以二分查找(check是30分钟内能否独立查出)， 最好选择contrustive(构造) 对思维提高最大，然后看看能不能30分钟独立推理出来，一定要独立思考，不要觉得怎么也想不到就觉得受挫,也不要立刻看题解!在怎么也想不到的情况下寻找一条路是锻炼直觉的关键，这种想不到却依旧得去想的经历也是直觉提高的重要铺垫! (除非你是天才)，不断去做，如果连续几次在30分钟内想出这个级别题，就去做这个级别题+100难度的题，然后坚持想30分钟，在想的过程中不断寻找可能的方向，想不出来看题解，有不知道的小技巧，小坑点都要记下来，有不懂的算法或特殊应用可以学会,用这种方法不断把上限提高

（重点）3、经常打acwing，牛客，和cf的比赛，不断验证自己的实力，而且打线上比赛很重要的是能提高竞赛能力，同时把比赛中会踩的坑都踩了，在一定的场次之后就可以只作为验证实力提高的标准了

刷题过程中如何平衡⾃⼰写代码和看他⼈代码的⼩纠结——— by 柳婼

可能很多⼈在刷算法过程中，会觉得⾃⼰写不出来的时候看了别⼈写的代码就不是⾃⼰的了，感觉像是抄了⼀遍别⼈的代码，觉得不是⾃⼰想出来的印象不够深刻，可能因为⼩时候做数学题的时候，发现⽼师讲了⼀遍的数学题⾃⼰没记住，但是⾃⼰独⽴思考然后做出来的却印象很深刻…所以觉得写代码的过程中也应该尽量保持独⽴⾃主完成～其实我觉得这样的想法是不太对的哦～

算法这个神奇的东东，有它⾃身的⼀些特点，⽐如⼀道PAT题⽬，可能你看了题⽬后觉得⾃⼰有⼀点思路了，毕竟只是给个输⼊要求你给出正确的输出嘛，或多或少还是有些⾃⼰的想法的，就开始⾃⼰写，结果没能AC，修修补补改改也勉强最后AC了，但是代码却冗⻓繁琐，过阵⼦让你再做⼀遍这道题⼜没有思路了…

算法题就是这样，总给你⼀种好像也不是太难的感觉，⽽且这种提交后会看到⾃⼰得分的真题题库总会让⼈产⽣⼀种当作⼀次正式考试测试⼀下⾃⼰的⽔平的想法，导致很多⼈刷算法完完全全就是在把⾃⼰仅有的思维和编程语法知识完全倒出来展现在代码⾥，如果这个⼈是个竞赛⾼⼿倒也没什么关系，但是如果基础不太好，直接⾃⼰写⽽排斥看他⼈代码的想法是对⾃⼰的算法提升是⾮常不利的，可能你冗⻓⽽思路不够清晰的代码确实AC了这道题，但是你可能也错过了向更优秀思路的代码学习的机会。

反⽽那些没什么思路的⼈，可能去看了别⼈优秀的代码，让⾃⼰学会遇到这类算法题的清晰思路，还学了⼀些下次能⽤得到的编程语⾔技巧（⽐如18年12⽉PAT考试结束后，⼀位可爱的⼩学弟来感谢我学了我代码中的s.substr()的⽤法，让他考试的时候直接AC了⼀道题，增强了考试时的信⼼，考试的后半段时间做题状态很好多拿了很多分）所以我建议不管这道题你写出来的代码是AC了还是做错了找不到bug，都应该看⼀看别⼈解这道题的代码是不是和你思路相同～

在我刷题的时候，如果⾃⼰的代码和别⼈思路⽅法完全不同，那我会思考，我所写的⽅法是不是⽐别⼈写的代码优秀？很多时候会发现，并不能找到错误原因的那段代码本身逻辑就为混乱，所以我的建议是直接删掉原来写的，对⾃⼰写的代码⽤更好的⽅法进⾏重构，因为即使这段代码勉强调试写出来了，下⼀次⻅到它还是难以理解，对⾃⼰的考前复习也是⼀种打击，会让⾃⼰看到这段代码就想要跳过不看，⽽且还让⾃⼰错过了⼀次学习他⼈优秀⽅法的机会，要知道刷题的真正意义是学到知识呀～

经典题目分析leetcode第一题

（有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来​​）

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6

输出：[0,1]

提示：

2 public: vector int n = nums.size(); for (int i = 0; i