PAT 备考笔记

  • 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

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. 传参传指针

2.8 引用

  1. 直接在函数的参数类型后面加 & 即可;
  2. 函数传参:指针的引用;
  3. 常量不可使用引用;

2.9 结构体

  1. 初始化:
  2. 结构体里面不能定义自己本身,但是可以定义自身类型的指针变量:
  3. 访问元素
  4. 初始化

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. 浮点数比较
  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 过不了!

//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 随机数
  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 ) ):对于每个素数,筛去它的所有倍数 欧拉筛法:每个合数只用其最小的一个质因数去筛

// NOTE 11 进制转换模板

5.5 质因子分解

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

// NOTE 12 vector 传参

5.6 大数运算 🍔

  1. 存储:整数高位存数组高位!
  2. 输入:字符串输入,倒序赋值给 bign
  3. 比较大小:先比 len,再从高到低比较
  4. bign + bign:关键步骤 c.d[c.len++] = temp % 10;
  5. bign – bign:先比大小,再大 – 小
  6. int * bign:进位可以是好大的数字!不用严格一位一位的!P174
  7. bign / int:同上
  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. 求解:
  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 中可以有迭代器 + 整数的写法
  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;
  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]
    • 迭代器
  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;数字越小优先级越大
    • 结构体类型
  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 的键值进行插入

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) 给出一个序列在全排列里的下一个全排列
  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. 释放内存空间:
    • mallocfree(p)
    • newdelete(p)
  4. 动态链表
  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. 存储
    • 结点定义
    • 生成新结点
  5. 查找
  6. 插入:插入位置即为查找失败位置 只要是修改了结构,就一定要使用引用
  7. 创建
  8. 完全二叉树的存储:
    • 编号:1号为根结点;x 左子树 2x,右子树 2x+1;
    • 判断根节点:该节点左子节点编号 root * 2 > n;
    • 判断空节点:root > n;

9.2 二叉树的遍历

  1. 遍历模板
  2. 层序遍历
  3. 先/后序遍历+中序遍历 重建二叉树
  4. 二叉树的静态实现 P298 略

9.3 树的遍历

  1. 结构体定义
  2. 新建节点
  3. 先序遍历 相当于 DFS
  4. 层序遍历 相当于 BFS

9.4 二叉查找树(BST)

  1. 定义:lchild < root < rchild
  2. 查找
  3. 插入
  4. 建立
  5. 删除
  6. 性质:中序遍历有序

9.5 平衡二叉树(AVL树)

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

  2. 查找 与二叉树无异

  3. 插入

    树形 判定条件 调整方法
    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);
  4. 建立 //A1066

9.6 并查集 🍔

  1. 合并 & 查找
    • int father[i] // 表示 i 的父亲结点
    • 根结点:结点是自己
  2. 初始化:一开始每个元素都是单独的集合,因此所有 father[i] = i;
  3. 查找:查找结点所属集合的根结点,以判断多个结点是否在同一个集合
  4. 合并:两个集合合并成一个
  5. 路径压缩

9.7 堆

一定是从 1 开始的序列

  1. 大顶堆,小顶堆,用来实现优先队列
  2. 建堆(以大根堆为例)
  3. 堆排序:倒序遍历,每个都先与堆顶交换,再 dj // A1098

9.8 哈弗曼树

  1. 定义:最小带权路径长度
  2. 哈弗曼编码 略

CH10 图

10.1 定义

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

10.2 存储

  1. 邻接矩阵 只适用于顶点数<1000
  2. 邻接表

10.3 遍历

  1. DFS //A1034
    • 连通分量:无向图中,可达;
    • 强连通分量:有向图中,两个方向均可达
  2. BFS

10.4 最短路径

  1. Dj:单源最小路径,且边权为正

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

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

  2. Bellman-Ford & SPFA

    • BF:单源最短路径问题 略
    • SPFA:略
  3. Floyd:全源最短路径问题:O(n^3)[n<=200]

10.5 最小生成树

  1. Prim:
    • 与 Dj 想法几乎相同,只是 d[i] 表示顶点 i 到已选🌲的最短距离
    • 适用于边多的情况
  2. Kruskal:
    • 适用于边少的情况
    • 所有边小到大排序,只要不构成环,则加入🌲,直到边数=顶点数-1

10.6 拓扑排序

步骤:

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

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

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

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 最长公共子序列:

11.4 最长回文子串:

dp[i][j] 表示 s[i]s[j] 的子串是否为回文子串,是=1,不是=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] }

    滚动数组(不懂):dp[v] = max{ dp[v], dp[v-w[i]]+c[i] }

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

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

Ch13 拓展

13.1 分块

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;,观察程序是否崩溃
    • 计时:
  7. 书写检查:
    • 勿忘初始化:变量要初始化,指针要初始化为 NULL
    • 复杂表达式一定要有括号
    • 数组编号 0 还是 1 开始?
    • > 还是 >= ?
    • 数组下标一定全部检查一遍,莫越界
    • 对指针 * 运算时,先判断是否指向 NULL,否则程序崩溃

Ch15 考前与考试时

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

[mathjax]

1 thought on “PAT 备考笔记”

Leave a Comment

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