《挑战程序设计竞赛：第2版》
ISBN 978-7-115-32010-0
因为第一章介绍的都是常识性内容，这章的笔记会有比较多的吐槽和回忆成分。
程序设计竞赛
我重点关注的是解题类的程序设计竞赛。其他类别有性能竞赛（数据挖掘和人工智能？）、创意竞赛（应用设计开发）之类。
解题竞赛可以理解成做题竞赛，写代码提交，测评机会用一堆输入检查代码的输出，对得多、做得快的排名高。题目的形式一般是题面 + 输入输出规定 + 样例 + 数据规模 + 时间和空间限制。题面往往有一半的废话用来创设情景，讲一个和小明相关的故事，另外一半是真正提问题的，暗示或明示了该题需要用到的数据结构和算法。输入输出的格式会有严格的限制，这一方面减少了读入数据的难度，另一方面也会卡一部分选手，比如最后一个输入末尾没有回车，这需要读入检查 EOF，或要求行末不能有空格、必须以样例编号 + 空格 + 答案的格式输出之类。样例是参考的输入和对应的正确输出，可能会帮助选手发现没考虑到的边界条件，也可能就是普通的数据，甚至可能故意绕过掩盖一些坑，导致过了样例但是WA的结果。数据规模可能放在题面里，也可能单独领出来。时空限制规定了本题的代码应该在某个时间内。利用不超过一定大小的内存输出全部答案。这两个限制往往决定了这题可以暴力过还是必须用特殊算法。
赛制和赛程方面，各竞赛不尽相同。OI和类ACM（现在叫ICPC？）区别比较大。
大体上，要求算得对、算得快，这需要算法的学习、刷题和一定的想象力。是非常接近高中学习模式的竞赛之一。
知名度比较高的比赛有高中搞的OI（NOIP、NOI、IOI），属于奥林匹克竞赛之一，当然和奥赛一样越来越难出（对高中升学有帮助的）成果；Google 开的 GCJ，输入数据的规模分 Small 和 Large，小难题的小数据也可能暴力过；TopCoder，特点是 challenge phase 和类 OI 的单次提交；ACM-ICPC，三人一队一机，5小时10道题，对团队配合要求高。关于GCJ的信息这本书上的比较旧了。
此外有很多使用在线评测功能的做题网站（Online Judge），比如北大的POJ，杭电的HDOJ，俄罗斯的Codeforces，日本的AOJ。还有像洛谷、LibreOJ、UOJ这样很活跃的国内OJ。各个 OJ 的使用方法参考它们的网站。
语言方面，C++。它提供了一些比较好用的通用数据结构（比如链表、队列、栈）和算法（比如排序、排列），同时保证了运行效率。Java 也可以，但是会慢。许多 OJ 对 Java 的时间空间限制都是其他语言的两倍。同样属于其他语言的 Python 因为速度往往不如 C++ 而经常被卡时间，所以入门之后就可以丢掉了。Pascal 快死了。NOIP在2019年和2022年之后都不支持 Pascal。
提交后常见的状态
| 状态 | 解释 |
|---|---|
| Compile Error | CE，编译不通过，一般会给出报错信息 |
| Memory Limit Exceeded | MLE，爆空间，使用了超过限制的内存 |
| Time Limit Exceeded | TLE，爆时间，算法正确但是太慢，或者某个地方死循环，或者输入有问题，样例输完了程序还在等输入 |
| Output Limit Exceeded | OLE，比较少见，是输出了太多东西 |
| System Error, Validator Error | 测评机坏了 |
| Presentation Error | PE，除了AC之外最喜欢看到的报错，意思是答案正确但是换行或空格不符合要求 |
| Accepted | AC，完全正确，可以做下一题了 |
| Wrong Answer | WA，最常见的结果 |
算法复杂度
分时间复杂度和空间复杂度。复杂度一般指程序消耗的资源随问题规模增长而变化的情况。比如遍历一个链表的时间复杂度和链表长度成正比，是 $O(n)$ 时间，遍历一个正方形矩阵的时间复杂度是 $O(n^2)$ 时间。 对规模较大（$1 \times 10^5$ 以上）的问题，暴力算法基本必WA。
空间复杂度一般考虑得不多，优化方法有滚动列表之类的操作。
热身题
三角形
$n$ 根给定长度的棍子, 从中选出 $3$ 根棍子组成三角形, 使周长最长. 输出周长, 无法组成则输出 $0$.
暴力 $O(n^3)$
3层循环遍历数组，用可以组成三角形的周长去更新最大值。
排序 $O(n\log n)$
由于只需要最长的周长，可以贪心。先对长度排序，选最长的三根判断。
- 三根能构成三角形，则为答案
- 三根构不成三角形，必有最短的两个长度和不大于最长长度，则直接舍去最长长度，窗口“滑动”一个单位继续判断。
排序复杂度 $O(n\log n)$，遍历复杂度 $O(n)$。
蚂蚁（POJ 1852）
$n$ 只蚂蚁以每秒 $1cm$ 的速度在长 $Lcm$ 的细杆上爬行，蚂蚁相遇时立刻调转方向爬行，爬到杆子两端时则掉落。已知各蚂蚁到杆左端的距离，但不知道各蚂蚁的初始朝向。求蚂蚁全部掉落需要的最短时间和最长时间。
暴力 $O(2^n)$
枚举蚂蚁所有朝向的组合，对每种组合进行模拟/计算。
思维 $O(n)$
蚂蚁都是相同的，相遇后各自调转方向相当于穿过彼此继续前进。则最短时间则是距杆子两端最近的距离，同理得最长时间。读入时即可解决。
抽签
有 $n$ 个写有数字的签。每次抽一个，记录数字后放回，抽 $4$ 次。求抽出的数字之和是否能等于 $m$。
暴力 $O(n^4)$
4层遍历并判断。有放回，每层从头开始。
二分 $O(n^3\log n)$
排序。3层循环遍历，在数组中搜索 $m - a[i] - a[j] - a[k]$。
二分 $O(n^2\log n)$
用 $n^2$ 时间保存各签两两求和的结果到一个新数组，排序后两层循环搜索 $m - a[i] - a[j]$。
复杂度：$n^2\log n^2 = 2n^2\log n$
就是这一系列的优化本质上是拉平每一步的复杂度，用最大的复杂度代替整体，然后靠忽略常数这一步得到更好看的结果。实际上去掉一阶换上一个大常数确实能在大规模下达到更快的速度。