国庆NOIP储备营讲课笔记
Day1（基础算法）
讲师：余快
枚举法
例题1
给定一个数 \(x\)，判断 \(x\) 是不是质数。
朴素算法：枚举 \([2,x?1]\) 之间所有的整数 \(i\)，逐个判断 \(x\) 是否被 \(i\) 整除，若都不能整除则 \(x\) 是质数，时间复杂度 \(O(x)\)，搞个 \(10^9\) 直接卡过。该怎么优化呢？
优化枚举范围：只需枚举到 \(\sqrt{x}\) 即可
例题2
简要思路
for 循环 + check 判断。
首先枚举计算所有的数所需要的火柴数量（设立数组 \(g\)，\(g_i\) 代表 i 这个数所需要的火柴数）。
再次，枚举所有在等式中可能出现的数（即 \([0,2000]\)），设立数组 \(a\) 来表示。
注意到火柴数最多为 \(24\) 根，去掉加号和等号的 \(4\) 根火柴，所以我们最多只能使用 \(20\) 根火柴。因此，我们不难推出：最大的等式大约是 \(1111 + 1111 = 2222\)，所以我们只需要枚举每一个加数，其范围为 \([0,1111]\)，再利用两个加数推出和，最后 check 判断一下火柴数是否符合条件即可。
例题3
暴力枚举（\(0\text {pts}\)）：
枚举区间的左端点，右端点，然后从左端点开始到右端点逐个加起来。
时间复杂度 \(O(n^3)\)
前缀和优化的朴素算法（\(40\text {pts}\)）：
先处理 \(s_i=a_1+a_2+ \dots +a_i\)
枚举区间的左端点 \(i\)，右端点 \(j\)，这段区间的和就是\(s_j ? s_{i?1}\)
时间复杂度 \(O(n^2)\)
优化枚举范围（\(100\text {pts}\)）：
如果我们固定右端点 \(i\) ，那么我们选择的左端点 \(j\) 一定满足 \(s_{j ?1}\) 最小，这样的 \(s_i?s_{j?1}\) 是最大的。
于是我们从左到右枚举右端点 \(i\)，维护 \([1,i]\) 里满足 \(s_{j?1}\) 最小的 \(j\)，然后直接选择 \(j\) 作为左端点。
时间复杂度 \(O(n)\) 。
悄悄说一下，其实这道题正解是 dp。
例题4
区间伸缩/尺取法：枚举区间左端点，不断往后选取数字直到出现所有 m 个画家为止。
左端点右移过程中，合法区间的右端点也一定在右移，所以右端点可以在上一次结果的基础上拓展，而不是重新由新的左端点开始枚举。
代码：太难了，不想写
模拟算法
模拟就是用计算机来模拟题目中要求的操作。
模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。
例题1
P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布
直接按题意模拟即可
例题2
中模拟，样例字符串到后面原形毕露，直接不装了/cf
技巧
写模拟题时，遵循以下的建议有可能会提升做题速度：
在动手写代码之前，在草纸上尽可能地写好要实现的流程。
在代码中，尽量把每个部分模块化，写成函数、结构体或类。
对于一些可能重复用到的概念，可以统一转化，方便处理。
调试时分块调试。模块化的好处就是可以方便的单独调某一部分。
写代码的时候一定要思路清晰，不要想到什么写什么，要按照落在纸上的步骤写。
实际上，上述步骤在解决其它类型的题目时也是很有帮助的。
习题
P1042 [NOIP2003 普及组] 乒乓球
P2670 [NOIP2015 普及组] 扫雷游戏
P3952 [NOIP2017 提高组] 时间复杂度
二分法
定义
二分的定义：在一个单调的有限数列上快速查找某一特定值的方法。
例题1
给你一个单调递增的数组，给你一个数x，问 $ > x, \ge x$的第一个数分别是什么？
可以用 STL 中的 lower_bound 和 upper_bound 轻松解决，不过在这里不讲。
事实上有不同二分的实现方法，刚刚接触二分的OIer经常在这个地方写错，进入死循环
//找第一个>q
int l=1,r=n;
while(l<r){
int mid=(l+r)>>1;
if (a[mid]<=q)l=mid+1;
else r=mid;
}
std::cout<<r;
//找第一个>=q
int l=1,r=n;
while(l<r){
int mid=(l+r)>>1;
if (a[mid]>=q)r=mid;
else l=mid+1;
}
std::cout<<r;
其实我们有最保守的写法
就是l=mid+1;r=mid-1
而答案直接考虑mid
例题2
求一个正整数X开三次根后的结果，保留六位小数。
因为我们这里要二分实数，所以 while 循环的终止条件是：r-l <= eps，其中 \(eps = 10^{-6}\) 。
解法1：
~~直接输出 \(x^{\frac{1}{3}}\) 可以用 ```pow``` 来实现。
解法2
假设我们不知道 pow 函数，只知道二分和 sqrt 函数，可以朴素的二分查找。
代码：调挂了，有空再写。
分治
快速幂
CSP-S2023第一轮 著名题目：
现在用如下程序来计算x^n，其时间复杂度为（ ）。
Quick_power(x,k):
if k==1 return x;
else return Quick_power(x,k/2)*Quick_power(x,k/2)*(k&1)?x:1;
A.O(n)
B.O(1)
C.O(log n)
D.O(n log n)
答案选A
详细讲解见 Day6 数论一节
归并排序
基础分治题目，不多赘述。
逆序对
在算法领域中可以用归并排序实现，还可以用数据结构中的树状数组。
对拍
:loop
make
100fen!
baoli
fc baoli.out a.out
if errorlevel==1 pause
goto loop
make为造数据的可执行文件
100fen! 为正解的可执行文件
baoli 为自己代码的可执行文件
fc用来比较他们的输出文件，如果不同则停止。
贪心
例题1
我们把每个小矮人按照腿长与臂长的和来排序，然后用 dp (01背包)来选择小矮人。
边界 \(f_0 = \sum _{i = 1} ^ n a_i\)
目标 \(f_i \ge 0\) 成立时，\(i\) 的最大值。
转移方程：\(f_j \rightarrow \max(f_j,f_{j - 1} - a_i) [f_{j - 1} + b_i \ge h]\)。
Day2上午 搜索
dfs深度优先搜索
例题1
#include<bits/stdc++.h>
#define int long long
int ans = 0;
int a[105];
bool vis[105];
int n, m;
int dfs(int now) {
if(now == n + 1){
int sum = 1;
for(int i = 1; i <= n; i++)
if(!vis[i])sum *= a[i];
return sum >= m;
}
vis[now] = true;
ans += dfs(now + 1);
vis[now] = false;
ans += dfs(now + 1);
return 0;
}
signed main(){
std::cin >> n >> m;
for (int i = 1; i <= n; i++) std::cin >> a[i];
dfs(1);
std::cout << ans;
return 0;
}
非常基础的爆搜，本人因开返回值为 int 的函数但忘记返回（本机测试不出来）而爆零，警钟长鸣。
或者用一个指数级别的 for 循环来解决，借助位运算状压，即可通过。
#include <iostream>
#define int long long
int a[15];
int ans = 0;
signed main() {
int n, m;;
std::cin >> n >>m;
for (int i = 1; i <= n; i++) std::cin >> a[i];
for (int i = 0; i < (1 << n); i++) {
int mul = 1;
for (int j = 1; j <= n; j++) {
if(i & (1 << (j - 1))) mul *= a[j];
}
if (mul >= m) ans++;
}
std::cout << ans;
return 0;
}
例题2
算法1 爆搜（55分）
#include<bits/stdc++.h>
int ans = -1;
int n;
int a[1005][1005];
void dfs(int sum, int x, int y) {
if (x == n + 1) {
ans = std::max(ans, sum);
return;
}
dfs(sum + a[x][y], x + 1, y);
dfs(sum + a[x][y], x + 1, y + 1);
}
signed main(){
std::cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
std::cin >> a[i][j];
dfs(0, 1, 1); //O(2^n)
std::cout << ans;
return 0;
}
算法2 记忆化搜索
#include<bits/stdc++.h>
int n;
int a[1005][1005];
bool vis[1005][1005];
int f[1005][1005];
int dfs(int x, int y) {
//返回值表示从 x, y 走到下面能获得的最大的和
//发现对于特定的 x, y，dfs(x, y) 的结果是一定的
//但是搜索过程中我们可能多次运用 dfs(x, y)
if (vis[x][y]) return f[x][y];
vis[x][y] = true; //表示我们算过 dfs(x, y)
if (x == n + 1) {
return f[x][y] = 0;
}
f[x][y] = a[x][y] + std::max(dfs(x + 1, y), dfs(x + 1, y + 1));
return f[x][y];
//复杂度为状态的个数，就是 x, y 的个数
//状态数 -> 状态转移个数 n^2
}
signed main(){
std::cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
std::cin >> a[i][j];
//sum = a[1][1]
std::cout << dfs(1, 1); //O(n^2)
return 0;
}
例题3
例题4
爆搜即可通过，但要考虑的剪枝很多，时间复杂度很玄学。
剪枝策略：
-
相同的只搜一遍；
-
如果现在已经拼成的长度，在后面是不可能成功的。那么我们就认定这个分支是失败的。所以如果之后的分支再次遇见像这样的长度。我们就直接把他给返回就可以了。
-
如果刚开始拼接木棒的时候，第一根已经导致了拼接失败。那我们就可以判定当前的大分支是不可行的。至于为什么，是因为他在第一次已经不行。那么它在其他木棒中也是不可以的。
例题5
广告：ExOJ POJ题库
直接模拟翻转的过程，注意翻转时的边界条件。搜索时搜两次，同样判断边界，分别为操作以及不操作的数量，而且要注意位置的更新。当棋盘中所有位置的颜色都一样（用一个函数判断）时，维护最小的答案。如果全部搜完了答案还是原来的数值，输出 Impossible。
#include <iostream>
char ch[5][5];
int ans = 0x7fffffff;
bool check() { //判断所有格子颜色是否都相同
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if(ch[i][j] != ch[0][0])
return false;
}
}
return true;
}
bool pdin(int x, int y) { //判断是否在棋盘内（没有越界）
return x < 4 && y < 4 && x >= 0 && y >= 0;
}
void change(int x, int y) { //单个位置修改
ch[x][y] = (ch[x][y] == 'w' ? 'b' : 'w');
}
void update(int x, int y) { //四周都要修改
change(x, y);
//修改时要判断边界
if (pdin(x + 1, y)) change(x + 1, y);
if (pdin(x, y + 1)) change(x, y + 1);
if (pdin(x - 1, y)) change(x - 1, y);
if (pdin(x, y - 1)) change(x, y - 1);
}
void dfs(int x, int y, int cnt){
if(check()) { //满足条件
ans = std::min(cnt, ans);
return;
}
if(!pdin(x, y)) return; //如果不在棋盘内，返回
int yy = (y + 1) % 4; //得到下一个位置的坐标（y为0 1 2 3）
int xx = x + (y + 1) / 4; //x 的值，取决于y + 1是否等于4，等于则x + 1
dfs(xx, yy, cnt);
update(x, y);
dfs(xx, yy, cnt + 1);
update(x, y);
//搜两种情况。注意最后要还原
}
signed main() {
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
std::cin >> ch[i][j];
dfs(0, 0, 0);
if (ans == 0x7fffffff) std::cout << "Impossible"; //没有情况
else std::cout << ans;
return 0;
}
例题6
搜索 + 大模拟，太麻烦不说了。
例题7
dp或搜索，前置知识为二次函数和二元一次方程组。
折半搜索法
如果问题能分成两个相对独立的部分，且两部分搜索结果能很方便合并，那么就可以利用折半搜索来大大提高搜索的效率。
我们先搜前半部分，然后将前半部分的搜索结果存入 hash 表，再去搜后半部分，再把两次搜索结果合起来。
bfs宽度优先搜索
bfs可以直接用来求每条边边权为 \(1\) 的最短路问题。
用来求每条边边权为 \(0\) 或 \(1\) 的宽搜算法 —— 01bfs
注意要用双端队列 deque 来存，在队首插入 \(0\) 边扩展的，在队尾插入 \(1\) 边扩展的。
例题1
思路：bfs
Day2下午 数据结构
二叉搜索树
二叉搜索树的性质
二叉搜索树具有以下性质：
- 这是一颗二叉树
- 每个节点的左儿子比自己小
- 每个节点的右儿子比自己大
如图，这两个都是二叉搜索树。可能会是一条链，所以容易被卡掉（极端情况下可能和用 for 循环没啥区别）。
节点建立
const int MAXN = 100005;
const int L = 0, R = 1; //定义常量，方便代码编写
struct node{ //一个树上节点
int son[2]; //记录左右儿子的下标，分别对应 son[L], son[R]
int val; //这个节点储存的值
}a[MAXN];
int cnt; //决定分配节点编号
二叉搜索树该如何建立呢？
- 将节点从根节点开始插入
- 与当前节点比较大小
- 如果比当前节点储存的值大，向右递归
- 如果比当前节点储存的值小，向左递归
关于二叉搜索树
二叉搜索树有什么用呢？
没用
那为什么要学习二叉搜索树呢？
非常简单的二叉树结构，方便大家熟悉二叉树如何编写，以及二叉树的构成。
——吴凯路
模板
二叉堆
二叉堆的定义
-
二叉堆是一种特殊的二叉树
-
满足根节点比任意节点 大 / 小 （决定了是大根堆还是小根堆）
二叉堆的作用
一般二叉堆能解决什么问题呢？
在 \(O(log n)\) 的时间内插入一个元素
在 \(O(log n)\) 的时间内删除一个元素
在 \(O(1)\) 的时间内查询最大值
节点建立
需要储存左儿子，右儿子，自己的权值，子树大小
const int MAXN = 100005;
const int L = 0, R = 1; //定义常量，方便代码编写
struct node{ //一个树上节点
int son[2]; //记录左右儿子的下标，分别对应 son[L], son[R]
int val; //这个节点储存的值
int size; //这个节点对应的子树大小
}a[MAXN];
int cnt; //决定分配节点编号
插入操作
以大根堆为例
- 从根节点开始，插入一个值，如果当前值比根节点大，与根节点交换存储的值
- 然后往子树大小更小的儿子递归
- 直到某个儿子大小为0（即没有某一边儿子），新建一个节点来储存这个值
- 这样我们可以保证插入操作一定不超过log n次递归。
删除操作
以大根堆为例
- 将当前节点权值视为0，与最大的儿子交换权值并递归
- 直到节点是一个叶子（无左右儿子），然后删除该叶子。
- 这样我们可以保证删除操作一定不超过log n次递归。
- 删除根节点即可弹出最大值。
查询最大值操作
以大根堆为例
取根节点的权值即可。
STL中的堆——priority_queue 支持一切常用操作。
薄纱手写堆了属于是
模板
习题
灵活运用：
洛谷 P1090
洛谷 P1631
洛谷 P2085
线段树
信息学竞赛中最最最重要的数据结构，最最最常见的数据结构 ——吴凯路
线段树的作用
线段树解决什么问题呢？
各种各样的序列操作问题，例如最常见的问题：
有一个长度为 \(N\) 的序列（可能有初始值）
然后有 \(Q\) 次操作，每次操作可能是以下两种之一：
修改一个位置的值
查询一个区间的权值和
\(1 \le N,Q \le 10^5\)
线段树的定义
线段树是一种二叉树结构
线段树上每个节点对应一个区间 \([L,R]\)
节点的左儿子对应 \([L,Mid]\),右儿子对应 \([Mid+1,R]\)。
运用
如何构建线段树？
首先令根节点的范围为 \([1,N]\)，然后递归建立左右子节点。
一共需要 \(4N\) 个节点来建立线段树。
不过有特殊写法，动态开点只需要开二倍空间即可。
接下来写的是吴凯路老师讲的线段树，个人感觉很抽象（）
单点修改
从根开始向下递归，用二分的思路找这个点，然后找到包含这个点的所有区间，修改对应区间的统计值。
区间查询
- 查询的时候将区间作为参数传入
- 如果查询区间是当前区间的，那么返回当前节点的统计值
- 如果查询区间是当前区间的一个子区间，根据将查询区间按情况递归进入左儿子，或者右儿子或者两边。
- 这样可以把一个查询区间拆成已有的不超过 \(2 \times \log_2 n\) 个区间。
大家一定这么感觉：太简单了，只要学过分治不就能写出来吗？
难度提升警告
有一个长度为 \(N\) 的序列（可能有初始值）
然后有 \(Q\) 次操作，每次操作可能是以下两种之一：
给某个区间的所有位置加上一个权值 \(c\)。
查询某个区间的权值和
\(1 \ge N,Q \ge 10^5\)
区间修改 & lazy标记
有这样一个问题，有一个长度为10的区间，和为205，现在对于区间中每一个位置增加了7，那么和为多少？
可以计算和为 \(205 + 7 \times 10 = 275\)
我们知道每个位置的具体值吗？ 并不知道
与每个位置的具体值有关吗？ 无关
所以我们使用类似于区间查询的方法，将每个区间修改操作，拆成 \(\log_2{n}\)个已有的节点对应的区间。
然后单个节点可以自己更新自己的统计值（比如区间和），不需要下发这个操作到所有子节点。
但是我们需要记录当前有多少尚未下发的区间加操作。（即所有未下发的区间加操作的和）因为如果查询的不是整个区间，而是某个更小的子区间，那么会对答案造成影响。
所以我们有了下传操作（pushdown）。
下传标记即为将未下发的操作合并后变成一个操作一起下发给左右儿子。（注意只下发给左右子儿子就够了）
然后清空当前节点暂存的操作。（因为已经下传走了）
例题1
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define LL long long
const int L=0,R=1;
LL v[N];
struct xds{
int son[2];
LL sum;//区间和， 随时随地的区间总和，已考虑了addtag
LL addtag;//区间加标记 现在每个人加了addtag分
}a[N*2];int cnt;
void build(int &k,int l,int r){//建立线段树
k=++cnt;
if(l==r){
a[k].sum=v[l];//初始化信息
}else{
int mid=(l+r)>>1;
build(a[k].son[L],l,mid);//递归建立左儿子
build(a[k].son[R],mid+1,r);//递归建立右儿子
a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//合并左右儿子信息
}
}
// 给节点k，增加一个标记（告诉他所有人加分）
// 给节点k说，他管理的范围是[l,r]，然后所有人增加 val 分
void addtag(int k,int l,int r,LL val){//节点k上做区间加
a[k].sum+=(r-l+1)*val; // 显然管理区间的总分增加了 人数 * val
a[k].addtag+=val; // 记录一下当前的tag
}
void pushdown(int k, int l, int r){
int mid = (l+r) >> 1;
addtag(a[k].son[L],l,mid,a[k].addtag);
addtag(a[k].son[R],mid+1,r,a[k].addtag);
a[k].addtag=0;
}
// 节点k,管理[l,r]，对于区间[ql, qr] 集体增加 val
void modify(int k,int l,int r,int ql,int qr,LL val){//区间修改操作，比如区间加
if(ql==l&&r==qr){//全区间操作
addtag(k,l,r,val);
}else{
int mid=(l+r)>>1;
//下传并清空节点k的所有标记
pushdown(k, l, r);
if(qr<=mid) modify(a[k].son[L],l,mid,ql,qr,val);
else if(ql>mid) modify(a[k].son[R],mid+1,r,ql,qr,val);
else modify(a[k].son[L],l,mid,ql,mid,val),modify(a[k].son[R],mid+1,r,mid+1,qr,val);
a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//下传后更新
}
}
LL query(int k,int l,int r,int ql,int qr){//区间查询操作，比如问区间和
if(ql==l&&r==qr){//全区间查询
return a[k].sum;
}else{
int mid=(l+r)>>1;
//下传并清空节点k的所有标记
pushdown(k, l, r);
LL ret = 0;
if(qr<=mid) ret=query(a[k].son[L],l,mid,ql,qr);
else if(ql>mid) ret=query(a[k].son[R],mid+1,r,ql,qr);
else ret=query(a[k].son[L],l,mid,ql,mid)+query(a[k].son[R],mid+1,r,mid+1,qr);
return ret;
}
}
int n, m, root;
int main(){
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%lld", &v[i]);
build(root, 1, n);
for(int i=1;i<=m;i++){
int op, x, y;
LL k;
scanf("%d%d%d", &op, &x, &y);
if(op == 1){
scanf("%lld", &k);
modify(root, 1, n, x, y, k);
}else{
printf("%lld\n", query(root, 1, n, x, y));
}
}
return 0;
}
吴凯路老师的存树方式是动态开点，并且没有存 \(l,r\) 所以写法有一些奇特。我来贴一份详细注释、好理解的代码 。
例题2
在结构体中加一个 mul，即为乘法的lazy标记，和加法的lazy标记一样，用来更新区间答案以及打上/下传标记。
注意，在进行下传操作时，要先下传乘法的标记，再下传加法的标记，因为这样可以更方便地更新/获取答案
树状数组
树状数组与线段树
线段树是一种解决区间修改与区间查询的数据结构
树状数组是一种简单高效的解决单点修改与前缀查询的数据结构
也就是说，树状数组能实现的功能，线段树都可以
但是线段树通常比树状数组慢一倍时间，代码长三倍。
其实，树状数组可以看成线段树的 “青春版”。
树状数组的优劣势
-
优势：代码量短，速度较快。
-
劣势：树状数组只能支持单点修改和前缀查询，并不能支持区间修改和区间查询
树状数组的实现
\(lowbit_x\) 表示 \(x\) 最大的为 \(2\) 的整次幂的因数。
例如 \(lowbit_3=2^0=1, lowbit_{12}=2^2=4, lowbit_8=2^3=8\)
树状数组的节点i，管理的区间是 \([i-lowbit_i+1,i]\)，也就是长度为 \(lowbit_i\)，结尾为 \(i\) 的区间。
上图这是以上代码的搜索树，肉眼可见，这个搜索树会指数级增大，而且有大量的重复。
我们可以记录下每个状态得到的答案，这样第二次搜索到时，直接返回答案，
这就是记忆化搜索，本题搜索复杂度从 \(O(2^n+m)\) 降低到 \(O(mn)\)。
// dp版本
for(int i = 1;i <= n; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = max(dp[i - 1][j], dp[i][j -1]) + val[i][j];
// 两个循环完美满足所有要求。（其实大多数都是可以几个循环解决）
从前往后的递推，每个状态只算一次。
状态转移方程的补充说明：
状态转移方程需要满足如下条件：
-
除了初始状态以外，每个状态都可以通过其他状态计算得出
-
依赖关系不能成环（成环了，该按照什么顺序算？？？）
我们还忘了一个dp的关键要素——状态值函数
通常，我们通过拓扑序遍历所有状态来逐个计算状态值函数。
Day5图论
图的概念
有点有边的叫做图。
有向图：边有方向
无向图：边没有方向
度：一个顶点的度是指于该顶点相关联的边的条数（定义在无向图中）
对于有向图来说，一个顶点的度可细分为入度和出度
入度：与其关联的各边中，以其为终点的边数
出度：以改顶点为起点的边数。
自环：若一条边的两个顶点为同一顶点，则此边为自环。
路径：从一个顶点到另一顶点的可能经过同一个点和同一条边的路线
简单路径：不能走重复点和重复边的路径。
环：起点 = 终点的路径。
简单环：简单路径和环的集合体，保证起点 = 终点且除起点（终点）外不能经过重复的点和边的路径。
树相关
树：无向、无环、联通（任意两点间都可以互相到达）。
\(n\) 个点的树有 \(n-1\) 条边。
如果我们去除一些性质会变成什么样？
去掉联通：
森林：无向、无环、但不连通（有很多树组成）。
去掉无向：
有向树：有向、无环、联通。
外向树：所有的边都向外处指的有向树。
内向树：所有的边都通向一个点的有向树。
去掉无环
章鱼图 / 基环树：无向、联通且只有一个环。
\(n\) 个点，\(n\) 条边。章鱼图 -环上的一条边 = 树。
仙人掌：无向、联通且有多个环。
其他图
DAG：有向无环图（在树形dp中常用）
二分图：把无向图的所有的点分为两个部分，第一部分的点连接的一定是第二部分的点，第二部分的点连接的一定是第一部分的点。也就是说一条边一定是连接第一部分和第二部分的点。不要求联通。树和森林就是二分图。在树中，深度为奇数的为第一部分，深度为偶数的为第二部分。
奇环：长度为奇数的环。
存在奇环的不是二分图，所有的二分图也不存在奇环。
存图
邻接矩阵
const int MAXN=1010;
//邻接矩阵
//缺点：需要n^2的内存
//优点：取i->j这条边的信息只需要O(1)
int bian[MAXN][MAXN];
//bian[i][j]表示从i点到j点这条边的信息
void add_edge(int s,int e,int d){
bian[s][e]=d;
}
边表
const int MAXN=1010;
//vector存图：边表
//缺点：取i->j这条边的信息只需要O(n)
//优点：这需要O(n+m)的内存
vector<pair<int,int> >g[MAXN];//g[i]用来储存所有从i出发的边
void add_edge(int s,int e,int d){//添加一条从s->e长度为d的边
g[s].push_back(make_pair(e,d));
}
最短路问题
定义：从一个点到另一个点的所有路径中所经过的边边权之和最小的路径。
最短路的三角不等式
\(dist_{i,j} \le dist_{i,k} + dist_{k,j}\)
Floyd
本质上是一个动态规划。
状态： \(dist_{i,j,k}\) 代表从 \(j\) 走到 \(k\) 且走过的点的编号都 \(\le i\) 的最短路。
目标值：最后求出 \(dist_{n,j,k}\) 来作为我们的答案。
初始化：
-
如果 \(j\) 到 \(k\) 有边，\(dist_{0,j,k}=\min(dist_{0,j,k},d_{j,k})\)。
-
如果 \(j\) 到 \(k\) 无边，\(dist_{0,j,k}=∞\)。
转移方程：\(dist_{i,j,k}\rightarrow \min(dist_{i−1,j,k},dist_{i−1,j,i}+dist_{i−1,i,k})\)
例题1
#include<bits/stdc++.h>
using namespace std;
int dist[105][105][105];
//dist[i][j][k] 代表从 j 走到 k 使得中间经过的节点编号 <=i 的情况下的最短路
const int INF=0x3f3f3f3f;
int n,m;//n 点 m 边
signed main(){
memset(dist,0x3f,sizeof(dist));//把数组dist每一个元素赋值为INF
cin>>n>>m;
for(int i=1;i<=m;i++){
int s,e,d;
cin>>s>>e>>d;//一条从s到e长度为d的边
dist[0][e][s]=min(dist[0][e][s],d);
dist[0][s][e]=min(dist[0][s][e],d);
}
for(int i=1;i<=n;i++)
dist[0][i][i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dist[i][j][k]=min(dist[i-1][j][k],dist[i-1][j][i]+dist[i-1][i][k]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
printf("%d ",dist[n][i][j]);
printf("\n");
}
return 0;
}
时间复杂度 \(O(n^3)\)，空间复杂度 \(O(n^2)\)
我们发现在转移过程中，都是向 \(dist_{i,j,k}\) 转移的，所以可以压掉第一个维度来节省空间，可以写出以下代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int dist[MAXN][MAXN];
const int INF=0x3f3f3f3f;
signed main(){
memset(dist,0x3f,sizeof(dist));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int s,e,d;
scanf("%d%d%d",&s,&e,&d);
dist[e][s]=min(dist[e][s],d);
dist[s][e]=min(dist[s][e],d);
}
for(int i=1;i<=n;i++)
dist[i][i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dist[j][k]=min(dist[j][k],
dist[j][i]+dist[i][k]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
printf("%d ",dist[i][j]);
putchar('\n');
}
return 0;
}
dijkstra算法
SPFA算法
维护一个队列，用来存放可能会更新其他点最短路的点，每次用队首的点去做松弛操作（记得要弹出队首），在把其他满足条件的点加入队列，知道队列为空（有点像bfs）。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m,x;
long long dist[MAXN];
bool vis[MAXN];
vector<pair<int,int> >z[MAXN];
void add_edge(int s,int e,int d){//添加一个从s出发到e的长度为d的边
//push_back:向vector的末尾加入一个元素
z[s].push_back(make_pair(e,d));
}
void SPFA(int s){
memset(dist,0x3f,sizeof(dist));
dist[s]=0;
queue<int>q;
q.push(s);
vis[s]=true;
while(q.size()){
int p=q.front();
q.pop();
vis[p]=false;
for(int i=0;i<z[p].size();i++){
int e=z[p][i].first;
int d=z[p][i].second;
if(dist[e]>dist[p]+d){
dist[e]=dist[p]+d;
if(!vis[e])q.push(e),vis[e]=true;
}
}
}
}
signed main(){
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++){
int s,e,d;
scanf("%d%d%d",&s,&e,&d);
add_edge(s,e,d);
}
SPFA(x);
for(int i=1;i<=n;i++)
printf("%d ",dist[i]);
return 0;
}
强连通分量
定义
在有向图中，找到若干个点和若干条边，使得每个点都可以互相走到，构成的图就叫做强连通分量。独立的点也可以作为一个强连通分量。每个点都一定要在一个强连通分量里。
问题：给你一张有向图，找到所有的强连通分量。
tarjan算法
树边：DFS 树上的边
非树边：不是树边的边
找能组成环的非树边。
什么样的非树边能产生环？
回边：一条非树边连向自己的祖先，能形成环。
横叉边：不是回边的边（没连向自己的祖先，不能组成环）。
如果两条横叉边能组成环，那是因为 DFS 改变了树的形态，所以那不是横叉边，而是一条回边。
横叉边虽然不能组成环，但是可以扩大环的范围，但是要求连过去的边往上走的最上面的那个点必须是横叉边开始的点的 \(k\) 的祖先。
Day6上午 数学
取模运算基础
要算 \(n! \text{ mod } p\)
错误做法：
#include<bits/stdc++.h>
using namespace std;
signed main(){
int ans=1;
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++)ans*=i;
cout<<ans%p;
return 0;
}
如果算完阶乘再取模很可能爆掉，得出的结果就是错的。
正确做法：
边乘边模
#include<bits/stdc++.h>
using namespace std;
signed main(){
int ans=1;
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++)ans=ans*i%p;
cout<<ans;
return 0;
}
快速幂
我们在六年级的时候学过同底数幂的乘法法则，得知 \(x^a \times x^b = x^{a + b}\)，因此 \(x^{\frac{y}{2}} \times x^{\frac{y}{2}} = x ^ y\)，所以我们可以分治，直到指数为 \(0\)。记当前的结果为 \(z\)，底数为 \(x\)，指数为 \(y\)，按照 \(z^y = z^{\frac{y}{2}} \times z^{\frac{y}{2}}\) 来计算。如果当前的 \(y\) 为偶数，直接返回计算的结果；如果 \(y\) 为奇数，就要把刚才得到的结果再乘上一个 \(x\)，再返回。
int ksm(int x,int y,int p){
if(y==0)return 1;
int z=ksm(x,y/2,p);
z=1ll*z*z%p;
if(y&1)z=1ll*z*x%p;
return z;
}
逆元
若 \(a \times b \equiv 1 (\text{mod } p)\)，那么就称 \(b\) 为 \(a\) 在模 \(p\) 意义下的乘法逆元。借助逆元，我们就可以完成模意义下的除法操作了。
费马小定理：
\(p\) 为质数，\(\gcd(a,p) = 1\) 时，\(a^{p-1} \equiv 1(\text{mod } p)\).
两边同时 \(\div a\)，得 \(a^{p-2} \equiv \frac{1}{a} (\text{mod } p)\).
我们发现 \(a^{p-2} \times a \equiv 1 (\text{mod } p)\).
\(a^{p-2}\) 即为 \(a\) 在模 \(p\) 意义下的乘法逆元，快速幂求出即可。
所以，在 \(p\) 为质数，\(a\) 与 \(p\) 互质的情况下，\(a \div b \text{ mod } p = a \times a^{p-2} \text{ mod } p\).
欧拉定理：
当 \(\gcd(a,p)=1\) 时，\(a^{\varphi(p)} \equiv 1(\text{mod } p)\)
\(\varphi(p)\) 为欧拉函数，表示 \([1,p]\) 中有多少个数与 \(p\) 互质。
互质的定义：若 \(a\) 与 \(b\) 互质，则 \(\gcd(a,b) = 1\)。
这个时候我们会发现如果一个数 \(p\) 是质数，那么 \(\varphi(p) = p - 1\)，即除了 \(p\) 以外都与它互质。
得到 \(a^{\varphi(p)} \equiv 1(\text{mod } p)\) 这样就是费马小定理了。所以费马小定理实际上是欧拉定理的特殊情况。
扩展欧几里得算法
给你一组 \(a,b,c\)，求一组整数解 \(x,y\) 满足 \(ax + by = \gcd(a,b)\)。
假设我们现在要求 \(ax + by = \gcd(a,b)\)。令 \(g = \gcd(a,b)\)，我们学习过欧几里得算法
热门相关：从红月开始 嫡嫁千金 重生之嫡女祸妃 我是仙凡 我成了暴戾帝君的小娇包