- 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 多点测试
- 2.1 宏定义
- 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
vsi++
- 条件运算符
A ? B : C
A为真,则执行B,否则执行C - 位运算符
<<
左移>>
右移&
w按位与|
按位或^
按位异或~
按位取反
2.3 顺序结构
-
scanf("%d", &n)
- 除了 char 数组整个输入的情况不加 &,其他所有变量类型都要加 &
int-%d longlong-%lld float-%f double-%lf char-%c char 数组-%s
- 这里
%lld
有时候会报错,改成%l64d
试试 -
scanf ("%c")
可以读入空格与换行;其它以空格%换行为结束标志 -
scanf ("%*c")
用来跳过行尾的换行符
-
printf("%d", n)
无需 &int-%d longlong-%lld float-%f double-%f char-%c char 数组-%s
- double 精度比 float 高!两个小数相乘,用 double;
- 输入输出格式 🍔
-
%3d
不足3位的 int 右对齐输出,高位用空格补齐,超过3位保持原样; -
%-3d
不足3位的 int 左对齐输出,高位用空格补齐,超过3位保持原样; -
%03d
不足3位的 int 右对齐输出,高位用0补齐,超过3位保持原样; -
%.5f
保留5位输出,超过部分四舍五入,否则0补齐; -
%+d
无论正数负数,都要把符号输出;
-
-
a = getchar()
putchar(b)
输入输出单个字符- 若只是
getchar()
则输入的字符被接受,但是没有被存储; -
getchar()
可以识别空格&换行符
- 若只是
- 格式化流输入输出:
#include <iomanip>
-
cout.width(n);cout.fill(' ');cout<<a;
右对齐,长度为 n,不足部分空格补齐(每次输出前都要调用) -
cout<<oct<<a;
八进制;cout<<hex<<a;
十六进制;
-
- 在流输入输出前加一句
ios::sync_with_stdio(false);
可和scanf,printf
一样快; - 常用 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 选择
-
if
如果表达式是n!=0
,则可省略为if(n)
;n==0
,则可省略为if(!n)
- switch
123456789switch(a+b){case const int:do sth;break;default:do sth;}
2.5 数组
- 初始化:
int a[10] = {};
全部置零(只能置零) - 如果数组大小较大(~10^6级别),需要将其定义在 main 函数之外(系统栈空间不足)
-
memset(数组名,值,sizeof(数组名))
为数组整体赋值,只可以是-1或0!需要string.h头文件;fill(start,end,value)
可以是任意值; - 字符数组只在初始化的时候可以赋值字符串;
- 字符数组结尾
\0
,故数组大小至少为长度+1; - 字符数组输入输出:
-
scanf()
printf()
无需&,空格或换行作为结尾; -
getchar()
putchar()
-
gets()
输入一行;scanf 完一个整数之后,需要先 getchar 接收\n
,再 gets;puts()
输出一行;将一维数组输出后再输出一个\n
;
-
- 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 得索引; -
sscanf(str1,"%d", &n)
从 str1 输入到变量中(→);支持正则表达式 #TODOsprintf(str1,"%d", &n)
把 n 以 %d 格式写到 str 1 字符数组中(←);
2.6 函数
参数是数组时,数组的第一维不需要填写长度;调用时只用写数组名;数组为传引用;
2.7 指针
-
&
取址,得到unsigned
类型整数; - 在数据类型后面加
*
表示指针变量:int* p1, *p2, *p3;
int *p = &a;
其中 p 是地址,*p 是地址中存放的元素; 基类型必须和指针变量存储的地址类型相同; - 指针变量加减法:地址距离(差了几个该类型的值,而非字节数),下一个上一个;
- 数组:
a == &a[0]; *(a+i) == &a[i];
scanf("%d",a+i)
for(int *p=a;p<a+10;p++) printf("%d ",*p);
- 传参传指针
123456void swap(int *a, int *b){int temp = *a;*a = *b;*b = temp;}
2.8 引用
- 直接在函数的参数类型后面加 & 即可;
- 函数传参:指针的引用;
123456void swap(int* &a, int* &b){int* temp = a;a = b;b = temp;}
- 常量不可使用引用;
2.9 结构体
- 初始化:
12345678struct student{char id;char gender;char name[20];}Alice,Bob,stu[100]; // AB代表两个结构体变量,stu代表很多学生的数组studentinfo Alice; // 和上面等价
- 结构体里面不能定义自己本身,但是可以定义自身类型的指针变量:
12345struct node{node n; // 不可以node* next; // 可以};
- 访问元素
12345678910struct student{char id;char gender;char name[20];}stu,*p;stu.id;(*p).id;p->id;
- 初始化
1234567891011struct 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
-
getline
两者不可混淆!-
cin.getline(str1,100);
把一整行读入 char 型数组 str1[100]; -
getline(cin,str);
string 容器 # TODO
-
cout<<setiosflags(ios::fixed)<<setprecision(2)<<123.456<<endl;
- 浮点数比较
1234567const 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)) // 小于等于
- 计算结果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
引子:将输入的数字作为数组下标使用
- hash表:
h = key % mod;
// mod = tsize = 素数 - 线性探查法,平方探查法,链地址法
-
(x,y)
:x * range + y;
- 字符:A-Z = 0-25;后面的数字可以 26-35,若是固定格式,也可直接数字使用
//NOTE8 取char长度,要 #include <cstring>
//NOTE9 所有东西的初始化不能忘!
4.3 递归
4.4 贪心
当前状态局部最优,使全局最优
4.5 二分 🍔
-
mid = (left + right)/2;
可能会溢出,改用mid = left + (right - left)/2;
- 二分模板 P129
- 最后一个满足条件 A <=> 第一个满足 !A
- 二分幂:b 奇数 \(a^b = a * a^b\);b 偶数 \(a^b = a^{(b/2)} * a^{(b/2)}\) 进阶:b二进制表示,a计算相乘
-
if (b%2 == 1)
可以写成if (b & 1)
速度更快 - 大于 num 的第一个值
upper_bound (v.begin(), v.end(), num, cmp)
大于等于 num 的第一个值lower_bound (v.begin(), v.end(), num, cmp)
均是返回指针或迭代器
4.6 two pointers
- 两个指针有制约关系,使得 O(\(n^2\)) 变为 O(n)。如两边同时向中间走,如序列合并。
- 归并排序 递归 / 循环方式 //B1035/A1089
- 快速排序
- cpp 随机数
1234567891011#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;}
- 随机快排:随机选择主元,而非起始作为主元 //NOTE 10 数组去重
4.7 打表
- 在程序中一次性计算出所有需要用到的结果,之后直接查询
- 在程序 B 算出来,然后直接把结果写在 A 中,A 就可以直接用了……
- 对于不会做的,先暴力小范围算,找到结果的规律
4.8 活用递推
找深层次规律,而非简单模拟
4.9 随机选择算法
- 原理:找出序列中第 M 大的数字:类似随机快排,比较当前主元序号与 M 大小关系,二分下去递归即可
- 一个集合拆成两个,在两集合个数差最小时,求两集合s元素和只差的最大值:随机选择,找到第 n/2 大的数,左右即为分开的集合
CH5 数学问题
5.1 简单数学
- 给出的数字的范围作为边界,一定要进行测试
5.2 最大公约 & 最小公倍数 🍔
- 最大公约数 d:辗转相除法
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
- 最小公倍数:
a/d*b
(防止溢出)
5.3 分数
- 表示:
struct Fraction{int up,down;//分子分母};
- 使分母 down 为非负数,分子可正可负
- 分数为零,则分子 = 0,分母 = 1
- 分子与分母互质
- 化简:上述每条规则一个if
- 运算:分子分母分别运算,最后化简;若除数分子为零,输出错误;分子分母使用
long long
存储。 - 输出
- 先化简
- 分母为1,则不输出分母
- 假分数,则带分数形式输出
- 以上均不满足,直接输出
5.4 素数
- 判断素数:不能被
1 ~ (int)sqrt(1.0*n)
整除(#include <math.h>
) - 素数表获取:
Eratosthenes 筛法 O( n * log ( logn ) ):对于每个素数,筛去它的所有倍数
欧拉筛法:每个合数只用其最小的一个质因数去筛
1234567891011121314151617181920const 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 质因子分解
- 结构体 factor 存因子与其个数。fac 数组大小开到
fac[10]
即足够 int 范围 - 枚举
1 ~ sqrt(n)
范围的所有质数,判断是否为质因子,是,则不断除计算个数 - 若最后 n > 1,则将其加入 fac 数组
// NOTE 12 vector 传参
5.6 大数运算 🍔
- 存储:整数高位存数组高位!
123456789struct bign {int d[1000];int len;bign(){ //构造函数memset(d,0,sizeof(d));len = 0;}};
- 输入:字符串输入,倒序赋值给 bign
- 比较大小:先比 len,再从高到低比较
- bign + bign:关键步骤
c.d[c.len++] = temp % 10;
1234567891011121314bign 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;} - bign – bign:先比大小,再大 – 小
123456789101112131415bign 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;}
- int * bign:进位可以是好大的数字!不用严格一位一位的!P174
123456789101112131415bign 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;}
- bign / int:同上
1234567891011121314151617bign 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;}
- 拓展的高精度算法:10000进制
5.7 扩展欧几里得算法
- 问题:
a * x + b * y = c
的解 - 有解条件:
c mod gcd(a,b) == 0
- 转化:a = \(\frac{a}{gcd(a,b)}\);b = \(\frac{b}{gcd(a,b)}\);c = \(\frac{c}{gcd(a,b)}\)
- 求解:
12345678910void exgcd(int a,int b,int c,int &x,int &y){if (a == 0){x = 0;y = c/b;}else{ // 不懂 # TODOexgcd(b%a,a,c,x,y);y = x;x = (c-b*y)/a;}}
- 构造通解:\(x_0\) 和 \(y_0\) 为一组解,则通解为 $$ \begin{cases} x =& c * x_0 + c * b * k\ y =& c * y_0 – c * a * k \end{cases} $$
5.8 组合数
- n! 中有 \( \frac{n}{p} + \frac{n}{p^2} + \frac{n}{p^3} + … \) 个质因子p
- 组合数计算: \(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 通用操作
- 迭代器
v.begin() v.end()
-
v.rbegin() v.rend()
逆向迭代器
6.1 vector 动态数组
vector< vector<int> > name;
- vector 数组
vector<int> vi[100];
- 二维 vector:
vector<vector<int> > b(m, vector<int>(n));
- 元素访问
- 下标
vi[0]
- 迭代器 只在 vector 和 string 中可以有迭代器 + 整数的写法
123vector <typename>::iterator it = vi.begin();printf("%d",*(it+3));
- 下标
- 常用函数
-
push_back(x)
在最后添加元素 -
pop_back()
删除尾元素 -
size()
clear()
-
insert(it,x)
在 it 位置插入 x 元素 -
erase(it)
删除 it 处的元素 -
erase(first,last)
删除 first ~ last 的元素
-
- 用途:
- 存储个数不确定的 数组
- 有时要输出不确定个数个数据在同一行,可用 vector 先存起来
- 用邻接表存储图
// NOTE 13 vector 数组
6.2 set 集合
- 内部自动有序,不含重复元素
#include <set>
- 定义
set<typename> name;
默认升序- 降序
set< int, greater<int> > s;
- 降序
- 元素访问:只能通过迭代器
set<typename>::iterator it;
1234for(set<int>::iterator it = st.begin; it!=st.end; it++){printf("%d",*it);} - 常用函数
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();
- 用途
- 自动去重并按升序排列
// NOTE14 set 判断元素是否存在 b.find(*it)!=b.end()
// NOTE15 printf 打印%
6.3 String 字符串
#include <string>;
- 定义
string str = "abcd";
- 输入:
-
cin>>str;
忽略空格、回车、TAB 等,遇到空格停止 -
getline(cin,str,'\n')
遇到 ‘\n’ 终止输入
-
- printf 输出 string:
printf("%s",str.c_str());
- iterator:同vector
- 常用函数
-
+
这里的两个操作数至少有一个是 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 映射
- 可以将任何基本类型映射到任何基本类型(基本类型包括 STL 容器) map 键值是唯一的,如果一个键多个值,需要 multimap。
- 定义
map<typename1,typename2> mp;
// 前 key,后 value 若是字符串→int,必须使用 string 而非 char 数组 - 访问:map 内部会按照键从小到大的顺序排列
- 下标访问
map<char,int> mp; mp[key]
- 迭代器
1234for(map<char,int>::iterator it = mp.begin();it!=mp.end();it++){printf("%c %d",it->first,it->second);} // it->first 键;it->second 值
- 下标访问
- 函数
it = mp.find(key)
-
mp.erase(it);
mp.erase(key);
mp.erase(firstit,lastit);
-
mp.size()
mp.clear();
-
mp.count(10);
返回 mp 中值为10的元素个数
- 用途
- 字符串与整数之间的映射
- 判断大整数或其他数据类型是否存在
// NOTE 16 scanf 接收换行符 // NOTE 17 STL string 大小写转换 // NOTE 18 map 按照 value 排序:
6.5 Queue 队列
-
#include <queue>;
queue<typename>name;
- 函数
-
q.push(元素);
q.pop();
// 出队,无返回 -
q.front()
// 队头q.back()
// 队尾 -
q.empty()
// 判断k是否空,true为空 q.size()
-
- 用途:
- 实现广度优先搜索时 # TODO
- 使用
q.front()
q.back()
前,一定先q.empty()
判断
6.6 Priority_queue 优先队列
- 队首元素一定是优先级最高的
-
#include <queue>;
priority_queue<typename>name;
- 函数
-
q.top()
只能访问队顶元素 -
q.push(元素)
q.pop();
q.empty()
q.size()
-
- 优先级设置
- 基本数据类型 ( int, double, char ):
ps:
map multimap set multiset
均可用此种方式进行内部排序 下面的>>
中间必须有空格!否则编译失败!priority_queue<typename1, vector<typename1>, less<int> > q;
数字越大优先级越大priority_queue<typename1, vector<typename1>, greater<int> > q;
数字越小优先级越大 - 结构体类型
12345678910struct fruit{string name;int price;friend bool operator < (const &fruit f1,const &fruit f2){// 引用没有也可,有效率高retutn f1.price < f2.price;// 这里与sort函数的顺序是相反的!}}priority_queue<fruit> pq;1234567struct cmp{bool operator () (const &fruit f1,const &fruit f2){retutn f1.price < f2.price;}}priority_queue<fruit, vector<fruit>, cmp> q;
- 基本数据类型 ( int, double, char ):
ps:
- 用途
- 贪心问题,Dj 算法的优化 # TODO
-
top()
之前,先要empty()
判断
6.7 stack 栈
-
#include <stack>;
stack<typename> name;
- 函数
-
st.top()
只能访问栈顶元素 -
st.push(元素);
st.pop();
st.empty();
st.size()
- 清空:
while(!st.empty()){st,pop();}
(其实新建一个栈更快)
-
- 用途
- 模拟实现递归
6.8 pair
-
#include <utility>;
或#include <map>;
-
pair<typename1,typename2> name;
pair<string,int> p("haha",5);
make_pair("haha",5);
- 函数
- 元素访问
p.first
p.last
- 比较大小:直接使用符号比较。先以 first 大小为标准,first 相等时才判别 second 大小
- 元素访问
- 用途
- 代替二元结构体及其构造函数
- 作为 map 的键值进行插入
123map<string,int>mp;mp.insert(make_pair("haha",5));
6.9 algorithm
-
max()
min()
abs(整数)
- 若想比较三个:
max(x,max(y,z))
- 浮点型绝对值:math 头文件下的
fabs()
- 若想比较三个:
-
swap(x,y)
交换 xy 值 reverse(it1,it2)
-
next_permutation(pos1,pos2)
给出一个序列在全排列里的下一个全排列123456789int 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,否则第一个不输出 -
fill(pos1,pos2,value)
把数组/容器某一段赋为相同的值 类似地,memset(it,int value,n)
将从 it 开始的前 n 个字节赋为相同的值(来自 string.h 头文件) sort(it1,it2,cmp(选填))
// NOTE 19 cmp 写法
CH7 数据结构
7.1 栈
- 后进先出
- 栈顶指针 TOP 栈空时
TOP = -1
7.2 队列
7.3 链表
struct node {typename data; node* next;};
- 为新节点分配内存空间:
-
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];
-
- 释放内存空间:
-
malloc
:free(p)
-
new
:delete(p)
-
- 动态链表
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#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;}}
- 静态链表 node 用 hash 实现
- 答题模板:
- 定义链表
- 初始化链表,将特征值置为最小的数或
false
- 从首地址开始遍历,同时对性质进行统计
- 静态链表,下标不连续:按性质排序 // 一定注意,题目给出的可能有无效节点
CH8 搜索
8.1 DFS 深度优先搜索
- 从 n 个数之中选 k 个,和为 x,的所有方案
8.2 BFS 广度优先搜索
// STL 的 queue ,无法修改已入队的元素,因此最好将序号入队,而非整个元素入队。
CH9 🌲
9.1 二叉树
- 空树,层次,度,深度,高度,森林
- n 个结点的🌲,边数一定是 n-1;
(连通 && (边数-顶点数 == 1)) == 树
- 满二叉树,完全二叉树
- 存储
- 结点定义
1234567struct node{typename data;int layer; // 用于层序遍历node *lchild;node *rchild;};
- 生成新结点
1234567node* newNode(int v){node *Node = new node;node->data = v;node->lchild = node->rchild = NULL;return Node;}
- 结点定义
- 查找
1234567void 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);}
- 插入:插入位置即为查找失败位置
只要是修改了结构,就一定要使用引用
123456void insert(node* &root,int x){if (root == NULL){root = newNode(x);return;}if (要插在左边){insert(root->lchild,x);}else {insert(root->rchild,x);}
- 创建
12345678node* Create(int data[],int n){node* root = NULL;for(int i = 0;i<n;i++){insert(root,data[i]);}return root;}
- 完全二叉树的存储:
- 编号:1号为根结点;x 左子树 2x,右子树 2x+1;
- 判断根节点:该节点左子节点编号 root * 2 > n;
- 判断空节点:root > n;
9.2 二叉树的遍历
- 遍历模板
123456789void 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); //后序}
- 层序遍历
12345678910111213141516171819void 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);}}}
- 先/后序遍历+中序遍历 重建二叉树
123456789101112131415node* 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;}
- 二叉树的静态实现 P298 略
9.3 树的遍历
- 结构体定义
12345struct node{int data,layer;vector<int> child; //存放子节点下标}Node [maxn]; //maxn为结点上限个数
- 新建节点
1234567int index = 0;int newNode(int v){Node[index].data = v;Node[index].child.clear();return index++;}
- 先序遍历 相当于 DFS
1234567void PreOrder(int root){printf("%d",Node[root].data);for(int i = 0;i<Node[root].child.size();i++){PreOrder(Node[root].child[i]);}}
- 层序遍历 相当于 BFS
1234567891011121314void 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)
- 定义:
lchild < root < rchild
- 查找
123456789void search(node *root,int x){if (root == NULL) return; // 查找失败if (root->data = x) do dth. // 查找成功else if (root->data < x)search(root->rchild,x);elsesearch(root->lchild,x);}
- 插入
1234567891011void 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);elseinsert(root->lchild,x);}
- 建立
12345678node create(int data[],int n){node *root = NULL;for(int i = 0;i<n;i++){insert(root,data[i]);}return root;}
- 删除
123456789101112131415161718192021222324252627282930313233343536node* 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);}
- 性质:中序遍历有序
9.5 平衡二叉树(AVL树)
-
定义:左右子树高度之差绝对值 <= 1
1234567891011121314151617181920212223242526272829struct 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;} -
查找 与二叉树无异
-
插入
1234567891011121314151617181920//左旋void L(node* &root){node* temp = root->rchild;root->rchild = temp->lchild;temp->lchild = root;updateHeight(root);updateHeight(temp);root = temp;}//右旋:交换lrvoid 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); 12345678910111213141516171819202122232425262728293031323334void 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);}}}} -
建立 //A1066
12345678node* create(int data[],int n){node* root = NULL;for(int i = 0;i<n;i++){insert(root,data[i]);}return root;}
9.6 并查集 🍔
- 合并 & 查找
-
int father[i]
// 表示 i 的父亲结点 - 根结点:结点是自己
-
- 初始化:一开始每个元素都是单独的集合,因此所有
father[i] = i;
- 查找:查找结点所属集合的根结点,以判断多个结点是否在同一个集合
1234567int findFather(int x){while(x != Father[x]){x = Father[x];}return x;}
- 合并:两个集合合并成一个
1234567void Union(int a,int b){ // 小写 union 是关键字int faA = findFather(a);int faB = findFather(b);if (faA != faB) //ab在同一集合不合并,保证同一集合不产生环,即并查集每个集合都是一棵树father[faA] = faB;}
- 路径压缩
1234567891011121314int 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 开始的序列
- 大顶堆,小顶堆,用来实现优先队列
- 建堆(以大根堆为例)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152int 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;}// 正式 adjustif (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);}
- 堆排序:倒序遍历,每个都先与堆顶交换,再 dj // A1098
12345678void heapSort(){createHeap();for(int i = n;i>0;i--){swap(heap[i],heap[1]);downAdjust(1,i-1);}}
9.8 哈弗曼树
- 定义:最小带权路径长度
123456789101112131415priority_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;}
- 哈弗曼编码 略
CH10 图
10.1 定义
顶点,边,有向图,无向图,出度,入度,点权,边权
10.2 存储
- 邻接矩阵 只适用于顶点数<1000
- 邻接表
1234567struct 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 遍历
- DFS //A1034
- 连通分量:无向图中,可达;
- 强连通分量:有向图中,两个方向均可达
12345678910111213141516171819// 邻接矩阵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);}}12345678910111213141516171819//邻接表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);}} - BFS
12345678910111213141516171819202122232425// 邻接矩阵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);}}1234567891011121314151617181920212223242526//邻接表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 最短路径
- Dj:单源最小路径,且边权为正
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495//邻接矩阵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>Gint 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 函数
-
DJ + DFS:先用DJ记下最短路径(只考虑距离 min ),再从中选出第二条标尺最优的:分为两部分,第一部分Dj完全不需要改,第二部分DFS根据题目而定
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152vector<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();} -
Bellman-Ford & SPFA
- BF:单源最短路径问题 略
- SPFA:略
-
Floyd:全源最短路径问题:O(n^3)[n<=200]
123456789101112131415161718const 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 最小生成树
- Prim:
- 与 Dj 想法几乎相同,只是 d[i] 表示顶点 i 到已选🌲的最短距离
- 适用于边多的情况
1234567891011121314151617181920212223242526int 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;} - Kruskal:
- 适用于边少的情况
- 所有边小到大排序,只要不构成环,则加入🌲,直到边数=顶点数-1
12345678910111213141516171819202122232425262728struct 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 拓扑排序
步骤:
-
定义队列Q,并将所有入度为0的结点加入队列
-
取front输出,删去从他出发的所有边,并令这些边到达的顶点入度-1;如果入度减到0,则加入队列;
-
反复上一步,直到队列为空。若此时入锅队的节点数恰好为n,则排序成功,是有向无环图
1234567891011121314151617181920212223bool 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 关键路径
- AOV网(点) & AOE网(边)
- AOE -> AOV:AOV每个顶点拆成两个顶点,中间改成带权重有向边;
- 关键路径:有向无环图的最长路径 代码略
Ch11 动态规划
- 条件:重叠子问题 + 最优子结构
- 递推 Vs 递归:递推-自底向上;递归-自顶向下;
- 常见的简单递推关系:
- 前序和、等差数列、等比数列、裴波那契数列,略;
- 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;
- n 条直线:
- 组合数: \(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 背包问题
-
01背包问题 🍔
问题:n 件物品,每件重量 w[i],价值 c[i]。背包容量 v,求选法,使背包内价值最大。
二维数组表示:
dp[i][v] = max{ dp[i-1][v], dp[i-1][v-w[i]] + c[i] }
123456for (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] }
1234567// 逆向滚动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]);}}123456789101112131415161718192021222324252627#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,其余 = -INFfor (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;} -
完全背包问题 问题:每件物品都有无穷件
1234567// 正向滚动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
- 字符串hash
p = 100000019, MOD = 1000000007:
H[i] = (H[i-1]*26 + index(str[i])) % MOD;
- 子串hash
H[i~j] = (H[j] - H[i-1]*p^(j-1+1) % MOD + MOD) % MOD;
12.2 KMP
问题:字符串匹配
-
next[]
:next[i]
表示使子串s[0~i]
的前缀等于后缀s[i-k~i]
的最大的 k,也就是最长相等前缀的最后一位的下标;如果没有,则next[i] = -1
123456789101112131415161718192021222324252627282930313233void 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 树状数组
- lowbit 运算:求能整除 x 的最大2的幂次
lowbit(x) = x & (-x)
- 树状数组:覆盖长度为
lowbit(i)
,下标必须从1开始;
Ch14 心得与技巧
- 简单的时间优化方法:
- 运算速度:位运算 > 逻辑运算 > 整形运算 > 实型运算;
-
+ - *
>/ %
; - 调用函数要比直接计算慢;
- 空间优化方法:
- 压缩存储:减小数组大小,降低数组维度
- 覆盖旧数据:滚动数组
- 动态化静态:动态内存分配速度很慢,尽量使用静态大数组
- 集合的表示:创建 hash 表
bool [n]
,表示 i 号元素是否存在,然后就可以用二进制的位移,按位与或操作。 - 初始化问题:min,max 均初始化为数组的第一项
- 调试:
system("pause"); while(1);
- 判断某段代码是否运行:写一句能让程序崩溃的代码
a[-100000] = 0;
,观察程序是否崩溃 - 计时:
1234double start = clock() / (double)CLOCKS_PER_SEC;double end = clock() / (double)CLOCKS_PER_SEC;end - start;
- 书写检查:
- 勿忘初始化:变量要初始化,指针要初始化为
NULL
- 复杂表达式一定要有括号
- 数组编号 0 还是 1 开始?
- > 还是 >= ?
- 数组下标一定全部检查一遍,莫越界
- 对指针
*
运算时,先判断是否指向NULL
,否则程序崩溃
- 勿忘初始化:变量要初始化,指针要初始化为
Ch15 考前与考试时
- 栈,队列,二叉树,二叉排序树,堆,图 — 熟练背默 快排,归并排序,二分查找,最大公约数,组合数 — 背默
- 老太太的裹脚布:
1234567891011#include <iostream>#include <fstream>#include <cstring>#include <algorithm>#include <cstdlib>#include <cstdio>#include <vector>#include <map>#include <queue>#include <math.h>
- 做题时:
- 通过数据范围估计时间复杂度:
- 想好算法,动笔之前,想想有没有反例会打破自己的算法?
- 写完运行之前,先要静态查错!
- 代码尽量不要复制粘贴,复制粘贴之后仔细检查所有字母!
- 代码有重大修改,一定备份!
- 测试时:
- 极端数据:边界大小,边界大小±1,0(计算中出现0),1(循环/迭代只有一个数)
- 有时即使测试数据对了,也不一定保证题意理解没问题!
- 测试数据只能用来发现问题,不能用来改正错误
- 没思路/骗分时:
- 分段讨论:针对不同规模的数据写不同的程序
- 有序化:先把数据顺序调好
- 暴力输出:-1, Impossible, Failed
- 交卷前:
- 没有调试的
printf
return 0;
- 没有调试的
[mathjax]
Спасибо