前言
一共八章
- 基本算法
- 基本数据结构
- 搜索
- 数学知识
- 数据结构进阶
- 动态规划
- 图论
- 综合技巧与实践
前置要求：简单熟悉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\)进制的数
\[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;
}
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;
}