算法入门笔记 #1 杂记

该笔记是去年尝试入坑 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. 如果题目要求文件提交，但禁止重定向：

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，用键盘读写）还是文件输入输出。如果是文件输入输出，是否禁止用重定向的方式访问文件

2. 如果允许重定向：

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);

3. 交换两数：a^=b^=a^=b;

4. 三整数排序：

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

4. 四舍五入：floor(x+0.5)，此时等于 1 的区间为 [0.5, 1.5)

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

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

5. 简单求无理数：const double pi = acos(-1.0)，注意三角函数使用弧度制。类似的还有 const double e = exp(1.0)。

6. 交错输出：printf("%d", q?a:b); q=!q;

7. 更新最值：ans=max(ans,dfs(i,j));

8. 初始化某个数组为正无穷：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）。

9. 求数组实际长度：sizeof(a)/sizeof(单位)，前者仅仅是整个数组占内存大小，必须除以单位才能得到数组的实际长度。

   • 注意这里的 a 是数组名，但如果用指针指向数组，sizeof(指针) 得到的却是指针的长度，这是数组名和指针的一大区别。
   • 在 32 位 (x86) 系统中，指针长度为 4，在 64 位 (x64) 系统中，指针长度为 8。

10. 两个整数相除并向上取整：(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 里面：

    // 完全闭包，无外部变量
    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)a 或 ll(a)，此外还新增了四种强转方法，用于类、结构体的强转。最基本的用法是 static_cast<long long>，效果和 C 的类似。

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

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

全新特性

• C++ 中最重要的特点就是「函数传引用调用」，例如 void swap(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;，在洛谷刷题比较常用。
  • 下面给出一个经典的类模板：

  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 模式：

#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. 表达式的运算顺序可能会关系到是否溢出，如果有大数相乘、相加，尽量先处理缩小运算符。