语言基础

最适合竞赛的语言：\(C\)++

主要原因：

  1. 强大的标准库：\(C\)++ 提供了一个非常强大的标准模板库 \((STL)\)，其中包括高效的数据结构（如 \(vector、map、set\) 等）和算法（如排序、搜索、二分查找等）。这些工具可以帮助参赛者快速实现复杂算法，减少编写底层代码的时间。
  2. 高效的执行速度：\(C\)++ 是一种编译型语言，其执行速度接近底层语言（如 \(C\) 和汇编），因此在执行时间上比解释型语言（如 \(Python\) 和 \(JavaScript\)）有优势。对于很多竞赛题目，时间效率是关键，\(C\)++ 的高效性能使其特别适合处理大规模数据。
  3. 广泛的使用与支持：\(C\)++ 是绝大多数算法竞赛支持的主流语言，并且在竞赛社区中非常流行。大量的参考代码、学习资源和讨论也是用 \(C\)++ 实现的。

时空复杂度分析

在竞赛中，对于所有题目，都会限制程序的运行时间与空间。

因此，我们要对每道题进行时空复杂度分析。

时间复杂度:

时间复杂度衡量的是算法在输入规模 \(n\) 增加时，所需的操作次数增长的快慢。

\(C\)++ 每秒的运行速度在 \(10^8\) 左右，题目限制的时间一般在 \(1-2\) 秒。

常见的时间复杂度包括：

  • 常数时间 \(O(1)\)：操作次数与输入规模无关。例如，访问数组元素 \(arr[i]\)。
  • 对数时间 \(O(log n)\)：例如二分查找。在每次操作后将输入规模减少一半。
  • 线性时间 \(O(n)\)：例如，遍历数组中的每个元素。
  • 线性对数时间 \(O(n log n)\)：典型例子是快速排序或归并排序。
  • 平方时间 \(O(n^2)\)：常见于两层嵌套循环的算法，例如冒泡排序，或检查两个字符串的所有配对。
  • 立方时间 \(O(n^3)\)：通常是三层嵌套循环的算法，例如 \(Floyd-Warshall\) 算法求最短路径。
  • 指数时间 \(O(2^n)\)：例如递归计算斐波那契数列或穷举所有子集的算法，这些算法的效率通常较低，只能处理小规模的输入。

空间复杂度:

空间复杂度衡量的是算法运行所需的额外内存空间。

常见的空间复杂度包括：

  • 常数空间 \(O(1)\)：算法所用的内存空间与输入规模无关，例如只用少量变量来存储中间结果。
  • 线性空间 \(O(n)\)：需要额外存储与输入规模成正比的内存空间。例如，使用一个数组来存储输入数据。
  • 平方空间 \(O(n^2)\)：一些图算法或动态规划问题需要二维矩阵来存储中间状态，例如 \(Floyd-Warshall\)。
  • 对数空间 \(O(log n)\)：例如递归深度与输入规模对数成正比的算法（如二分查找）。

什么是算法

算法是对于一种或多种操作进行的时间或空间方面的优化。

例题：Luogu P3865 【模板】ST 表 && RMQ 问题

提交代码后常见的反馈结果包括：

  1. Accepted (AC)：答案正确，算法在规定时间和空间内通过所有测试用例。
  2. Wrong Answer (WA)：答案错误，代码输出与预期结果不符。
  3. Time Limit Exceeded (TLE)：超出时间限制，算法运行时间超过规定时间。
  4. Memory Limit Exceeded (MLE)：超出内存限制，算法使用的内存超过允许范围。
  5. Runtime Error (RE)：运行时错误，代码在执行时出错（如除零、数组越界）。
  6. Compilation Error (CE)：编译错误，代码无法通过编译。

学习平台

  1. \(Acwing\)。优点：有课程以及配套练习题，适合算法入门； 缺点：课程需要购买。
  2. \(B\) 站董晓算法。优点：思路清晰，图解代码，不花钱； 缺点：算法知识较为杂碎，需要有目的去搜索学习。
  3. 洛谷。 可以用来练习算法模板题。
  4. 牛客。只适合参加比赛，不适合刷题。
  5. Codeforces。刷题与比赛兼具，思维题偏多，适合用来练习思维能力。

编译器推荐: \(cp\ editor\)

\(Acwing\) 的算法基础课可以让新手快速入门算法。