近半年知识点总结(二)
2025-08-01 11:31:02
发布于：上海
前言：感谢复仇者_零对本文提出的修改建议，欢迎多多纠错！
一.前缀和与差分
(一维)
假设有一个数列:
那么它对应的前缀和数列就是:
与其相反的则是差分:
假设有一个数列:
那么它对应的差分数列就是:
假设这个差分数列的每一项是,则满足:
前缀和数列的差分数列就是原数列.
差分数列的前缀和数列就是原数列.
(高维)
二.快速幂
参考Microsoft Bing的回答.
快速幂是高效的指数级运算方法.
比如计算a^b,快速幂可将时间复杂度为的计算,降低至
具体方法可以看一个示例:
将13转化为1101(二进制);而后计算
三.最短路
//其实我本来想做动态规划的.
最短路分为"单源"和"多源".
单源指的是只有一个起点,多源指的是有多个起点.
然后求它们到某个顶点的最短路.
我学过了Dijkstra,Floyd,SPFA.
这三个算法各有特点.
Dij是由贪心思想作为基础,所以无法处理负环.不过有稳定性.
Floyd的代码是简单的,但效率不高.
SPFA可以处理负环,但代码容易与Dij搞混,且容易出问题.
从Dijkstra开始看吧.
它是单源最短路算法.
这里因为不是教程,只是自己的知识点总结,所以不会有过多解释.
Dij,前文提过,使用了贪心的思路.
主要体现在每次会选择距离起点最近的一个顶点进行松弛.
松弛:最短路算法的核心.即用某个顶点作为中转站,用这个顶点来更新与其相邻的其他顶点的最短路数值.
Dij模板:
#include<bits/stdc++.h>
using namespace std;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
vector<Node>v[1005];
bool vis[1005];
int dis[1005];
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
}
for(int i=1;i<=n;i++){
dis[i]=1e9;
}
dis[s]=0;
pq.push({s,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int len=v[k][i].q;
int to=v[k][i].z;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
pq.push({to,dis[to]});
}
}
}
for(int i=1;i<=n;i++){
dis[i]==1e9 ? cout<<-1<<" " : cout<<dis[i]<<" ";
}
return 0;
}
然后是一个跟最短路有关系的小技巧:反向建边.
题目:邮递员送信 差不多是这样:
所以只要反向建边,原来需要运行n+1次的Dij,就只需要运行2次了(都是算从点1到其他节点的距离,只不过一次正边一次反边.
然后是SPFA。
SPFA是Bellman-Ford的优化。
Bellma-Ford：枚举所有顶点的所有边进行松弛，无视先后顺序，每次枚举时，数组发生了变化，就继续枚举，直到不再发生变化。
而它的优化是 发生了变化的点的边继续松弛，没有发生变化的就置之不理。
而每条边最多会进行n次松弛。
所以SPFA的最坏时间复杂度是 。
如果说一条边进行了超过n次的松弛，那就证明图中存在负环。
负环即一个环中的边的边权相加是负数，负环之上不存在最短路.
题目：小码君的太空基地
代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int z,q;
};
queue<Node>q;
vector<Node>v[10005];
int dis[10005];
bool vis[10005];
int main(){
int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
}
for(int i=0;i<=n+1;i++){
dis[i]=1e9;
}
dis[s]=0;
q.push({s,0});
vis[s]=1;
while(!q.empty()){
Node sum=q.front();
q.pop();
int k=sum.z;
vis[k]=0;
for(int i=0;i<v[k].size();i++){
int len=v[k][i].q;
int to=v[k][i].z;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to]){
vis[to]=1;
q.push({to,dis[to]});
}
}
}
}
cout<<dis[t];
return 0;
}
四.动态规划
本来打算在这里写的，但是由于这个板块太大了，会直接写一整个文章来介绍DP。
有帮助，赞一个