前言

一共八章

基本算法
基本数据结构
搜索
数学知识
数据结构进阶
动态规划
图论
综合技巧与实践

前置要求：简单熟悉C++这门语言。
学习算法，算法的门槛不像AI门槛那么高，每个人皆可学习。正如谚语所说：熟读唐诗三百首，不会作诗也会吟。
练习达到3000左右的题量，那你便可轻易Accepted一题。
学习算法，需要经过三个步骤：怎么做、为什么是对的、如何去想到这么做。

写学习笔记的目的有两个，一个是如果忘记可以快速拾起，二是也可以给他人查阅。

一、基本算法

位运算

原码
以有符号32位二进制数为例
一般假设一个二进制的数位为m，则其每个位数从左到右记为$m-1, m - 2, \dots ,2, 1, 0$。
原码：1011 0111 0111 1111 0011 0111 0111 1111
$ -931084159_{(10)} = -1 × (1 × 2^0 + 1 × 2^1 + \dots + 0 * 2^{32 - 1}) $
原码是给人类看的，最高位是符号位。
反码
反码就是将原码符号位不变，其他位取反得到。
原码：1100 1000 1000 0000 1100 1000 1000 0000
补码
补码就是反码加1
补码：1100 1000 1000 0000 1100 1000 1000 0001
补码就是机器真实存储的二进制，补码可以就是将二进制减法转换为加法，利用的是有限位数的二进制数的溢出，即取模运算。
总结
符号位为0，即正数和0，三码一致
符号位为1，即负数，计算机存储的是补码
原码变补码：符号位不变取反加1
补码变原码：可以是原码变补码的逆过程，也可以是符号位不变取反加1，二者等价

观察
1111 1111 -
0110 1010 =
1001 0101
总结
对于二进制数$S，有 \sim S = -1 - S$，因为-1的字面量为int，所以表示32位全为1的数。

	原码	反码	补码	十进制
int 32位	0000...0000	0000...0000	0000...0000	0
int 32位	0111...1111	0111...1111	0111...1111	2147483647
int 32位	1000...0000	1111...1111	1000...0000	-2147483648
int 32位	1000...0001	1111...1110	1111...1111	-1
unsigned int 32位	0000...0000	0000...0000	0000...0000	0
unsigned int 32位	1111...1111	1111...1111	1111...1111	4294967295

$2147483647 * 2 + 1 = 4294967295 $
科学计数法可以表示为 $ 2.147483647 × 10^9 $
最好背过2147483647。
移位运算
$1<<n=2^n, n>>1= \lfloor \frac n 2 \rfloor$
这里的$\lfloor \frac n 2 \rfloor$是向0取整

快速幂

快速幂简单来说就是利用下面这个公式
一个$base$进制的数

\[b = c_{n - 1}c_{n - 2}c_{n - 3} \dots c_{1}c_{0} \\ = c_{n-1}×base^{n-1}+c_{n-2}×base^{n-2} +\dots+ c_{1}×base^{1}+c_{0}×base^{0} \]

\[a^b = a^{c_{n-1}×base^{n-1}+c_{n-2}×base^{n-2} +\dots+ c_{1}×base^{1}+c_{0}×base^{0}} \\ = a×c_{n-1}×base^{n-1}×a×c_{n-2}×base^{n-2} ×\dots× a×c_{1}×base^{1}×a×c_{0}×base^{0} \]

参考链接
快速幂详解
例题：$a^b$ AcWing89

AC代码，展开查看

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL pow(int a, int b, int p){ // 请牢记此模板
    LL res = 1 % p;
    while(b){
        if(b & 1) res = res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}
int main(){
    int a, b, p;
    cin >> a >> b >> p;
    cout << pow(a, b, p) << endl;
    return 0;
}

例题：64位整数乘法 AcWing90
方法1：
原理和快速幂类似，时间复杂度$O(log_2b)$

AC代码1，展开查看

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL mul(LL a, LL b, LL p){
    LL res = 0;
    while(b){
        if(b & 1) res = (res + a) % p;
        a = a * 2 % p;
        b >>= 1;
    }
    return res;
}
int main(){
    LL a, b, p;
    cin >> a >> b >> p;
    cout << mul(a, b, p);
    return 0;
}

方法2：直接计算，算法时间复杂度$O(1)$ $$ a × b = k×p + a × b \ (mod \ p) \\ a × b \ (mod \ p) = a × b - k×p $$

AC代码2，展开查看

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD; // 可以存储十进制有效数字18~19位
ULL mul(ULL a, ULL b, ULL p){
    a %= p, b %= p; // 确保a * b 不会超过long double的整数表示的精确值
    ULL c = (LD) a * b / p;
    ULL x = a * b, y = c * p; // a * b 可能会溢出2^64
    // x % p 与 y % p 大小不确定
    LL ans = ((LL)(x % p) - (LL)(y % p) + p) % p; // (x - y) % p = ((x % p - y % p) + p) % p;
    return ans;
}
int main(){
    LL a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%llu", mul(a, b, p));
    return 0;
}

例题：起床困难综合症 AcWing998

AC代码，展开查看

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
pair<string, int> a[N];
int cal(int n, int bit, int now){
    int x;
    for(int i = 0; i < n; i ++ ){
        x = a[i].second >> bit & 1;
        if(a[i].first == "AND") now &= x;
        else if(a[i].first == "OR") now |= x;
        else now ^= x;
    }
    return now;
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ){
        cin >> a[i].first >> a[i].second;
    }
    int val = 0, ans = 0, res0, res1; // val不能超过m，ans 就是所求最大的伤害值
    for(int i = 29; i >= 0; i -- ){
        res0 = cal(n, i, 0), res1 = cal(n, i, 1); // 如果是1的话
        if(val + (1 << i) <= m && res0 < res1) // res0 = 0，res1 = 1
            val += 1 << i, ans += res1 << i;
        else ans += res0 << i;
    }
    cout << ans << endl;
    return 0;
}

例题：二进制中1的个数例题 AcWing901

AC代码，展开查看

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, a, ans;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ){
        ans = 0;
        scanf("%d", &a);
        for (int i = a; i; i -= i & -i) ans ++ ;
        printf("%d ", ans);
    }
    return 0;
}