该学习路线既是新手学习算法竞赛知识的指南,也是一份复习清单。
先从C++语法学起,一步一步来。
以一句Hello,World!,开始算法竞赛之旅吧!
同时了解一下C++的源程序的大致框架是什么样子的。
计算机出现的最初目的就是计算。因此我们先学习如何完成一些简单的运算任务吧。
有的时候,我们需要在不同的条件下,选择执行不同的语句,这时候我们就需要借助分支语句。
分支语句包括下面几种:
将若干条语句重复执行多次,就需要用到循环语句。
循环语句包括下面几种:
数组用于存储大量相同类型的数据。而结构体则可以将若干变量捆绑起来。
使用函数来让程序变得模块化,降低实现成本。
递归则是新手入门的一道坎,「自己调用自己」听起来并不是那么容易理解,不过仔细深究根本,就会发现「自己调用自己」和「自己调用别人」并没有本质差别。
从现在开始,你已经会使用C++语言完成一些简单的任务了,但是这远远不够。
为了做对一些简单的题目,你需要学会通过枚举或模拟脑海中的逻辑,来实现代码。这看起来并不是很高效,但有的时候很管用。
递归是指函数定义中不断调用自己的方法;而分治则是不断将这一个问题分解为若干子问题,求解后合并的操作。
在做信息学题目时,经常会碰到的一个数据类型就是字符串,你需要学习一些用于操作字符串的STL函数。当然,模拟也是解决字符串问题的好方法。
当你获得了一组数据时,如何将他们从无序变成有序也是个很重要的问题。在你没有思路的时候,不妨考虑一下将数组排个序吧。这也是接下来的很多算法的基础。
排序的方法有点多,但理解后记住它们并不难。
NOI大纲中入门级只要求学习选择、冒泡、插入排序,共三个排序算法,但是其余的难度也并不大,且初赛中可能涉及,故一并列出。
二分查找,本质上是运用分治的思想,不断减少查找范围的大小,直至找到答案。但是需要注意,这个查找方式必须应用在有序的数据结构中。
在入门组,搜索的题目常常会在迷宫类题目中出现,一般会有地图类的数据;此外,搜索也十分常用于高效地枚举构造合法解的情况,亦可用于骗分。
深度优先搜索指利用递归函数方便地实现暴力枚举的算法,与图论中的DFS算法有一定相似之处,但并不完全相同。
将每一个状态设计为图中的一个点,可以展开地毯式搜索。
数组,链表,队列,栈,都是线性结构。巧用这些结构可以做出不少方便的事情。
动态规划(DynamicProgramming,DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
即给出一个有限制容量的背包,选择放入若干有容量和价值的物品,求解如何放置能使得价值总和最大。这是阻挡很多OIer的第一道坎,从这里开始,算法就有些难以理解。
记忆化搜索是一种通过记录已经遍历过的状态的信息,从而避免对同一状态重复遍历的搜索实现方式。有的题目也可以使用记忆化搜索来降低思维难度。
因为记忆化搜索确保了每个状态只访问一次,它也是一种常见的动态规划实现方式。
区间类动态规划是线性动态规划的扩展,它在分阶段地划分问题时,与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
就算是longlong(或int64)还不够怎么办?用高精度算法。本质上就是模拟了四则运算。
在计算机中,除了二进制,比较常用的还有八进制和十六进制。有的时候学会运用正确的进制对解题也有很大帮助。
位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据,位运算是相当快的。
基本的位运算共6种,分别为按位与、按位或、按位异或、按位取反、左移和右移。
至此,你就学习完了入门组范畴内的所有算法,但是想要掌握它们,你需要继续进行足够数量的刷题,以巩固你所学到的知识点。