PAT 备考笔记

2020-07-29
  • CH2 C++入门
    • 2.1 宏定义 #define
    • 2.2 运算符
    • 2.3 顺序结构
    • 2.4 选择
    • 2.5 数组
    • 2.6 函数
    • 2.7 指针
    • 2.8 引用
    • 2.9 结构体
    • 2.10 Others
    • 2.11 多点测试
  • CH3 入门 模拟
  • CH4 入门 算法初步
    • 4.1 排序
    • 4.2 hash
    • 4.3 递归
    • 4.4 贪心
    • 4.5 二分 🍔
    • 4.6 two pointers
    • 4.7 打表
    • 4.8 活用递推
    • 4.9 随机选择算法
  • CH5 数学问题
    • 5.1 简单数学
    • 5.2 最大公约 & 最小公倍数 🍔
    • 5.3 分数
    • 5.4 素数
    • 5.5 质因子分解
    • 5.6 大数运算 🍔
    • 5.7 扩展欧几里得算法
    • 5.8 组合数
  • CH6 STL
    • 6.0 通用操作
    • 6.1 vector 动态数组
    • 6.2 set 集合
    • 6.3 String 字符串
    • 6.4 map 映射
    • 6.5 Queue 队列
    • 6.6 Priority_queue 优先队列
    • 6.7 stack 栈
    • 6.8 pair
    • 6.9 algorithm
  • CH7 数据结构
    • 7.1 栈
    • 7.2 队列
    • 7.3 链表
  • CH8 搜索
    • 8.1 DFS 深度优先搜索
    • 8.2 BFS 广度优先搜索
  • CH9 🌲
    • 9.1 二叉树
    • 9.2 二叉树的遍历
    • 9.3 树的遍历
    • 9.4 二叉查找树（BST）
    • 9.5 平衡二叉树（AVL树）
    • 9.6 并查集 🍔
    • 9.7 堆
    • 9.8 哈弗曼树
  • CH10 图
    • 10.1 定义
    • 10.2 存储
    • 10.3 遍历
    • 10.4 最短路径
    • 10.5 最小生成树
    • 10.6 拓扑排序
    • 10.7 关键路径
  • Ch11 动态规划
    • 11.1 最大连续子序列和：
    • 11.2 最长不下降子序列：
    • 11.3 最长公共子序列：
    • 11.4 最长回文子串：
    • 11.5 DAG 最长路 略
    • 11.6 背包问题
  • CH12 字符串
    • 12.1 字符串hash
    • 12.2 KMP
  • Ch13 拓展
    • 13.1 分块
    • 13.2 树状数组
  • Ch14 心得与技巧
  • Ch15 考前与考试时

// 自认为的重点用 🍔 表示

目录 展开

CH2 C++入门

2.1 宏定义 #define

尽量只用来定义const，定义语句的时候要加括号，#define ADD(a,b) ((a)+(b))

2.2 运算符

  • 除法：结果向下取整
  • ++i vs i++
  • 条件运算符 A ? B : C A为真，则执行B，否则执行C
  • 位运算符 << 左移 >> 右移 & w按位与 | 按位或 ^ 按位异或 ~ 按位取反

2.3 顺序结构

  1. scanf("%d", &n)
    • 除了 char 数组整个输入的情况不加 &，其他所有变量类型都要加 &
    • int-%d longlong-%lld float-%f double-%lf char-%c char 数组-%s
    • 这里 %lld 有时候会报错，改成 %l64d 试试
    • scanf ("%c") 可以读入空格与换行；其它以空格%换行为结束标志
    • scanf ("%*c") 用来跳过行尾的换行符
  2. printf("%d", n) 无需 &
    • int-%d longlong-%lld float-%f double-%f char-%c char 数组-%s
    • double 精度比 float 高！两个小数相乘，用 double；
  3. 输入输出格式 🍔
    • %3d 不足3位的 int 右对齐输出，高位用空格补齐，超过3位保持原样；
    • %-3d 不足3位的 int 左对齐输出，高位用空格补齐，超过3位保持原样；
    • %03d 不足3位的 int 右对齐输出，高位用0补齐，超过3位保持原样；
    • %.5f 保留5位输出，超过部分四舍五入，否则0补齐；
    • %+d 无论正数负数，都要把符号输出；
  4. a = getchar() putchar(b) 输入输出单个字符
    • 若只是getchar() 则输入的字符被接受，但是没有被存储；
    • getchar() 可以识别空格&换行符
  5. 格式化流输入输出：#include <iomanip>
    • cout.width(n);cout.fill(' ');cout<<a;右对齐，长度为 n，不足部分空格补齐（每次输出前都要调用）
    • cout<<oct<<a; 八进制；cout<<hex<<a; 十六进制；
  6. 在流输入输出前加一句 ios::sync_with_stdio(false); 可和 scanf,printf 一样快；
  7. 常用 math 函数 #include <math.h>
    • fabs(double x) 对 double 型取绝对值；
    • floor(double x) 向下取整；ceil(doubble x) 向上取整；
    • pow(double r, double p) sqrt(double x) log(double x)ln
    • sin(double x) cos(double x) tan(double x) 参数要求是弧度制；
    • const double pi = acos(-1.0); // π都这样写
    • double db = sin(pi * 45 /180);
    • round(double x) 四舍五入，返回 double；
    • log(x) 想求 \(log_mn\)，需要 double a = log(n)/log(m);

2.4 选择

  1. if 如果表达式是 n!=0，则可省略为 if(n)； n==0，则可省略为 if(!n)
  2. switch
    1
    2
    3
    4
    5
    6
    7
    8
    9
    switch(a+b){
        case const int:
        do sth;
        break;
     
        default:
        do sth;
    }
     

2.5 数组

  1. 初始化： int a[10] = {}; 全部置零(只能置零)
  2. 如果数组大小较大（~10^6级别），需要将其定义在 main 函数之外（系统栈空间不足）
  3. memset(数组名,值,sizeof(数组名))为数组整体赋值，只可以是-1或0！需要string.h头文件； fill(start,end,value) 可以是任意值；
  4. 字符数组只在初始化的时候可以赋值字符串；
  5. 字符数组结尾\0，故数组大小至少为长度+1；
  6. 字符数组输入输出：
    • scanf() printf() 无需&，空格或换行作为结尾；
    • getchar() putchar()
    • gets() 输入一行；scanf 完一个整数之后，需要先 getchar 接收 \n，再 gets； puts() 输出一行；将一维数组输出后再输出一个\n；
  7. string.h 🍔 strlen(str)数组中第一个\0之前字符的个数； strcmp(str1,str2) str1 小返回负整数，str1 大返回正整数，相等返回0； strcpy(str1,str2) 将 str2 复制到 str1； strcat(str1,str2) 将 str2 接在 str1 后面，保存在 str1 中，返回值为 &str1[0]； strncat(str1,str2,n) str2 的前 n 个字符连接到 str 的末尾； strchr(str,c) 在 str 中寻找一个字符 c，返回指针，返回值-str 就是具体索引位置； strstr(str1,str2) 在 str1 中寻找 str2，和上面一样返回指针，-str1 得索引；
  8. sscanf(str1,"%d", &n) 从 str1 输入到变量中（→）；支持正则表达式 #TODO sprintf(str1,"%d", &n) 把 n 以 %d 格式写到 str 1 字符数组中（←）；

2.6 函数

参数是数组时，数组的第一维不需要填写长度；调用时只用写数组名；数组为传引用；

2.7 指针

  1. & 取址，得到 unsigned 类型整数；
  2. 在数据类型后面加 * 表示指针变量：int* p1, *p2, *p3; int *p = &a; 其中 p 是地址，*p 是地址中存放的元素； 基类型必须和指针变量存储的地址类型相同；
  3. 指针变量加减法：地址距离（差了几个该类型的值，而非字节数），下一个上一个；
  4. 数组：a == &a[0]; *(a+i) == &a[i]; scanf("%d",a+i) for(int *p=a;p<a+10;p++) printf("%d ",*p);
  5. 传参传指针
    1
    2
    3
    4
    5
    6
    void swap(int *a, int *b){
        int temp = *a;
        *a = *b;
        *b = temp;
    }
     

2.8 引用

  1. 直接在函数的参数类型后面加 & 即可；
  2. 函数传参：指针的引用；
    1
    2
    3
    4
    5
    6
    void swap(int* &a, int* &b){
        int* temp = a;
        a = b;
        b = temp;
    }
     
  3. 常量不可使用引用；

2.9 结构体

  1. 初始化：
    1
    2
    3
    4
    5
    6
    7
    8
    struct student{
        char id;
        char gender;
        char name[20];
    }Alice,Bob,stu[100];    // AB代表两个结构体变量，stu代表很多学生的数组
     
    studentinfo Alice;      // 和上面等价
     
  2. 结构体里面不能定义自己本身，但是可以定义自身类型的指针变量：
    1
    2
    3
    4
    5
    struct node{
        node n;      // 不可以
        node* next;  // 可以
    };
     
  3. 访问元素
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct student{
        char id;
        char gender;
        char name[20];
    }stu,*p;
     
    stu.id;
    (*p).id;
    p->id;
     
  4. 初始化
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    struct student{
        char id;
        char gender;
        student(){}    // 默认构造函数，就是没分号
        student(int _id,char _gender){
            id = _id;
            gender = _gender;
        }
        stdent(int _id,char _gender):id(_id),gender(_gender) {}
    };
     

2.10 Others

  1. getline 两者不可混淆！
    • cin.getline(str1,100); 把一整行读入 char 型数组 str1[100]；
    • getline(cin,str); string 容器 # TODO
  2. cout<<setiosflags(ios::fixed)<<setprecision(2)<<123.456<<endl;
  3. 浮点数比较
    1
    2
    3
    4
    5
    6
    7
    const double eps = 1e-8;
    #define Equ(a,b) ((fabs((a)-(b)))<(eps))  // 等于
    #define More(a,b) (((a)-(b))>(eps))       // 大于
    #define Less(a,b) (((a)-(b))<(-eps))      // 小于
    #define MoreEqu(a,b) (((a)-(b))>(-eps))   // 大于等于
    #define LessEqu(a,b) (((a)-(b))<(eps))    // 小于等于
     
  4. 计算结果0可能是很小的负数，或者-0.0，这些都要考虑；

2.11 多点测试

输入 while (scanf(%d,&n)!=EOF)

CH3 入门 模拟

//NOTE1 字符串使用 scanf 输入的正确方式 //NOTE2 const 变量才可做静态数组长度

CH4 入门 算法初步

4.1 排序

//NOTE3 遍历一遍，比较多个量！ round(int n) 四舍五入 //NOTE4 排序 x 且返回索引的例子，注意并列排名的索引处理 //NOTE5 (已经更改) scanf 输入 string，这样操作自己电脑可以，PAT 过不了！

1
2
3
4
string str;
str.resize(20);
scanf("%s",str[0]);
 

//NOTE6 printf 精度控制 //NOTE7 char 数组要这样比大小

4.2 hash

引子：将输入的数字作为数组下标使用

  1. hash表：h = key % mod; // mod = tsize = 素数
  2. 线性探查法，平方探查法，链地址法
  3. (x,y)： x * range + y;
  4. 字符：A-Z = 0-25；后面的数字可以 26-35，若是固定格式，也可直接数字使用

//NOTE8 取char长度，要 #include <cstring> //NOTE9 所有东西的初始化不能忘！

4.3 递归

4.4 贪心

当前状态局部最优，使全局最优

4.5 二分 🍔

  1. mid = (left + right)/2; 可能会溢出，改用 mid = left + (right - left)/2;
  2. 二分模板 P129
  3. 最后一个满足条件 A <=> 第一个满足 !A
  4. 二分幂：b 奇数 \(a^b = a * a^b\)；b 偶数 \(a^b = a^{(b/2)} * a^{(b/2)}\) 进阶：b二进制表示，a计算相乘
  5. if (b%2 == 1) 可以写成 if (b & 1) 速度更快
  6. 大于 num 的第一个值 upper_bound (v.begin(), v.end(), num, cmp) 大于等于 num 的第一个值 lower_bound (v.begin(), v.end(), num, cmp) 均是返回指针或迭代器

4.6 two pointers

  1. 两个指针有制约关系，使得 O(\(n^2\)) 变为 O(n)。如两边同时向中间走，如序列合并。
  2. 归并排序 递归 / 循环方式 //B1035/A1089
  3. 快速排序
  4. cpp 随机数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    int main(){
        srand((unsigned)time(NULL));    // 生成随机种子
        printf("&d",rand()%(b-a+1)+a);  // [a,b]范围，
        printf("&d",rand*rand());       // 可两rand相乘范围更大
        printf("&d",(int)(round(1.0*rand()/RAND_MAX*(b-a+1)+a)));//大范围[a,b]
        return 0;
    }
     
  5. 随机快排：随机选择主元，而非起始作为主元 //NOTE 10 数组去重

4.7 打表

  1. 在程序中一次性计算出所有需要用到的结果，之后直接查询
  2. 在程序 B 算出来，然后直接把结果写在 A 中，A 就可以直接用了……
  3. 对于不会做的，先暴力小范围算，找到结果的规律

4.8 活用递推

找深层次规律，而非简单模拟

4.9 随机选择算法

  1. 原理：找出序列中第 M 大的数字：类似随机快排，比较当前主元序号与 M 大小关系，二分下去递归即可
  2. 一个集合拆成两个，在两集合个数差最小时，求两集合s元素和只差的最大值：随机选择，找到第 n/2 大的数，左右即为分开的集合

CH5 数学问题

5.1 简单数学

  1. 给出的数字的范围作为边界，一定要进行测试

5.2 最大公约 & 最小公倍数 🍔

  1. 最大公约数 d：辗转相除法 int gcd(int a,int b){return !b?a:gcd(b,a%b);}
  2. 最小公倍数：a/d*b（防止溢出）

5.3 分数

  1. 表示： struct Fraction{int up,down;//分子分母};
    • 使分母 down 为非负数，分子可正可负
    • 分数为零，则分子 = 0，分母 = 1
    • 分子与分母互质
  2. 化简：上述每条规则一个if
  3. 运算：分子分母分别运算，最后化简；若除数分子为零，输出错误；分子分母使用 long long 存储。
  4. 输出
    • 先化简
    • 分母为1，则不输出分母
    • 假分数，则带分数形式输出
    • 以上均不满足，直接输出

5.4 素数

  1. 判断素数：不能被 1 ~ (int)sqrt(1.0*n) 整除（#include <math.h>）
  2. 素数表获取： Eratosthenes 筛法 O( n * log ( logn ) )：对于每个素数，筛去它的所有倍数 欧拉筛法：每个合数只用其最小的一个质因数去筛
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    const int MAXN = 3000001;
    int prime[MAXN];            // 保存素数
    bool vis[MAXN] = {0};       // 初始化
    int Prime(int n)
    {
        int cnt=0;
        for(int i=2; i<n; i++)
        {
            if(!vis[i])
            prime[cnt++]=i;
            for(int j=0; j<cnt && i*prime[j]<n; j++)
            {
                vis[i*prime[j]] = 1;
                if(i%prime[j] == 0)     //关键
                break;
            }
        }
        return cnt;     // 返回小于n的素数的个数
    }
     

// NOTE 11 进制转换模板

5.5 质因子分解

  1. 结构体 factor 存因子与其个数。fac 数组大小开到 fac[10] 即足够 int 范围
  2. 枚举 1 ~ sqrt(n) 范围的所有质数，判断是否为质因子，是，则不断除计算个数
  3. 若最后 n > 1，则将其加入 fac 数组

// NOTE 12 vector 传参

5.6 大数运算 🍔

  1. 存储：整数高位存数组高位！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    struct bign {
    int d[1000];
    int len;
    bign(){                     //构造函数
        memset(d,0,sizeof(d));
        len = 0;
        }
    };
     
  2. 输入：字符串输入，倒序赋值给 bign
  3. 比较大小：先比 len，再从高到低比较
  4. bign + bign：关键步骤 c.d[c.len++] = temp % 10;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    bign plus(bign a, bign b){
        int c,temp;
        bign result;
        for (int i = 0;i<a.len || i<b.len;i++){
            temp = a.d[i] + b.d[i] + c;
            result.d[result.len++] = temp%10;
            c = temp / 10;
        }
        while (c!=0){
            result.d[result.len++] = c;
        }
        return result;
    }
     
  5. bign – bign：先比大小，再大 – 小
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bign sub(bign a,bign b){
        bign result;
        for(int i = 0;i<a.len || i<b.len;i++){
            if (a.d[i] < b.d[i]){
                a.d[i] += 10;
                a.d[i+1] -=1;
            }
            result.d[result.len++] = a.d[i] - b.d[i];
        }
        while(result.d[result.len-1] == 0 && result.len > 1){
            result.len --;
        }
        return result;
    }
     
  6. int * bign：进位可以是好大的数字！不用严格一位一位的！P174
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bign multi(bign a, int b){
        int c,temp;
        bign result;
        for (int i = 0;i<a.len;i++){
            temp = a.d[i] + b + c;
            result.d[result.len++] = temp%10;
            c = temp / 10;
        }
        while (c!=0){
            result.d[result.len++] = c % 10;
            c = c/10;
        }
        return result;
    }
     
  7. bign / int：同上
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bign devide(bign a, int b,int &r){  // r 为余数
        bign result;
        result.len = a.len;
        for(int i = a.len-1;i>=0;i--){
            r = r*10 + a.d[i];
            if (r < b)c.d[i] = 0;
            else{
                result.d[i] = r / b;
                r = r % b;
            }
        }
        while(result.d[result.len-1] == 0 && result.len > 1){
            result.len --;
        }
        return result;
    }
     
  8. 拓展的高精度算法：10000进制

5.7 扩展欧几里得算法

  1. 问题：a * x + b * y = c的解
  2. 有解条件：c mod gcd(a,b) == 0
  3. 转化：a = \(\frac{a}{gcd(a,b)}\)；b = \(\frac{b}{gcd(a,b)}\)；c = \(\frac{c}{gcd(a,b)}\)
  4. 求解：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void exgcd(int a,int b,int c,int &x,int &y){
        if (a == 0){
            x = 0;y = c/b;
        }else{                  // 不懂 # TODO
            exgcd(b%a,a,c,x,y);
            y = x;
            x = (c-b*y)/a;
        }
    }
     
  5. 构造通解：\(x_0\) 和 \(y_0\) 为一组解，则通解为 $$ \begin{cases} x =& c * x_0 + c * b * k\ y =& c * y_0 – c * a * k \end{cases} $$

5.8 组合数

  1. n! 中有 \( \frac{n}{p} + \frac{n}{p^2} + \frac{n}{p^3} + … \) 个质因子p
  2. 组合数计算： \(C_n^m = C_{n-1}^m + C_{n-1}^{m-1} \) 或 \(C_n^m = \frac{n-m+1}{m} * C_n^{m-1} \)

CH6 STL

6.0 通用操作

  1. 迭代器
  • v.begin() v.end()
  • v.rbegin() v.rend() 逆向迭代器

6.1 vector 动态数组

  1. vector< vector<int> > name;
  2. vector 数组 vector<int> vi[100];
  3. 二维 vector：vector<vector<int> > b(m, vector<int>(n));
  4. 元素访问
    • 下标 vi[0]
    • 迭代器 只在 vector 和 string 中可以有迭代器 + 整数的写法
      1
      2
      3
      vector <typename>::iterator it = vi.begin();
      printf("%d",*(it+3));
       
  5. 常用函数
    • push_back(x) 在最后添加元素
    • pop_back() 删除尾元素
    • size() clear()
    • insert(it,x) 在 it 位置插入 x 元素
    • erase(it) 删除 it 处的元素
    • erase(first,last) 删除 first ~ last 的元素
  6. 用途：
    • 存储个数不确定的 数组
    • 有时要输出不确定个数个数据在同一行，可用 vector 先存起来
    • 用邻接表存储图

// NOTE 13 vector 数组

6.2 set 集合

  1. 内部自动有序，不含重复元素
  2. #include <set>
  3. 定义 set<typename> name; 默认升序
    • 降序 set< int, greater<int> > s;
  4. 元素访问：只能通过迭代器 set<typename>::iterator it;
    1
    2
    3
    4
    for(set<int>::iterator it = st.begin; it!=st.end; it++){
        printf("%d",*it);  
    }
     
  5. 常用函数
    • st.insert(value)
    • set<int>::iterator it = st.find(value); // 返回迭代器
    • st.erase(it) st.erase(value) // 键&值均可删除
    • st.erase(firstit,lastit);
    • int size = st.size();
    • st.clear();
  6. 用途
    • 自动去重并按升序排列

// NOTE14 set 判断元素是否存在 b.find(*it)!=b.end() // NOTE15 printf 打印%

6.3 String 字符串

  1. #include <string>;
  2. 定义 string str = "abcd";
  3. 输入：
    • cin>>str; 忽略空格、回车、TAB 等，遇到空格停止
    • getline(cin,str,'\n') 遇到 ‘\n’ 终止输入
  4. printf 输出 string：printf("%s",str.c_str());
  5. iterator：同vector
  6. 常用函数
    • + 这里的两个操作数至少有一个是 string 对象，"a"+"b" 非法
    • = == != > < >= <=
    • str.length()
    • str.size()
    • str.insert(pos,sr2) // 在 pos(数字) 位置插入 str2
    • str.insert(it,it2,it3) // 在 it 位置插入 it2 到 it3 的
    • str.erase(it);
    • str.erase(firstit,lastit);
    • str.erase(pos,length) // pos length 均为数字
    • str.clear();
    • string str1 = str.substr(pos,len);
    • string::npos 是常数，为-1或4294967295
      • 作为 string 的成员函数的一个长度参数时，表示“直到字符串结束”
      • find 函数在找不到指定值得情况下会返回 string::npos
    • str.find(str2) 返回第一次出现的位置 (pos) 或 npos
    • str.replace(pos,len,str2) 从 pos 号位的 len 长度换为 str2
    • str.replace(it1,it2,str2) 从 it1 到 it2 换为 str2
    • str.c_str() 转换成字符数组
    • str.find('a',k) 从 k 开始寻找 ‘a’，k 可忽略
    • str.find("asd",k) str.find(str,k)

6.4 map 映射

  1. 可以将任何基本类型映射到任何基本类型（基本类型包括 STL 容器） map 键值是唯一的，如果一个键多个值，需要 multimap。
  2. 定义 map<typename1,typename2> mp; // 前 key，后 value 若是字符串→int，必须使用 string 而非 char 数组
  3. 访问：map 内部会按照键从小到大的顺序排列
    • 下标访问 map<char,int> mp; mp[key]
    • 迭代器
      1
      2
      3
      4
      for(map<char,int>::iterator it = mp.begin();it!=mp.end();it++){
          printf("%c %d",it->first,it->second);
      }   // it->first 键；it->second 值
       
  4. 函数
    • it = mp.find(key)
    • mp.erase(it); mp.erase(key);
    • mp.erase(firstit,lastit);
    • mp.size() mp.clear();
    • mp.count(10); 返回 mp 中值为10的元素个数
  5. 用途
    • 字符串与整数之间的映射
    • 判断大整数或其他数据类型是否存在

// NOTE 16 scanf 接收换行符 // NOTE 17 STL string 大小写转换 // NOTE 18 map 按照 value 排序：

6.5 Queue 队列

  1. #include <queue>; queue<typename>name;
  2. 函数
    • q.push(元素); q.pop();// 出队，无返回
    • q.front() // 队头 q.back() // 队尾
    • q.empty() // 判断k是否空，true为空
    • q.size()
  3. 用途：
    • 实现广度优先搜索时 # TODO
    • 使用 q.front() q.back() 前，一定先 q.empty() 判断

6.6 Priority_queue 优先队列

  1. 队首元素一定是优先级最高的
  2. #include <queue>; priority_queue<typename>name;
  3. 函数
    • q.top() 只能访问队顶元素
    • q.push(元素) q.pop(); q.empty() q.size()
  4. 优先级设置
    • 基本数据类型 ( int, double, char )： ps: map multimap set multiset 均可用此种方式进行内部排序 下面的 >> 中间必须有空格！否则编译失败！ priority_queue<typename1, vector<typename1>, less<int> > q;数字越大优先级越大 priority_queue<typename1, vector<typename1>, greater<int> > q;数字越小优先级越大
    • 结构体类型
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      struct fruit{
          string name;int price;
          friend bool operator < (const &fruit f1,const &fruit f2){  
              // 引用没有也可，有效率高
              retutn f1.price < f2.price;
              // 这里与sort函数的顺序是相反的！
          }
      }
      priority_queue<fruit> pq;
       
      或
      1
      2
      3
      4
      5
      6
      7
      struct cmp{
      bool operator () (const &fruit f1,const &fruit f2){
          retutn f1.price < f2.price;
          }
      }
      priority_queue<fruit, vector<fruit>, cmp> q;
       
  5. 用途
    • 贪心问题，Dj 算法的优化 # TODO
    • top() 之前，先要 empty() 判断

6.7 stack 栈

  1. #include <stack>; stack<typename> name;
  2. 函数
    • st.top() 只能访问栈顶元素
    • st.push(元素); st.pop(); st.empty(); st.size()
    • 清空：while(!st.empty()){st,pop();} （其实新建一个栈更快）
  3. 用途
    • 模拟实现递归

6.8 pair

  1. #include <utility>; 或 #include <map>;
  2. pair<typename1,typename2> name; pair<string,int> p("haha",5); make_pair("haha",5);
  3. 函数
    • 元素访问 p.first p.last
    • 比较大小：直接使用符号比较。先以 first 大小为标准，first 相等时才判别 second 大小
  4. 用途
    • 代替二元结构体及其构造函数
    • 作为 map 的键值进行插入
      1
      2
      3
      map<string,int>mp;
      mp.insert(make_pair("haha",5));
       

6.9 algorithm

  1. max() min() abs(整数)
    • 若想比较三个：max(x,max(y,z))
    • 浮点型绝对值：math 头文件下的 fabs()
  2. swap(x,y) 交换 xy 值
  3. reverse(it1,it2)
  4. next_permutation(pos1,pos2) 给出一个序列在全排列里的下一个全排列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int a[10] = {1,2,3};
    do{
        printf("%d%d%d ",a[0],a[1],a[2]);
    }while(next_permutation(a,a+3));
     
    // 输出 123 132 213 231 312 321
    // 到最后一个 返回 false
    // 不能用 while，否则第一个不输出
     
  5. fill(pos1,pos2,value) 把数组/容器某一段赋为相同的值 类似地，memset(it,int value,n) 将从 it 开始的前 n 个字节赋为相同的值（来自 string.h 头文件）
  6. sort(it1,it2,cmp(选填))

// NOTE 19 cmp 写法

CH7 数据结构

7.1 栈

  1. 后进先出
  2. 栈顶指针 TOP 栈空时 TOP = -1

7.2 队列

7.3 链表

  1. struct node {typename data; node* next;};
  2. 为新节点分配内存空间：
    • typename1* p = (typename*)malloc(sizeof(typename)); typename1* p = (typename*)malloc(100*sizeof(typename)); 申请一块 sizeof(typename) 大小的空间，并返回指针，并转化成 typename* 类型；当申请较大空间时，可能失败，返回 NULL
    • typename* p = new typename; typename* p = new typename[100];
  3. 释放内存空间：
    • malloc：free(p)
    • new：delete(p)
  4. 动态链表
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
     
    struct node{
        int data;
        node* next;
    };
     
    node* create(int array[], int size){
        node *p, *pre, *head;
        head = new node;
        head -> next = NULL;
        pre = head;
        for(int i = 0; i < size; i++){
            p = new node;
            p -> data = array[i];
            p -> next = NULL;
            pre -> next = p;
            pre = p;
        }
        return head;
    }
     
    int search(node* head, int x){
        int count = 0;
        node *p = head -> next;
        while (p != NULL){
            if (p -> data == x) count++;
            p = p -> next;
        }
        return count;   // 链表中 x 的个数
    }
     
    void insert(node* head, int pos, int x){
        node *q = head;
        while(pos-- > 0){q = q -> next;}  // 找到 pos-1 位置
        node *p = new node;
        p -> next = q -> next;
        q -> next = p;
        p -> data = x;
    }
     
    void del(node* head, int x){
        node *p = head -> next;
        node *pre = head;
        while(p != NULL){
            if (p -> data == x){
                pre -> next = p -> next;
                delete p;
                p = pre -> next;
            }
            else{
                pre = p;
                p = p -> next;
            }
        }
    }
     
    int main(){
        int array[5] = {1,2,3,4,5};
        node* L = create(array, 5);
        L = L -> next;    // 头结点没有数据
        while (L != NULL){
            printf("%d ",L -> data);
            L = L -> next;
        }
    }
     
  5. 静态链表 node 用 hash 实现
  6. 答题模板：
    1. 定义链表
    2. 初始化链表，将特征值置为最小的数或 false
    3. 从首地址开始遍历，同时对性质进行统计
    4. 静态链表，下标不连续：按性质排序 // 一定注意，题目给出的可能有无效节点

CH8 搜索

8.1 DFS 深度优先搜索

  1. 从 n 个数之中选 k 个，和为 x，的所有方案

8.2 BFS 广度优先搜索

// STL 的 queue ，无法修改已入队的元素，因此最好将序号入队，而非整个元素入队。

CH9 🌲

9.1 二叉树

  1. 空树，层次，度，深度，高度，森林
  2. n 个结点的🌲，边数一定是 n-1；(连通 && (边数-顶点数 == 1)) == 树
  3. 满二叉树，完全二叉树
  4. 存储
    • 结点定义
      1
      2
      3
      4
      5
      6
      7
      struct node{
          typename data;
          int layer;  // 用于层序遍历
          node *lchild;
          node *rchild;
      };
       
    • 生成新结点
      1
      2
      3
      4
      5
      6
      7
      node* newNode(int v){
          node *Node = new node;
          node->data = v;
          node->lchild = node->rchild = NULL;
          return Node;
      }
       
  5. 查找
    1
    2
    3
    4
    5
    6
    7
    void search(node *root,int value,int newdata){
        if (root == NULL)return;
        if (root->data == value)root->data = newdata;
        search(node->lchild,value,newdata);
        search(node->rchild,value,newdata);
    }
     
  6. 插入：插入位置即为查找失败位置 只要是修改了结构，就一定要使用引用
    1
    2
    3
    4
    5
    6
    void insert(node* &root,int x){
        if (root == NULL){root = newNode(x);return;}
        if (要插在左边){insert(root->lchild,x);}
        else {insert(root->rchild,x);
    }
     
  7. 创建
    1
    2
    3
    4
    5
    6
    7
    8
    node* Create(int data[],int n){
        node* root = NULL;
        for(int i = 0;i<n;i++){
            insert(root,data[i]);
        }
        return root;
    }
     
  8. 完全二叉树的存储：
    • 编号：1号为根结点；x 左子树 2x，右子树 2x+1；
    • 判断根节点：该节点左子节点编号 root * 2 > n;
    • 判断空节点：root > n;

9.2 二叉树的遍历

  1. 遍历模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void order(node *root){
        if (root == NULL)return;
        printf("%d",root->data);    //先序
        order(root->lchild);
        printf("%d",root->data);    //中序
        order(root->rchild);
        printf("%d",root->data);    //后序
    }
     
  2. 层序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void layerOrder(node* root){
        queue <node*> q;
        // 队中元素为地址，就可以对 q.front()->data 直接修改
        root->layer= 1;
        qu.push(root);
        while(!q.empty()){
            node* top = qu.front();
            printf("%d",top->data);
            if (top->lchild != NULL) {
                now->lchild->layer = now->layer+1;
                q.push(top->lchild);
            }
            if (top->rchild != NULL) {
                now->rchild->layer = now->layer+1;
                q.push(top->rchild);
            }
        }
    }
     
  3. 先/后序遍历+中序遍历 重建二叉树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    node* createTree(int preL,int preR,int inL,int inR){
        if (preL>preR)return NULl;
        node* root = new node;
        root->data = pre[preL];
        int leftnum,i;
        for(i = inL;i<inR;i++){
            if(in[i] == pre[preL]){
                leftnum = i-inL;break;
            }
        }
        root->lchild = createTree(preL+1,preL+leftnum,inL,i-1);
        root->rchild = createTree(pre+leftnum+1,preR,i+1,inR);
        return root;
    }
     
  4. 二叉树的静态实现 P298 略

9.3 树的遍历

  1. 结构体定义
    1
    2
    3
    4
    5
    struct node{
        int data,layer;
        vector<int> child;  //存放子节点下标
    }Node [maxn];           //maxn为结点上限个数
     
  2. 新建节点
    1
    2
    3
    4
    5
    6
    7
    int index = 0;
    int newNode(int v){
        Node[index].data = v;
        Node[index].child.clear();
        return index++;
    }
     
  3. 先序遍历 相当于 DFS
    1
    2
    3
    4
    5
    6
    7
    void PreOrder(int root){
        printf("%d",Node[root].data);
        for(int i = 0;i<Node[root].child.size();i++){
            PreOrder(Node[root].child[i]);
        }
    }
     
  4. 层序遍历 相当于 BFS
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void InOrder(int root){
        queue<int>q;
        q.push(root);
        Node[root].layer = 0;
        while(!q.empty()){
            int top = q.front();q.pop();
            printf("%d",Node[top].data);
            for(int i = 0;i<Node[top].child.size();i++){
                q.push(Node[top].child[i]);
                Node[Node[top].child[i]] = Node[top].layer+1;
            }
        }
    }
     

9.4 二叉查找树（BST）

  1. 定义：lchild < root < rchild
  2. 查找
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void search(node *root,int x){
        if (root == NULL) return;       // 查找失败
        if (root->data = x) do dth.     // 查找成功
        else if (root->data < x)
            search(root->rchild,x);
        else
            search(root->lchild,x);
    }
     
  3. 插入
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void insert(node* &root,int x){
        if (root == NULL) {
            root = newNode(x);
        } // 查找失败,插入
        if (root->data = x) return;
        else if (root->data < x)
            insert(root->rchild,x);
        else
            insert(root->lchild,x);
    }
     
  4. 建立
    1
    2
    3
    4
    5
    6
    7
    8
    node create(int data[],int n){
        node *root = NULL;
        for(int i = 0;i<n;i++){
            insert(root,data[i]);
        }
        return root;
    }
     
  5. 删除
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    node* findMax(node* root){
        while (root -> rchild != NULL){
            root = root -> rchild;
        }
        return root;
    }
     
    node* findMin(node* root){
        while (root -> lchild != NULL){
            root = root -> lchild;
        }
        return root;
    }
     
    void erase(node* &root,int x){
        if (root == NULL) return;
        if (root -> data == x){
            if (root -> lchild == NULL && root -> rchild == NULL) root = NULL;
            //总优先删除左会导致高度不平衡，最好记录树的高度，删除高的
            else if (root -> lchild != NULL){
                node* pre = findMax(root->lchild);
                root -> data = pre -> data;
                erase(root -> lchild, pre -> data);
            }
            else{
                node* next = findMin(root -> rchild);
                root -> data = next -> data;
                erase(root -> rchild, next -> data);
            }
        }
        else if (root -> data < x){
            erase(root -> rchild, x);
        }
        else erase(root -> lchild, x);
    }
     
  6. 性质：中序遍历有序

9.5 平衡二叉树（AVL树）

  1. 定义：左右子树高度之差绝对值 <= 1

    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
    28
    29
    struct node{
        int data,height;
        node *lchild, *rchild;
    };
     
    node* newNode(int v){
        node* Node = new node;
        Node -> v = v;
        Node -> height = 1;
        Node -> lchild = Node -> rchild = NULL;
        return Node;
    }
     
    // 获得根结点高度
    int getHeight(node* root){
        if (root == NULL)return 0;
        return root -> height;
    }
     
    int getBalanceFactor(node* root){
        return getHeight(root -> lchild) - getHeight(root -> rchild);
    }
     
    // 更新根节点高度
    void updateHeight(node* root){
        root -> height = max(getHeight(root -> lchild),getHeight(root -> rchild))+1;
    }
     
     

  2. 查找 与二叉树无异

  3. 插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //左旋
    void L(node* &root){
        node* temp = root->rchild;
        root->rchild = temp->lchild;
        temp->lchild = root;
        updateHeight(root);
        updateHeight(temp);
        root = temp;
    }
     
    //右旋：交换lr
    void R(node* &root){
        node* temp = root->lchild;
        root->lchild = temp->rchild;
        temp->rchild = root;
        updateHeight(root);
        updateHeight(temp);
        root = temp;
    }
     
    树形 判定条件 调整方法
    LL BF(root) == 2; BF(root->lchild) == 1 R(root);
    LR BF(root) == 2; BF(root->lchild) == -1 L(root->lchild); R(root);
    RR BF(root) == -2; BF(root->rchild) == -1 L(root);
    RL BF(root) == -2; BF(root->rchild) == 1 R(root->rchild); L(root);
    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
    28
    29
    30
    31
    32
    33
    34
    void insert(node* &root,int v){
        if (root == NULL){
            root = newNode(v);
            return;
        }
        if (v < root->v){
            insert(root->rchild,v);
            updateHeight(root);
            if (getBalanceFactor(root) == 2){
                if (getBalanceFactor(root->lchild) == 1){
                    R(root);
                }
                else if (getBalanceFactor(root->lchild) == -1){
                    L(root->lchild);
                    R(root);
                }
            }
     
        }
        else{
            insert(root->rchild,v);
            updateHeight(root);
            if (getBalanceFactor(root) == -2){
                if (getBalanceFactor(root->rchild) == -1){
                    L(root);
                }
                else if (getBalanceFactor(root->rchild) == 1){
                    R(root->rchild);
                    L(root);
                }
            }
        }
    }
     

  4. 建立 //A1066

    1
    2
    3
    4
    5
    6
    7
    8
    node* create(int data[],int n){
        node* root = NULL;
        for(int i = 0;i<n;i++){
            insert(root,data[i]);
        }
        return root;
    }
     

9.6 并查集 🍔

  1. 合并 & 查找
    • int father[i] // 表示 i 的父亲结点
    • 根结点：结点是自己
  2. 初始化：一开始每个元素都是单独的集合，因此所有 father[i] = i;
  3. 查找：查找结点所属集合的根结点，以判断多个结点是否在同一个集合
    1
    2
    3
    4
    5
    6
    7
    int findFather(int x){
        while(x != Father[x]){
            x = Father[x];
        }
        return x;
    }
     
  4. 合并：两个集合合并成一个
    1
    2
    3
    4
    5
    6
    7
    void Union(int a,int b){    // 小写 union 是关键字
        int faA = findFather(a);
        int faB = findFather(b);
        if (faA != faB) //ab在同一集合不合并，保证同一集合不产生环，即并查集每个集合都是一棵树
            father[faA] = faB;
    }
     
  5. 路径压缩
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int findFather(int x){
        int a = x;
        while(x != Father[x]){
            x = Father[x];
        }
        // 第二遍，把路过的所有节点的father都改成根结点
        while(a != Father[a]){
            int z = Father[a];
            a = Father[a];
            father[z] = x;
        }
        return x;
    }
     

9.7 堆

一定是从 1 开始的序列

  1. 大顶堆，小顶堆，用来实现优先队列
  2. 建堆（以大根堆为例）
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    int heap[maxn],n;   //heap为堆，n为元素个数
     
    // 调整标号为 low 的元素，high 是堆容量，O(logn)
    void downAdjust(int low,int high){
        int i = low,j = i * 2;
        while(j<=high){
            // 选择两个儿子较大的
            if ((j+1)<high && heap[j]<heap[j+1]){
                    j = j+1;
                }
            // 正式 adjust
            if (heap[j]>heap[i]){
                swap(heap[i],heap[j]);
                i = j;
                j = i * 2;
            }
            else break;
        }
    }
     
    // 建堆：从1到[n/2]是非叶子节点，倒着一个一个调整,O(n)
    void createHeap(){
        for(int i = n/2;i>=1;i--){
            downAdjust(i,n);
        }
    }
     
    //如果要删除堆顶，只需要最后一个元素覆盖堆顶元素，然后dj根结点即可，时间复杂度O(logn)
    void deleteTop(){
        heap[1] = heap[n--];
        downadjust(1,n);
    }
     
    //low 为1，high为要调整的
    void upadjust(int low,int high){
        int i = high,j = i/2;
        while(j>=low){
            if (heap[j]<heap(low)){
                swap(heap[i],heap[j]);
                i = j;
                j = i/2;
            }
            else break;
        }
    }
     
    // 添加元素
    void insert(int x){
        heap[++n] = x;
        upadjust(1,n);
    }
     
  3. 堆排序：倒序遍历，每个都先与堆顶交换，再 dj // A1098
    1
    2
    3
    4
    5
    6
    7
    8
    void heapSort(){
        createHeap();
        for(int i = n;i>0;i--){
            swap(heap[i],heap[1]);
            downAdjust(1,i-1);
        }
    }
     

9.8 哈弗曼树

  1. 定义：最小带权路径长度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    priority_queue<LL,vector<LL>,greater<LL>> pq;
    LL huffman(LL data[],int n){
        LL ans = 0;
        for(int i = 0;i<n;i++){
            pq.push(data[i]);
        }
        while(pq.size()>1){
            LL x = pq.top();pq.pop();
            LL y = pq.top();pq.pop();
            pq.push(x+y);
            ans += (x+y);
        }
        return ans;
    }
     
  2. 哈弗曼编码 略

CH10 图

10.1 定义

顶点，边，有向图，无向图，出度，入度，点权，边权

10.2 存储

  1. 邻接矩阵 只适用于顶点数<1000
  2. 邻接表
    1
    2
    3
    4
    5
    6
    7
    struct Node{
        int v,w;
        Node(int _v,int _w):v(_v),w(_w){}   //构造函数
    }
    vector<Node>adj[N]; //每个点一条链表
    adj[i].push_back(Node(3,4));
     

10.3 遍历

  1. DFS //A1034
    • 连通分量：无向图中，可达；
    • 强连通分量：有向图中，两个方向均可达
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 邻接矩阵
    Graph[maxn][maxn];
    bool vis[n] = {false};
     
    void DFS(int u,int depth){
        vis[u] = true;
        for(int i = 0;i<n;i++){
            if (Graph[u][i]!=INF && vis[v]==false){
                DFS(v,depth+1);
            }
        }
    }
     
    void DFSTravel(){
        for(int i = 0;i<n;i++){
            if (vis[i] == false) DFS(i,1);
        }
    }
     
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //邻接表
    vector<node>adj[maxn];
    bool vis[maxn] = {false};
    int n;
     
    void DFS(int u,int depth){
        vis[u] = true;
        for(int i = 0;i<adj[u].size();i++){
            if (vis[adj[u][i]] == false)
                DFS(adj[u][i],depth+1);
        }
    }
     
    void DFSTravel(){
        for(int i = 0;i<n;i++){
            if (vis[i] == false) DFS(1,i);
        }
    }
     
  2. BFS
    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
    // 邻接矩阵
    Graph[maxn][maxn];
    bool vis[n] = {false};
     
    void DFS(int u){
        vis[u] = true;
        queue<int>q;
        q.push(u);
        while(!q.empty()){
            int top = q.front();
            q.pop();
            for(int i = 0;i<n;i++){
                if (Graph[top][i]!=Inf && vis[i]==false)
                    q.push(i);
                    vis[i] = true;
            }
        }
    }
     
    void DFSTravel(){
        for(int i = 0;i<n;i++){
            if (vis[i] == false) DFS(i);
        }
    }
     
    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
    //邻接表
    vector<node>adj[maxn];
    bool inq[maxn] = {false};
    int n;
     
    void DFS(int u){
        inq[u] = true;
        queue<node>q;
        q.push(node(u,0));      //u号0层
        while(!q.empty()){
            int top = q.front();
            q.pop();
            for(int i = 0;i<adj[top].size();i++){
                if (inq[adj[top][i].v]==false)
                    q.push(node(adj[top][i].v,top.layer++));
                    inq[adj[top][i].v] = true;
            }
        }
    }
     
    void DFSTravel(){
        for(int i = 0;i<n;i++){
            if (inq[i] == false) DFS(i);
        }
    }
     

10.4 最短路径

  1. Dj：单源最小路径，且边权为正
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    //邻接矩阵
    const int INF = 0x3fffffff;
    const int MAXV = 1000;  //最大顶点数
    int n,G[MAXV][MAXV];
    int d[MAXV],pre[MAXV];
    bool vis[MAXV] = {false};
    void Dijkstra(int s){
        fill(d,d+MAXV,INF);
        d[s] = 0;
        for(int i = 0;i<n;i++){pre[i] = i;}
        for(int i = 0;i<n;i++){
            int k = -1,MIN = INF;
            for(int j = 0;j<n;j++){
                if (vis[j]==false && d[j]<MIN){
                    MIN = d[j];
                    k = j;
            }
            if (k == -1)return;
            vis[k] = true;
            for(int j = 0;j<n;j++){
                if (vis[j] == false && G[k][j]!=INF && d[k]+G[k][j]<d[j]){
                    d[j] = d[k]+G[k][j];
                    pre[j] = k;
                }
            }
        }
    }
     
    //邻接表
    const int INF = 0x3fffffff;
    const int MAXV = 1000;  //最大顶点数
    int n;
    struct node{
        int distance,v;
    };
    vector <node>G
    int d[MAXV],pre[MAXV];
    bool vis[MAXV] = {false};
    void Dijkstra(int s){
        fill(d,d+MAXV,INF);
        d[s] = 0;
        for(int i = 0;i<n;i++){pre[i] = i;}
        for(int i = 0;i<n;i++){
            int k = -1,MIN = INF;
            //这个寻找最小d[k]的过程可以用priority_queue改写
            for(int j = 0;j<n;j++){
                if (vis[j]==false && d[j]<MIN){
                    MIN = d[j];
                    k = j;
            }
            if (k == -1)return;
            vis[k] = true;
            for(int j = 0;j<G[k].size();j++){
                if (vis[j] == false && d[k]+G[k][j].dis<d[G[k][j].v]){
                    d[G[k][j].v] = d[k]+G[k][j].dis;
                    pre[G[k][j].v] = k;
                }
            }
        }
    }
     
    //输出最短路径
    void DFS(int s,int v){
        if(v == s){
            printf("%d/n",s);
        }
        DFS(s.pre[v]);
        printf("%d",v);
     
    //有多条最短路径->新增边权(其实点权也是一样滴)
            for(int j = 0;j<n;j++){
                if (vis[j] == false && G[k][j]!=INF){
                    if (d[k]+G[k][j]<d[j]){
                        d[j] = d[k]+G[k][j];
                        c[j] = c[k]+cost[k][j]; //c为边权
                        pre[j] = k;
                    }else if (d[k]+G[k][j]==d[j] && c[j] < c[k]+cost[k][j]){
                        c[j] = c[k]+cost[k][j]
                    }
                }
            }
     
    //有多条最短路径->求最短路径条数:s->j条数num[j]
            int num[n] = 0;num[j] = 1;
            for(int j = 0;j<n;j++){
                if (vis[j] == false && G[k][j]!=INF){
                    if (d[k]+G[k][j]<d[j]){
                        d[j] = d[k]+G[k][j];
                        num[j] = num[k];
                    }else if (d[k]+G[k][j]==d[j]){
                        num[j] += num[k];
                    }
                }
            }
     

// NOTE20 只能0可以简单的初始化，其它的初值需要用 fill 函数

  1. DJ + DFS：先用DJ记下最短路径（只考虑距离 min ），再从中选出第二条标尺最优的：分为两部分，第一部分Dj完全不需要改，第二部分DFS根据题目而定

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    vector<node>adj[maxn];
    vector<int>pre[maxn];
    int pre[maxn],distance[maxn];
    bool visit[maxn] = {false};
     
    void Dj(int start){
        fill(distance,distance+maxn,INF);
        dis[start] = 0;
        for(int ii = 0;ii<n;ii++){
            int MIN = INF,k = -1;
            for(int i = 0;i<n;i++){
                if (distance[i] < MIN && vis[i] == false){
                    MIN = distance[i];
                    k = i;
                }
            }
            if (k == -1)return;vis[k] == true;
            for(int i = 0;i<adj[k].size();i++){
                int v = adj[k][i].v;
                if (dis[v] > dis[k] + adj[k][i].weight){
                    dis[v] = dis[k] + adj[k][i].weight;
                    pre[v].clear();
                    pre[v].push_back(k);
                }
                else if (dis[v] == dis[k] + adj[k][i].weight){
                    pre[v].push_back(k);
                }
            }
        }
    }
     
    int optValue = -1;
    vector<int>tempbest,best;
     
    void DFS(int v){    //v为当前访问结点
        if (v == start){
            //计算条数：
                pathNum++;
            //计算 optValue：
                tempbest.push_back(v);
                if (算出来的tempOptValue > optvalue){赋过去;}
                // 注意这里的 tempbest 是逆序的！
                tempbest.pop_back();
            return;
        }
        tempbest.push_back(v)
        for(int i = 0;i<pre[v].size();i++){
            DFS(pre[v][i]);
        }
        tempbest.pop_back();
    }
     

  2. Bellman-Ford & SPFA

    • BF：单源最短路径问题 略
    • SPFA：略

  3. Floyd：全源最短路径问题：O(n^3)[n<=200]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    const int maxn = 200;
    const int INF = 0x3fffffff;
    int n;                      //顶点数
    int dis[maxn][maxn];
     
    void Floyd(){
        for(int k = 0;k<n;k++){
            for(int i = 0;i<n;i++){
                for(int j = 0;j<n;j++){
                    if (dis[i][k]<INF && dis[k][j]<INF && dis[i][k]+dis[k][j]<dis[i][j])
                    {
                        dis[i][j] = dis[i][k]+dis[k][j];
                    }
                }
            }
        }
    }
     

10.5 最小生成树

  1. Prim：
    • 与 Dj 想法几乎相同，只是 d[i] 表示顶点 i 到已选🌲的最短距离
    • 适用于边多的情况
    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
    int Prim(int s){
        fill(d,d+MAXV,INF);
        d[s] = 0;
        int ans = 0;    //最小生成树的边权之和
        for(int i = 0;i<n;i++){
            int k = -1,MIN = INF;
            //这个寻找最小d[k]的过程可以用priority_queue改写
            for(int j = 0;j<n;j++){
                if (vis[j]==false && d[j]<MIN){
                    MIN = d[j];
                    k = j;
            }
            if (k == -1)return;
            vis[k] = true;
            ans += d[k];
            for(int j = 0;j<G[k].size();j++){
                int v = G[k][j].v；
                // 底下这是关键一句！
                if (vis[j] == false && G[k][j].dis < d[v]){
                    d[v] = G[k][j].dis;
                }
            }
        }
        return ans;
    }
     
  2. Kruskal：
    • 适用于边少的情况
    • 所有边小到大排序，只要不构成环，则加入🌲，直到边数=顶点数-1
    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
    28
    struct edge{
        int u,v,cost;
    }E[maxn];
     
    bool cmp(edge a,edge b){
        return a.cost<b.cost;
    }
     
    int kruscal(int n,int m){    //返回最小边权之和，n顶点个数，m边数
        int ans = 0,edges = 0;
        for(int i = 0;i<n;i++){
            father[i] = i;
        }
        sort(E,E+m,cmp);
        for(int i = 0;i<m;i++){
            int faa = findfather[E[i].v];
            int fab = findfather[E[i].u];
            if (faa != fab){
                father[faa] = fab;
                ans += E[i].cost;
                edges += 1;
            }
            if (edges == n-1)break;
        }
        if (edges < n-1)return -1;
        else return ans;
    }
     

10.6 拓扑排序

步骤：

  1. 定义队列Q，并将所有入度为0的结点加入队列

  2. 取front输出，删去从他出发的所有边，并令这些边到达的顶点入度-1；如果入度减到0，则加入队列；

  3. 反复上一步，直到队列为空。若此时入锅队的节点数恰好为n，则排序成功，是有向无环图

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    bool topologicalSort(){
        int num = 0;
        queue<int>q;
        for(int i = 0;i<n;i++){
            if (inDegree[i] == 0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i = 0;i<G[u].size();i++){
                int v = G[u][i];
                inDegree[v] --;
                if (inDgreaa[v] == 0)q.push(v);
            }
            G[u].clear();
            num++;
        }
        if (num == n)return true;
        else return false;
    }
     

10.7 关键路径

  1. AOV网(点) & AOE网(边)
    • AOE -> AOV：AOV每个顶点拆成两个顶点，中间改成带权重有向边；
  2. 关键路径：有向无环图的最长路径 代码略

Ch11 动态规划

  1. 条件：重叠子问题 + 最优子结构
  2. 递推 Vs 递归：递推-自底向上；递归-自顶向下；
  3. 常见的简单递推关系：
    • 前序和、等差数列、等比数列、裴波那契数列，略；
    • s(n,k) 含有 n 个元素的集合划分为 k 个集合的情况数： s(n,k) = s(n-1,k-1) + k * s(n-1,k);
    • n 本书重新排列，要求排列后每本书不能在原来位置上： \(d_n = (n-1)(d_{n-1}+d_{n-2});d_1 = 0;d_2 = 1;\)
    • 分平面的最大区域数：
      • n 条直线：f(n) = f(n-1) + n;
      • n 条折线：f(n) = f(n-1) + 4*n - 3;
      • n 条封闭曲线（比如圆）：f(n) = f(n-1) + 2*n - 2;
    • 组合数： \(C_n^m = C_{n-1}^m + C_{n-1}^{m-1} \)
    • Catalan 数：
      • 通项：\(h_n = \frac{C^n_{2n}}{n+1}\)
      • 问题：合法的出入栈序列数（n 对括号的正确使用数），n+1 个叶子节点的二叉树的个数，有序树的个数，折线不越过轴的路径数

11.1 最大连续子序列和：

dp[i] = max { A[i], dp[i-1]+A[i] } 得到以 i 结尾的最大子串和 dp[i]，再在 dp[] 中找到最大即可

11.2 最长不下降子序列：

题目：找到最长子序列（可以不连续），使得这个子序列非递减。 dp[i] = max{ 1, dp[j] + 1} (j = 1~i-1 && a[j]<a[i])

11.3 最长公共子序列：

1
2
3
4
dp[i][j] = dp[i-1][j-1] + 1,                (a[i] == b[i])
         = max{ dp[i-1][j], dp[i][j-1]},    (a[i] != b[i])
边界：dp[i][0] == dp[j][0] = 0
 

11.4 最长回文子串：

dp[i][j] 表示 s[i] 到 s[j] 的子串是否为回文子串，是=1，不是=0；

1
2
3
4
5
dp[i][j] = dp[i+1][j-1]                     (s[i] == s[j])
         = 0                                (s[i] != s[j])
边界：dp[i][i] = 1,dp[i][i+1] = (s[i] == s[i+1])?1:0;
递推过程：第 i 轮求长度为 i+2 的 d[][]
 
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
28
29
30
31
32
33
34
#include <cstdio>
#include <cstring>
consst int maxn = 1010;
char S[maxn];
int dp[maxn][maxn];
 
int main(){
    gets(S);
    int len = strlen(S),ans = 1;
    memset(dp, 0, sizeof(dp));
    // 边界条件
    for(int i = 0;i<len;i++){
        dp[i][i] = 1;
        if (i < len - 1){
            if (S[i] == S[i+1]){
                dp[i][i+1] = 1;
                ans = 2;
            }
        }
    }
    // 状态转移方程
    for (int L = 3;L <= len; L++){
        for(int i = 0;i+L-1<len;i++){
            int j = i+L-1;
            if (S[i] == S[j] && dp[i+1][j-1] == 1){
                dp[i][j] = 1;
                ans = L;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}
 

11.5 DAG 最长路 略

11.6 背包问题

  1. 01背包问题 🍔

    问题：n 件物品，每件重量 w[i]，价值 c[i]。背包容量 v，求选法，使背包内价值最大。

    二维数组表示：dp[i][v] = max{ dp[i-1][v], dp[i-1][v-w[i]] + c[i] }

    1
    2
    3
    4
    5
    6
    for (int i = 0;i<n;i++){
        for (int v = w[i];v<V;v++){
            dp[i][v] = max (dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
        }
    }
     

    滚动数组（不懂）：dp[v] = max{ dp[v], dp[v-w[i]]+c[i] }

    1
    2
    3
    4
    5
    6
    7
    // 逆向滚动
    for (int i = 1;i<=n;i++){
        for (int v = V; v >= w[i]; v--){
            dp[v] = max(dp[v], dp[v-w[i]]+c[i]);
        }
    }
     
    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 <cstdio>
    #include <algorithm>
    using namespace std;
    const int maxn = 100;   //物品最大件数
    const int maxv = 1000;  //v的上限
     
    int w[maxn],c[maxn],dp[maxv];
    int main(){
        int n,v;
        scanf("%d %d",&n,&v);
        for (int i = 0;i<n;i++){scanf("%d",&w[i]);}
        for (int i = 0;i<n;i++){scanf("%d",&c[i]);}
        for (int v = 0;v<=V;v++){dp[v] = 0;}        // 边界
        // 如果要恰好装满，初始化应该 dp[0] = 0，其余 = -INF
        for (int i = 1;i<=n;i++){                   // 状态转移
            for (int v = V; v >= w[i]; v--){
                dp[v] = max(dp[v], dp[v-w[i]]+c[i]);
            }
        }
        int max = 0;
        for (int v = 0;v<=V;v++){
            if (dp[v]>max)max = dp[v];
        }    
        printf("%d",max);
        return 0;
    }
     

  2. 完全背包问题 问题：每件物品都有无穷件

    1
    2
    3
    4
    5
    6
    7
    // 正向滚动
    for (int i = 1;i<=n;i++){
        for (int v = w[i]; v <= V; v++){
            dp[v] = max(dp[v], dp[v-w[i]]+c[i]);
        }
    }
     

CH12 字符串

12.1 字符串hash

  1. 字符串hash p = 100000019, MOD = 1000000007: H[i] = (H[i-1]*26 + index(str[i])) % MOD;
  2. 子串hash H[i~j] = (H[j] - H[i-1]*p^(j-1+1) % MOD + MOD) % MOD;

12.2 KMP

问题：字符串匹配

  1. next[]： next[i] 表示使子串 s[0~i] 的前缀等于后缀 s[i-k~i] 的最大的 k，也就是最长相等前缀的最后一位的下标；如果没有，则 next[i] = -1
    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
    28
    29
    30
    31
    32
    33
    void getNext(char s[],int len){
        int j = -1;
        next[0] = -1;
        for(int i = 1;i<len;i++){
            while(j!=1 && s[i] != s[j+1]){
                j = next[j];
            }
            if (s[i] == s[j+i]){
                j++;
            }
            next[i] = j;
        }
    }
     
    int KMP(char text[], char pattern[]){
        int n = strlen(text),m = strlen(pattern);
        getNext(pattern, m);
        int ans = 0,j = -1;
        for(int i = 0;i<n;i++){
            while(j!=1 && text[i] != pattern[j+1]){
                j = next[j];
            }
            if (text[i] == pattern[j+i]){
                j++;
            }
            if (j == m-1){
                ans ++;
                j = next[j];
            }
        }
        return ans;
    }
     

Ch13 拓展

13.1 分块

1
2
3
4
5
6
问题：查询从小到大第 k 个数；
解法：将 n 个数分成 sqrt(n) 块，先找块，再在块里找数，只需 O(sqrt(n))
 
拓展问题：无序数组从小到大第 k 个数；
解法：hash统计每个值的次数 O(n)，
 

13.2 树状数组

  1. lowbit 运算：求能整除 x 的最大2的幂次 lowbit(x) = x & (-x)
  2. 树状数组：覆盖长度为 lowbit(i)，下标必须从1开始；

Ch14 心得与技巧

  1. 简单的时间优化方法：
    • 运算速度：位运算 > 逻辑运算 > 整形运算 > 实型运算；
    • + - * > / %；
    • 调用函数要比直接计算慢；
  2. 空间优化方法：
    • 压缩存储：减小数组大小，降低数组维度
    • 覆盖旧数据：滚动数组
  3. 动态化静态：动态内存分配速度很慢，尽量使用静态大数组
  4. 集合的表示：创建 hash 表 bool [n]，表示 i 号元素是否存在，然后就可以用二进制的位移，按位与或操作。
  5. 初始化问题：min,max 均初始化为数组的第一项
  6. 调试：
    • system("pause"); while(1);
    • 判断某段代码是否运行：写一句能让程序崩溃的代码 a[-100000] = 0;，观察程序是否崩溃
    • 计时：
      1
      2
      3
      4
      double start = clock() / (double)CLOCKS_PER_SEC;
      double end = clock() / (double)CLOCKS_PER_SEC;
      end - start;
       
  7. 书写检查：
    • 勿忘初始化：变量要初始化，指针要初始化为 NULL
    • 复杂表达式一定要有括号
    • 数组编号 0 还是 1 开始？
    • > 还是 >= ？
    • 数组下标一定全部检查一遍，莫越界
    • 对指针 * 运算时，先判断是否指向 NULL，否则程序崩溃

Ch15 考前与考试时

  1. 栈，队列，二叉树，二叉排序树，堆，图 — 熟练背默 快排，归并排序，二分查找，最大公约数，组合数 — 背默
  2. 老太太的裹脚布：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <iostream>
    #include <fstream>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    #include <cstdio>
    #include <vector>
    #include <map>
    #include <queue>
    #include <math.h>
     
  3. 做题时：
    • 通过数据范围估计时间复杂度：
    • 想好算法，动笔之前，想想有没有反例会打破自己的算法？
    • 写完运行之前，先要静态查错！
    • 代码尽量不要复制粘贴，复制粘贴之后仔细检查所有字母！
    • 代码有重大修改，一定备份！
  4. 测试时：
    • 极端数据：边界大小，边界大小±1，0(计算中出现0)，1(循环/迭代只有一个数)
    • 有时即使测试数据对了，也不一定保证题意理解没问题！
    • 测试数据只能用来发现问题，不能用来改正错误
  5. 没思路/骗分时：
    • 分段讨论：针对不同规模的数据写不同的程序
    • 有序化：先把数据顺序调好
    • 暴力输出：-1, Impossible, Failed
  6. 交卷前：
    • 没有调试的 printf
    • return 0;

[mathjax]

1 thought on “PAT 备考笔记”

Leave a Comment

电子邮件地址不会被公开。