type
status
date
slug
summary
tags
category
icon
password
本文将介绍以下三方面内容：算法竞赛基本知识、如何自学与高效刷题、时间空间复杂度分析。
算法竞赛基本知识
OJ 评测结果
状态 | 全称 | 含义 | 可能的原因 |
AC | Accepted | 程序通过 | 有问题吗？没有问题！ |
PC | Partially Correct | 部分正确 | 输出的结果中有部分是错误的。某些评测系统会有这个评测状态。 |
PE | Presentation Error | 格式错误 | 距离成功最近的一种，仅仅是输出答案的排版不正确，没有换行、插入了多余的空格等。 |
CE | Compile Error | 编译错误 | 代码没有通过编译，可能是语法问题、链接错误、找不到头文件等。 |
WA | Wrong Answer | 答案错误 | 答案与给定的不符，可能是计算错误、算法错误等输出了错误内容，或者有多余输出。 |
RE | Runtime Error | 运行时错误 | 运行过程中出现的一些导致程序异常终止的问题，如段错误、除以 0、栈溢出等，属于程序本身的问题。 |
TLE | Time Limit Exceeded | 超出时间限制 | 运行时间超出了题目规定的时间上限，可能是程序死循环或者算法复杂度过高。 |
MLE | Memory Limit Exceeded | 超出内存限制 | 使用的内存超出了题目规定的上限，可能是空间复杂度过高。 |
OLE | Output Limit Exceeded | 输出超过限制 | 答案输出过长，可能是出现了死循环，或者循环次数过多等问题。 |
UKE | Unknown Error | 未知错误 | 系统因其它原因造成的错误。 |
三大赛制
- OI 赛制：每道题提交之后都没有反馈，根据每道题通过的测试点的数量获得相应的分数。每道题不限制提交次数，如果提交错误没有任何惩罚，但仅以最后一次提交为准，赛后按照总得分来排名。
- IOI 赛制：每道题提交之后都有反馈，可以实时看到自己每道题得了多少分，但看不到错误的测试样例。每道题都有多个测试点，根据通过的测试点的数量获得相应的分数。每道题不限制提交次数，如果提交错误没有任何惩罚。比赛过程中一般可以看到实时排名，按照总得分来排名。
- ICPC 赛制：每道题提交之后都有反馈，但看不到错误的测试样例（LeetCode 周赛可以看到），每道题都有多个测试点，每道题必须通过了所有的测试点才算通过。每道题不限制提交次数，没通过的话会有罚时，比赛过程中可以看到实时排名，通过题数相同的情况下按照答题时间 + 罚时来排名。
OI 赛制和 IOI 赛制没有提交限制，提交错误也没有惩罚，所以可以大胆地提交，但 ICPC 赛制的罚时会拉开很大的差距。
比赛时间
每年时间不定，但大致相同。
上半学期：
- 8 - 12 月：CCPC、ICPC
- 12 月：蓝桥杯校赛
下半学期：
- 4 月：蓝桥省赛、CCCC-GPLT 团体程序设计天梯赛国赛
- 6 月：蓝桥杯国赛、RAICOM 睿抗省赛、四川省赛、百度之星省赛、码蹄杯省赛
- 7 月：RAICOM 睿抗国赛、码蹄杯国赛
- 8 月：百度之星国赛
以上为 B 类竞赛时间，赛氪上有一些比赛也可自行报名，加智育分（看学校）。
如何自学与高效刷题
学习语言
在算法竞赛中，C++ 是使用最为广泛的语言，它拥有以下优势：
- 有丰富的函数库。
- 可以使用 C++ 标准模板库（STL），极大地方便了操作。
- 格式化输入输出操作相对于其它语言比较方便。
- 极高的运行效率。
最重要的自然是第 4 条，更快更好始终是算法竞赛所追求的，C++ 完美地满足了这点要求。
学习算法
语言只是工具，算法才是灵魂。
在完成语言部分后，我们便可以来好好研究程序的灵魂了。
算法小科普：
对于有看书习惯的同学，推荐以下书籍：
- 《挑战程序设计竞赛 第 2 版》
作者巫泽俊，是 ACM-ICPC 世界总决赛冠军。
- 《算法竞赛入门经典 第 2 版》
竞赛选手常称为紫书。
这两本书均可作为算法竞赛的入门书籍，可以从中较为全面地学习基础算法。
- 《算法竞赛》
俗称白书，比较新的算法竞赛指南。
从这一阶段开始，学新算法 → 刷题 → 遇到不会的题 → 学新算法将会是一个常态化的过程，算法竞赛选手需要在这一过程中具有较强的定力、坚持下去的决心以不断锤炼自己的编码水平与算法水平。
在这一过程中，各大 OJ 平台将会是训练的重点。
常用网站/OJ
PTA（Pintia）
PTA 是学校很多课程所用的教学平台，同时，它的公共题目集也很适合作为入门期训练所用，也是备战天梯赛的主要平台。
在入门期，可以通过刷固定题目集-团体程序设计天梯赛-练习集 L1 部分进行基础语法的学习与巩固。
洛谷（Luogu）
洛谷是备战 NOIP/NOI 的重要平台，也是中国目前最庞大的算法竞赛备赛平台。网站内存在大量 NOIP/NOI 真题，题库丰富且大多具有题解，具有比较高的训练价值。
同时，洛谷也收录了 Codeforces、AtCoder、SPJ 等 OJ 的题目。
牛客竞赛
牛客网主要提供技术类求职备考、社群交流、企业招聘等服务。而牛客竞赛则主要针对 OI 与 ICPC 选手进行竞赛训练。牛客 OJ 中具有比较丰富的题库，也有定期举办的牛客系列比赛作为训练内容。
牛客作为线上办赛平台，可在平台上参加各大高校的程序设计校赛/新生赛作为算法初学阶段的练习。
AcWing
由闫学灿（北京大学、NOI 金牌）自建的一个课程网站，其中的算法课（算法基础课、算法提高课）需要付费购买，性价比在同行中颇高。
授课方式以题目打卡、视频回放的方式进行知识点讲解。知识点的整理分类对于初入算竞的小白来说尤为关键。
网上自然有许多免费课程，但缺少系统化整理，买课观看不失为一种有效方式。
LeetCode（力扣）
LeetCode 是国外面向面试、笔试的算法学习平台，力扣是其国内版。与传统 OJ 相比，LeetCode 写题均为核心代码模式（函数题），无需自己处理输入输出。
但是，对于准备算法竞赛来说，LeetCode 并不适合作为训练平台，其题目风格与题目难度均与真正的竞赛环境相去甚远。
而对于找工作而言，LeetCode 的题目较为适中，适合在大四春招期间作为练习平台。
Codeforces
到达一定水平后，Codeforces 的训练便必不可少。Codeforces 是全世界最强最大的算法平台，是由俄罗斯萨拉托夫国立大学的一个团体创立并负责运营的。它最大的特点就是代码和题解的公开，所有人都可以随意查看其它大牛的代码，且具有质量极高的题库。
Codeforces 会不定期开展比赛，难度分为 div1~4 四个阶段，其中 div1 最难，div4 最易，具有很高的训练价值。
Cf 介绍与使用：
AtCoder
AtCoder 是日本最大的算法竞技网站，也是全球第二大的算法竞赛平台，正式创立于 2012 年 6 月 20 日，由 AtCoder Inc. 运行并维护。与 Codeforces 相似，AtCoder 也会不定期展开相关比赛，分为 ABC、ARC、AGC 三个难度逐级递增，AtCoder 题以思维难度高而著名，大多数 ARC、AGC 难题都没用到什么高级算法，代码量也不大，但非常难以想到。
AtC 介绍与使用：
Virtual Judge
Virtual Judge 是一个不是 OJ 的 OJ。
它主要通过爬虫软件，爬取其它 OJ 的题目，让我们可以直接在 VJ 上查找并提交各种 OJ 的题目，然后将我们的题目通过它的账号（比如你在 Cf 上会看到用户名 vj1、vj2……在 HDU 上会看到张翼德、马孟起……）在真正的 OJ 上提交并把结果反馈给我们，相当于一个平台一个中介。
包括上述所说的 Codeforces、AtCoder、洛谷等平台，VJ 均可爬取并进行提交。
HydroOJ
HydroOJ 是一个新兴的在线评测系统，目前尚处于发展阶段，正在维护 BZOJ 题库、CCF 真题题库及英文翻译。
RemoteJudge（远端评测）已支持：洛谷、Codeforces、SPOJ、POJ、UOJ，并仍在不断增加对更多 OJ 平台的支持。
可以自由引用官方的公开题目（包括 RemoteJudge 题库）创建比赛、作业和训练计划。
Cpp reference
cppreference 是一个 C/C++ 在线参考手册。
在语法学习阶段，可以通过查阅该网站了解 C/C++ 语法，学会使用 C/C++ 标准库。
OI Wiki
OI Wiki 是一个免费开放且持续更新的编程竞赛（Competitive Programming）知识整合站点。大家可以在这里获取与竞赛相关的、有趣又实用的知识。
该网站具有种类齐全的算法分类与讲解，遇到不会的算法基本均可以在此网站找到。
算法复杂度分析
为何要分析
计算机执行代码并做基本运算是需要时间的，开数组和变量名是需要占用空间的。在处理一个问题时，题目会限制时间与空间。你的代码需要在限制时间内输出结果，并且在空间限制内存储数据。
通常情况下：
时间限制：C/C++ 秒，其它语言 秒
空间限制：C/C++ ，其它语言
时间复杂度
概念：衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等。一般来说，数据规模越大，算法的用时就越长。而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即时间复杂度。
计算机的运行速度大约是 次（级别）/秒，Cf 的评测机能达到 次/秒。
一般我们使用大 符号粗略表达时间复杂度：
常数阶
程序中不包含循环及递归。
线性阶
平方阶
对数阶
时退出，
线性对数阶
根号阶
复杂判断
以下算法的时间复杂度为
并列语句的执行趋势是相加的
嵌套语句的执行趋势是相乘的
如果将 改为 ，那么时间复杂度就是
复杂度排序
时间复杂度从小到大排序：
时间复杂度求的是运行的上界。解决一个问题时，我们需要考虑代码的最坏时间复杂度的情况是否超时。
在 秒之内大约能解决最大问题规模 ：
运算量 | ||||||
最大规模 | ||||||
速度扩大两倍后 |
时间复杂度越小，能处理的数据就越大。这也是算法需要做的事情。
空间复杂度
概念：完成一个算法所需要占用的存储空间。
计算方法：
注意：二维数组
int a[x][y]; 所开大小为 ，总大小不能接近题目限制的内存。- 作者:DrimTech
- 链接:https://drim.cc/ac-beginning
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
