算法入门笔记 #1 杂记

本文最后更新于:2023年3月18日 晚上

该笔记是去年尝试入坑 ACM 竞赛的遗留物,为作机试的准备,重新整理一遍以加深印象。以下部分内容出自刘汝佳的《算法计算入门经典》,也就是俗称的「紫书」,部分内容参考了网上流传甚广的博客。

算法竞赛技巧

  1. 数组在 main 外面定义可以开得更大:避免爆栈,在全局区申请分担压力;main 函数返回 0,是为了告诉操作系统、IDE、调试器、OJ,程序正常结束。
  2. 对复杂的表达式化简不仅可以减少计算量,还能减少中间结果溢出的可能,尤其是带除法运算的浮点数,绝对会爆 double,必须把表达式通分后除最大公约数。
  3. 使用 while(scanf("%d", &x) == 1)读入未知量数据:scanf 会成功返回读入变量的个数,如果有多个变量,则用 == 2。否则即使只成功一个,返回 1,循环还是会执行。如果发生错误输入/中止符,中止前输入的数也会被保存。

    • 此时运行代码时如果用键盘输入,则最后一个 Enter 无法中止程序,因为函数默认略过换行。

    • 在 Windows 下,输入完毕后先按 Enter 再按 Ctrl+Z 再按 Enter 可以结束输入,相当于人工输入一个 EOF,换成 while(scanf() != EOF) 也行。

    • 在 Linux 下,输入完毕后按 Ctrl+D 即可。

  4. 使用 while(cin>>x) 读入未知量数据:正常输入,直到遇到文件结束符 EOF 或人工输入 Ctrl+Z,istream 返回无效假条件;错误输入,如用字符输入整型变量,也会返回假条件,强制结束循环;如果有多个读入 >>x>>y,只要发生上面任意一种,都会中止,但在中止前输入的数会保存;
    • 证明了 >> 运算符返回值是同样的 istream。
  5. 打表法:对于输入范围在 1e3 以内,暴力复杂度较高的情况,使用一个 freopen("ans.txt","w",stdout); 即可将输出重定向到文本,再造好数组格式的输出,手动复制到代码里提交即可;
    • 一维数组:造输出时用 printf("%d,",num); 不要忘记输出逗号,复制到 int ans[]={这里};
    • 二维数组:造输出时用 printf(f[%d][%d]=%d",i,j,d[n][m]);,复制到一个 void get_ans(){这里}
    • 如果有 long long 输出,必须带上 LL,用 printf("f[%d][%d]=%lldLL",i,j,d[n][m]);
  6. O3 优化:如果代码里有 STL 的话,请一定加上这句话 #pragma GCC optimize(3),一般的 OJ 都是默认开启的,洛谷需要手动点一下。
    • 开启 O3 后编译器会自动 inline/register 加速,节省时间(代价是汇编代码变多,可能编译失败)。
    • 开启 O3 后编译器会自动 const 所有不修改的常量,加速取模等复杂运算。
    • 开启 O3 后编译器会自动将乘法变成移位运算。
  7. cin/cout 解绑:原生的 cin/cout 的速度非常慢,因为要和 scanf/printf 进行同步,所以需要加上 ios::sync_with_stdio(false); cin.tie(0);
    • 注意解绑后,不能使用 scanf/printf 了,快读也是不可以的。解绑后的 cin/cout 的速度是比 scanf 要快的,因为不用类型判断。
    • 解绑后可以 #define endl "\n",因为 endl 在使用的时候不仅仅是换行,还会清空缓冲区。速度上可能比 "\n" 换行慢了 10 倍。

调试技巧

  1. 最常用的方法:输出中间结果,提交代码时记得注释掉;
  2. 使用 exit(0); 中断程序,如果没有问题,则往下继续中断,也可以用来定位 bug;
  3. 编译时加入以下参数 -Wall -Wshadow:增强警告信息,列举所有有遮盖关系的变量(覆盖);
  4. 调试时不想反复输入数据,可用重定向输入输出,这样就会把文件作为流:
    • freopen("input.in", "r", stdin);
    • freopen("output.out", "w", stdout);
    • 如果懒得注释可以用 #define LOCAL,再在 #ifdef LOCAL#endif 两句中重定向,提交代码时删除定义语句 #define LOCAL
  5. 断言表达式 assert(判断语句):当判断语句为真时无变化,当表达式为假时中止程序,并给出错误提示。

实用代码

  1. 如果题目要求文件提交,但禁止重定向:
1
2
3
4
5
6
7
FILE *fin, *fout;	// c
fin=fopen("data.in", "rb");
fout=fopen("data.out", "wb");
while(fscanf(fin, "%d", &x) != EOF)
fprintf(fout, "%d", x);
fclose(fin);
fclose(fout);

在比赛前先了解是使用标准输入输出(即标准I/O,用键盘读写)还是文件输入输出。如果是文件输入输出,是否禁止用重定向的方式访问文件

  1. 如果允许重定向:
1
2
3
4
5
6
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
while(scanf("%d", &x) != EOF) // 这里也可以换成 cin >> x
printf("%d", x); // 这里也可以换成 cout << x
fclose(stdin);
fclose(stdout);
  1. 交换两数:a^=b^=a^=b;

  2. 三整数排序:

1
2
3
if(a>b) swap(a,b); // 执行完a≤b
if(a>c) swap(a,c); // 执行完a≤c,且a≤b依然成立
if(b>c) swap(b,c); // 执行完a≤b≤c
  1. 四舍五入:floor(x+0.5),此时等于 1 的区间为 [0.5, 1.5)

    • 注意,小数部分为 0.5 数可能受到浮点误差的影响,因为计算机中可能存了 0.49999。

    • 并且 floor 函数返回值是 double 型,要强转或赋值给 int 型。

  2. 简单求无理数:const double pi = acos(-1.0),注意三角函数使用弧度制。类似的还有 const double e = exp(1.0)
  3. 交错输出:printf("%d", q?a:b); q=!q;
  4. 更新最值:ans=max(ans,dfs(i,j));
  5. 初始化某个数组为正无穷:memset(a,0x3f,sizeof(a));,比直接用 0x7fffffff 好,不容易加法溢出。同理初始化为负无穷用 memset(a,0xcf,sizeof(a));
    • 在 LeetCode 中如果用 vector 初始化,可以用 vector<int> a(n, INT_MAX),同理还有 INT_MIN 常量,这是在 limits.h 头文件中定义的最大最小值,分别是 2147483647 和 -2147483648(-INT_MAX-1)。
  6. 求数组实际长度:sizeof(a)/sizeof(单位),前者仅仅是整个数组占内存大小,必须除以单位才能得到数组的实际长度。
    • 注意这里的 a 是数组名,但如果用指针指向数组,sizeof(指针) 得到的却是指针的长度,这是数组名和指针的一大区别。
    • 在 32 位 (x86) 系统中,指针长度为 4,在 64 位 (x64) 系统中,指针长度为 8。
  7. 两个整数相除并向上取整(x + y - 1) / y,比 ceil((double x / y)) 更快。

C vs. C++

版本比较

  • 在 C89 中不允许在 for 循环中 int i=0,但 C99 后和 C++ 都可以。
  • 在 C99 中,double 的输出必须用 %f,输入要用 %lf,但 C89 和 C++ 中都可以全用 %lf,所以尽量用 C++。
  • C99 中只规定了 int 至少是 16 位,但没规定具体值,好在比赛平台几乎都是 32 位,即上限 2147483647,这里有 10 位数,long long 最大值有 19 位数。
  • C99 用 long long 可以解决部分溢出,但是输入时要改成 %lld

    • 但是在 MinGW 的 gcc 中,要把 %lld 改成 %I64d,在 VC2008 中又得改回 %lld
    • 因此如果涉及 long long 的输入输出,常用 C++ 的输入输出流 cin/cout自定义的输入输出方法。
  • C 中的 gets(s) 存在缓冲区溢出漏洞,不推荐使用,在 C11 标准中,已经被正式删除。
    • 使用 fgets(buf, maxn, fin); 替代,或者直接用 C++ 的 cin>>s;
    • 但是 C++ 直接流读取 string 类型会在遇到空格时停止,如果想要读取一整行包含空格的字符串,可以用 getline(cin,str);
  • C++ 声明数组时,可以用 const 声明的常数数组,在 C99 中是不允许的,推荐用 C++。

新增工具

  • C++ 中特有的 bool 型变量,只有 0 或 1 两种取值,用 true 和 false 表示真和假。
  • C 中的空指针 NULL 定义为 ((void *)0),使用时可以强转赋值给任意类型指针,而 C++ 不能隐式强转,因此 NULL 被定义为 0,引入了新的关键字 nullptr 来表示空指针。
  • C 中的 qsort 需要强转万能指针 void*,并且让 cmp 函数在 a<b,a=b,a>b 时分别返回负数、零、正数。注意 cmp 是被函数指针 int (*comparator) 指向的函数。一般在算法竞赛中使用 C++ STL 中的 sort 函数。

    • sort 通常配合自定义 cmp 函数实现复杂排序 bool cmp(T &a,T &b){return a<b;},在力扣刷题时要在函数前加上 static

    • 对于比较简短的比较函数,也可以用 Lambda 表达式直接塞进 sort 里面:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      // 完全闭包,无外部变量
      sort(v.begin(), v.end(), [](auto &a, auto &b){
      return a < b;
      });
      // 捕捉闭包外的变量,&hash 表示引用捕捉指定变量,也可以只用 & 表示全部变量
      sort(v.begin(), v.end(), [&hash](auto &a, auto &b){
      if(hash[a] == hash[b]) return a > b;
      else return hash[a] < hash[b];
      });
  • C++ 中可以用 C 的类型强转:(ll)all(a),此外还新增了四种强转方法,用于类、结构体的强转。最基本的用法是 static_cast<long long>,效果和 C 的类似。

  • C++ 中除了有 Lambda 表达式,还可以封装可调用的 Lambda 仿函数(函数内嵌函数),可以避免用到全局变量、或传入冗长的参数,在 LeetCode 中较为使用,具体用法如下:

    1
    2
    3
    4
    5
    6
    7
    int main(){
    // 使用 & 表示捕获全部变量
    function<int(int, int)> dfs = [&](int x, int y) {
    return x + y;
    }; // 注意这里必须要有分号
    return dfs(1, 2);
    }

全新特性

  • C++ 中最重要的特点就是「函数传引用调用」,例如 void swap2(int&a, int&b),不必再传指针调用,更方便快捷。对于字符串、长数组可以节省大量时间,且可以直接在函数内修改原参数。

    • 不过一旦使用 & 入参就不能为常量,如 func(1)。此时只能使用 const auto& a 传参,这样速度更快,但是限制了函数内修改参数
  • C++ 中除了 struct 还有 class,工程中,一般用 struct 定义纯数据的类型,用 class 定义复杂行为的类型,二者最主要的区别是访问权限和继承方式不同。但算法竞赛中还是常用 struct 来定义结构体,因为 C++ 的结构体还可以定义成员函数构造函数等。

    • 拥有构造函数的结构体,可以通过 T *a = new T(10); 调用,得到一个指向结构体的指针,在力扣刷题用。
    • 此外也可以直接调用 T a(10);T a = T(10);T b = a;,在洛谷刷题比较常用。
    • 下面给出一个经典的类模板:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class MyClass {
    public:
    // 成员变量
    static const int N = 1e5 + 6;
    int nums[N], param;

    // 构造函数
    MyClass(int param_in) : param(param_in)) {
    memset(nums, 0, sizeof(nums));
    }

    // 成员函数
    void func1(int num) {
    // TODO
    }

    vector<int> func2() {
    // TODO
    return res_vec;
    }
    };

    /** 使用方法
    * MyClass* obj = new MyClass(param_in);
    * obj->func1(num);
    * vector<int> res_vec = obj->func2();
    */
  • C++ 中可以重载运算符,实现结构体之间的四则运算和输入输出。例如:

    • T operator +(const T &A) const{ return ...;} 在结构体内重载加法运算;
    • T operator +(const T &A, const T &B){ return ...;} 在结构体外重载加法运算;
    • ostream& operator << (ostream &out, const T& p){ out << ...; return out;} 在结构体外重载输出流;
  • C++ 中具有泛型、模板的概念,即 template<typename T>,可以实现函数端口参数的自适应,如各种类型数组的求和,甚至结构体数组的求和(需要重载加法)。

Python

在算法竞赛中,Python 有时会更有优势:高精度运算、字符串处理、记忆化搜索等,因此有必要掌握 Python 的简单技巧。Python 的基础知识可以参考 Python笔记 #1 基础语法,下面介绍算法竞赛中会用到的内容:

  • 类的模板
  • 高精度运算
  • 常用容器
  • 常用函数
  • 记忆化搜索(函数修饰符)

算法时间复杂度选择

一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。在这种情况下,C++ 代码中的操作次数控制在 $10^7 \sim 10^8$ 为最佳。

下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:

数据范围时间复杂度算法
$n \leq 30$$O(n!) \;\; O\left(2^{n}\right)$DFS+剪枝、状态压缩 DP
$n \leq 100$$O\left(n^{3}\right)$Floyd、DP、高斯消元
$n \leq 1000$$O\left(n^{2}\right) \;\; O\left(n^{2} \log n\right)$DP、二分、朴素版 Dijkstra、朴素版 Prim、Bellman-Ford
$n \leq 10^{4}$$O(n\sqrt{n})$块状链表、分块
$n \leq 10^{5}$$O(n \log n)$各种 sort、线段树、树状数组、set/map、heap、拓扑排序、Dijkstra+heap、Prim+heap、Kruskal、二分、树链剖分
$n \leq 10^{6}$$O(n)$,常数较小的 $O(n \log n)$ 算法单调队列、hash、双指针、并查集、KMP
常数比较小的 $O(n \log n)$ 做法:sort、树状数组、heap、Dijkstra
$n \leq 10^{7}$$O(n)$双指针扫描、KMP、差分、前缀和、离散化
$n \leq 10^{9}$$O(\sqrt{n})$判断质数
$n \leq 10^{18}$$O(\log n)$最大公约数、快速幂
$n \leq 10^{1000}$$O\left((\log n)^{2}\right)$高精度加减乘除
$n \leq 10^{100000}$$O(\log k \times \log \log k)$,$k$ 表示位数高精度加减、FFT/NTT

IDE 代码模板

ACM 模式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lb(x) ((x) & (-x))
#define mem(a,b) memset(a,b,sizeof(a))

typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int maxn = 2e5 + 5;

int n,m,k;
int dp[maxn][maxn], a[maxn][maxn];

int main(){
ios::sync_with_stdio(false); cin.tie(0);

return 0;
}

常见错误

取值范围有关:

  1. 根据取值范围判断类型,注意 $10^5$ 个 $10^5$ 相加有 11 位数会爆 int,要用 long long
  2. 当题目明确说「对 $1e9 + 7$ 取模」时,一定要用 long long,可以确保一次相乘后还不会溢出,但是可能溢出的地方都要尽量取模。
  3. 当题目明确说「保证 XXX 在不取余的情况下可以用 64 位有符号整数保存」时,此时不仅要开 long long,还不能先取模,因为可能需要 max 操作(不满足模不变性),必须在最后返回时才取模。
  4. 如果题目要求取余,则应当在所有运算之后都取余。避免最后减法导致负数加法导致上溢等不易察觉的错误。
  5. long long 变量赋值(+=)时,等号右边也可能溢出,最好先进行转换 1LL *
  6. nums.size() - 1 不能乱用,因为 .size() 返回 unsigned long,如果 0 - 1 答案不是 -1,而是越界。
  7. 使用 STL 中的 accumulate 时,可能会因为最后一个参数 0 而爆 int,所有 STL 算法都可能潜在溢出

边界条件有关:

  1. 使用 stack、queue 等容器时,要注意容器可能为空,直接访问元素会报 heap 溢出编译错误。
  2. 使用 $i+1$、$i-1$ 等方式访问容器 vector 的时候,要注意可能容器越界,会报 vector 编译错误。
  3. DP 初始化 DP 数组时,考虑到初始状态 dp[0],通常会将数组扩大一些,防止越界报错。
  4. DP 访问历史值时,如果会跨很长距离,也要注意可能容器越界,会报 vector 编译错误。
  5. for 循环的起始条件如果是 $x-y$ 的形式,可能会是负数,导致容器越界,应该套上 max(0, x - y)

题目的坑有关:

  1. 有的坑题故意给排好序的样例,但实际上要先自己排序
  2. 有的题目要统计满足某条件的 XX 个数,还告诉你答案可能很大,但只要题目没说,一定要特判个数为 $0$ 的情况。
  3. 记得测试 $n$ 等于 $0$ 或 $1$ 等边界情形时,答案是否需要特判

复杂度有关:

  1. 当题目出现树结构时(无论是题目给的或是自己用的),都要防止树退化成链表,卡复杂度 $O(n^2)$。
  2. 搜索题如果用到 DFS,要根据参数看是否需要记忆化,如果会重复访问同一个状态则需要。
  3. 小技巧:如果力扣周赛平台的错误用例被隐藏,大概率是卡最坏复杂度、或整数溢出,数据过多而不显示。

代码实现有关:

  1. &&|| 运算符有短路机制,可能会漏执行后面的条件,而 &| 位运算符则都会执行。
  2. >> 等位运算的优先级最低,实现二分等操作时容易出错,建议全加上括号!
  3. 表达式的运算顺序可能会关系到是否溢出,如果有大数相乘、相加,尽量先处理缩小运算符。

算法入门笔记 #1 杂记
https://hwcoder.top/Algo-Note-1
作者
Wei He
发布于
2022年8月27日
许可协议