C++ 竞赛编程入门指南

本文由 Aaron Xie 撰写，最初发表于Educative。

对很多人来说，竞技编程不仅仅是敲代码那么简单。它是一项运动。它是一项需要多年时间才能精通并完全熟练的严谨活动。事实上，竞技编程不仅仅是一种爱好。参加比赛有很多好处：找到工作、提高逻辑分析能力，以及拓展你的创造力。

在今天的文章中，我们将向您介绍竞技编程，并讲解您首次参赛所需的主要概念。我们还邀请了 ACM ICPC 世界决赛选手 Yash Kumar，分享他对竞技编程的想法和经验。

我们将介绍以下内容：

• 什么是竞技编程？

• 竞技编程如何进行？

• 竞技编程基础知识

• 总结和资源

什么是竞技编程？

竞技编程是一项运动，甚至可以说是一门艺术。它是一项需要创造力和分析性思维来解决棘手编程问题的活动。竞技编程包括一些活动（通常通过互联网举行），参与者被称为“运动程序员”，他们解决特定的问题或谜题。评判通常由主机完成，通常基于在规定时间内解决的问题数量。目标是编写能够解决给定逻辑或数学问题的源代码。

这些比赛自 20 世纪 70 年代就已存在，多年来人们对其的兴趣与日俱增，包括国际比赛和全球社区。这些赛事得到了 Facebook 和 Google 等多家大型公司的认可。比赛种类繁多，包括短期赛事、长期赛事、专注于开源技术的活动等等。正如我所提到的，竞技编程是指通过在特定限制下编写计算机程序来解决明确定义的问题。那么，让我们更详细地解释一下。

• 定义明确的问题：比赛中，你会遇到一些问题。这些问题的定义明确，例如，你给出了变量约束、假设和其他限制条件。

• 计算机程序：你将编写计算机程序和源代码来解决给定的问题。需要注意的是，这些计算机程序是简单的命令行程序，而不是花哨的图形用户界面 (GUI) 或 Web 应用程序。

• 指定限制：你将需要开发一个在指定时间和内存限制内的程序。此限制将迫使你解决问题并开发创造性想法。你还将被限制使用一组允许的编程语言。

竞技程序员会参加ACM ICPC、Google CodeJam、Facebook HackerCup等众多竞赛。在这些比赛中，竞技程序员运用算法、数据结构、逻辑推理和其他技能来解决棘手的算法问题。由于参赛者需要在有限的时间内开发程序，因此难度极高。Java和C++是竞技编程中最常用的编程语言，因为它们的运行时效率比 Python 或 JavaScript 等其他语言更高。

竞技编程的好处

当我们问到 ACM ICPC 全球决赛选手、Educative 课程“ C++ 竞赛编程”的创始人 Yash Kumar为什么开始参加比赛时，他回答道：

一开始只是个爱好。挑战不断，有新的主题要学，参加比赛也总能让我获得一段有趣的学习经历。一开始我并不是为了通过软件开发者的面试，但它确实帮了我大忙。很快，我就开始在线上和线下比赛中展示我的技能。当然，当时我没有收入，所以奖品只是额外的奖励。

竞技编程所需的技能将对您的开发者职业生涯产生深远的益处。参加竞技编程有很多好处，包括：

• 求职：参加竞技编程可以让你成为公司理想的候选人。参加像 ACM 国际大学生程序设计竞赛这样的大型比赛，你很有可能被苹果、Facebook、IBM、谷歌等公司看中。科技公司会追踪比赛和活动来寻找潜在员工。大型竞技编程活动声望极高，成功率也极高，所以如果你表现出色，就足以证明你的技术天赋和能力。正因如此，许多公司才会赞助编程比赛。

• 团队合作能力：参加这些比赛时，你通常会进行团队合作，这意味着你将学习如何在高压时刻与队友互动。这是一项非常重要的技能。作为一名软件工程师，你几乎总是会与其他人合作，这意味着公司非常看重你的沟通能力和团队合作能力。此外，大多数团队都会有一位领导者。如果你是团队的领导者，这体现了你的管理能力，使你更受青睐。公司希望了解你能否与团队成员有效且顺畅地合作。

• 面试准备：当你想找一份工程类的工作时，公司会考察你对数据结构和算法的了解。参加编程竞赛，你需要努力加深对这些概念的理解。此外，编程面试和编程竞赛的环境非常相似。它们都是高压环境，你需要参与解决问题。虽然很多人可能无法适应这种环境，但你的竞赛经验会让你更具优势。

• 让你更快、更专注：当你训练并参加编程比赛时，你会变得更加自律、更快、更高效。在这种环境下，你会在紧迫的截止日期前解决问题并编写代码。这会教会你如何专注于一项任务并高效执行。

虽然竞技编程可以帮助你找到工作，但 Yash 想明确表示，你不应该仅仅为了找工作而开始竞技编程：

这也是我在课程中强调的一点。你可以通过参加面试准备课程并练习有限的主题来获得工作。你不会为了一份体面的工作而去任何地方展示你的竞技编程天赋。这是一项运动，应该被当成一项运动来对待。你参加比赛是因为你享受投入的时间，并且能从中获得一些回报。竞技编程肯定会帮助你应对面试，但你不必为了准备面试而参加CP。

竞技编程如何进行？

先决条件

编程语言。在开始竞技编程之前，你需要掌握一门编程语言和基本数据结构。C ++因其速度快、资源占用少和内存控制能力强，是竞技编程中最常用的语言。其他流行的语言包括 C 或 Java。不过，你并不局限于这些语言，在大多数情况下，你可以自由选择。

数据结构和算法。选择好编程语言后，你需要复习数据结构和算法的基础知识。理解数据结构和算法是竞技编程的核心，因为它们是解决问题的方法。你应该理解数组、链表、队列、树、字典树、图、排序算法、递归和动态规划等概念。

应用和时间复杂度。除了了解概念之外，你还需要知道在何时何地应用它们。这意味着你需要知道针对特定问题应该使用哪种数据结构才能获得最优解。你需要理解时间和空间复杂度的概念，例如大O符号。这对于成为一名竞技程序员至关重要，因为你的排名很大程度上取决于你解决问题的速度。

练习，练习，再练习。现在，你已经确定了编程语言，并学习了数据结构和算法。现在，你应该继续练习。在参加正式比赛之前，你应该先在一些在线平台上练习。一些练习网站包括 Codechef、Codeforces、Topcoder 和 SPOJ。从基础问题开始，等你更有信心了，就可以逐渐尝试更难、更复杂的问题。如果你真的想在竞技编程中取得成功，就需要定期练习。

竞争

如果您准备参加正式比赛，请考虑以下几点：

• 国际大学生程序设计竞赛（ACM ICPC）
• TopCoder
• 国际信息学奥林匹克竞赛（I​​OI）
• 国际函数式编程会议（ICFP）。

Google 还举办了许多编程竞赛，例如 Google Code Jam、Google Hash Code 和 Google Kickstart。在开始之前，Yash 给你以下建议：

竞技编程就像一项运动，如果你不享受这个过程，它可能不适合你。开发人员是问题解决者，他们利用现有知识解决未知问题。CP 让你比非 CP 开发人员更擅长解决问题。正因如此，许多公司会超越传统的 SD 面试，转而选择 CP 来招聘更优秀的问题解决者，尤其是在早期阶段。

那么比赛是什么样的呢？你遇到的大多数编程问题和挑战本质上都是数学或逻辑的，通常涉及以下类别之一：组合数学、数论、图论、几何学、字符串分析和数据结构。解决问题的过程通常包含两个步骤。

• 首先，构建一个高效的算法。
• 第二，用合适的编程语言实现该算法。

通常情况下，主机会对你进行自动评判。所有参赛者提交的解决方案都会在评委面前根据一系列测试用例进行运行。大多数情况下，题目采用“全或无”的评分系统，这意味着解决方案要么被接受，要么被拒绝。你完成被接受的解决方案的速度越快，在线评委给你的排名就越高。

竞技编程基础知识

C++ 复习

C++ 是迄今为止最受竞技程序员欢迎的编程语言。它提供了一个名为STL（标准模板库）的库。STL 是 C++ 模板类的集合，提供通用的数据结构和函数。

紧随 C++ 之后的是其他语言，例如面向对象编程语言 Java。Java 提供了丰富的数据结构库，称为集合 (Collections)。不过，它的运行速度比 C++ 稍慢，这是一个缺点。竞赛编程中另一种流行的语言是 Python，因为它功能友好，代码比其他编程语言更短更简洁。Python 的缺点是，与 C/C++ 和 Java 相比，它的速度相当慢。

想复习 C++？看看我们的课程《学习 C++ 面向对象编程》

继续学习。

Educative 的竞技编程课程涵盖理论知识、代码示例、分步解答的样题、插图、实用的练习题以及快速上手的技巧和窍门！所有内容均可通过浏览器访问，无需额外下载。

成为一名有竞争力的程序员

复杂性分析

在深入研究数据结构和算法之前，我们有必要先介绍一下复杂度分析，这是一种描述算法在输入量增大时的性能和效率的方法。分析算法的运行时复杂度，以确定你的解决方案是否能够满足时间限制，这一点很重要。

有三种情况需要考虑：

• 最佳情况
• 平均情况
• 最坏的情况

参加比赛时，你需要专注于最坏情况分析。通常情况下，输入会迫使你的解决方案达到最坏情况下的性能。

大 O 符号是一种渐近分析，用于描述算法执行所需的时间。换句话说，它用于描述算法的效率或复杂程度。你应该阅读文章《什么是大 O 符号？》来温习一下这个概念。

数据结构

数据结构是一种以特定布局存储数据的容器。这种“布局”使得数据结构在某些操作中高效，而在其他操作中低效。

理解数据结构对于参加竞技编程至关重要，因为你需要决定使用哪种数据结构来最有效地解决给定的问题。如果你在大学里学过计算机科学课程，你很可能对数据结构很熟悉。你应该学习以下内容：

• 数组
• 堆栈
• 队列
• 链表
• 二叉树
• 二叉搜索树
• 图表
• 特里斯
• 哈希表
• 堆

想复习一下数据结构？访问我们的“顶级数据结构和算法”文章。

数论

竞技编程涉及大量数学知识，因此复习开发者常用的数学概念至关重要。让我们回顾一下比赛中涉及的一些主要主题。这些基本原理决定了你的成败！

代数：

• 自然数都是从 1 开始的正整数（例如：1、2、3、4、5、6、7……）

• 计算前 n 个整数的和

  $$n(n+1)/2$$

• 阶乘用n!表示，即n!=1*2*3……

• 素数是大于 1 的自然数，不能由多个其他整数组成

算术序列：

等差数列是一系列数字，其中每个连续数字之间的差是常数。例如，等差数列可以是 1,3,5,7……，因为公差是 2。

具有 $n$ 项的等差数列的和是

几何序列：

等比数列是指一系列数字，其下一项由前一项乘以一个共同乘数得到。例如，2、4、8、16、32。共同乘数是 2。

具有n项的几何序列的和是

算法范式

算法范式是解决问题的通用策略。算法范式有四种常见的形式：暴力破解法、分治法、贪婪算法和动态规划。今天，你将学习暴力破解法和动态规划（DP）。

蛮力算法是通过反复试验来解决问题的穷举方法。它利用纯粹的计算能力，尝试每一种可能性来找到解决方案。线性搜索就是蛮力算法的一个例子，它是一种通过迭代列表中的每个值来查找目标值的方法。

动态规划是一种算法策略，它利用原始问题的最优解取决于其子问题的最优解这一原理，将问题分解为更小的子问题。您可以在此处阅读有关动态规划的更多信息。

图算法

图是一种由节点和边组成的非线性数据结构。这些节点也可以称为顶点。下图是图的可视化图。

要学习的热门图形概念：

• 广度优先搜索（BFS）

• 深度优先搜索（DFS）

• 从源到所有顶点的最短路径（Dijkstra）

• 从每个顶点到每个其他顶点的最短路径（Floyd Warshall）

总结和资源

现在你已经了解了什么是竞技编程，以及在比赛前需要复习哪些概念。如果你想知道如何参加比赛，请访问以下网站。最后，Yash 总结一下：

结交热爱CP的人。拥有这样的团队绝对是我从未对CP感到厌倦的一大原因。比赛结束后，和朋友们深夜讨论新问题可能听起来很无聊，但拥有一个充满动力的圈子会让你保持动力。我经常看到学生花费数月时间学习CP理论，却从未参加过任何比赛（无论是线上还是线下），因为他们担心自己掌握的知识不足以参加比赛，或者害怕限时比赛的压力。编写准确快速的代码是CP的重要组成部分，而只有通过参加线下比赛才能提高这一点。

Yash 汇集了他多年的竞技编程经验和热情，打造了一门面向初学者的一站式课程。他的指南将带您了解整个流程、内幕技巧以及所有需要掌握的概念。从《C++ 竞技编程：成功的关键》开始吧！

其他资源

• 国际大学生程序设计竞赛主页
• TopCoder 竞技编程主页
• C++ 中的数据结构：在线课程