AKSZ - 第5~7课笔记
2024-06-09 18:15:22
发布于:英国
STL库
包含很多数据结构,可以节省手搓的时间直接用:
vector: 动态数组
queue: 队列
priority_queue: 优先队列
deque: 双向队列
set: 有序集合
multiset: 有序集合,但允许相同的元素
unordered_set: 无序集合
map: 字典,以键值对的方式储存数据
unordered_map: 无序的字典,通过哈希实现
bitset: 一种二进制数据结构,常用于加速位运算
倍增
一种基于指数增长模式的算法设计技术
典型例题:求a^b % (1e9+7), a<=1e9, b<=1e9
模板:
int a, b, mod, ans=1, k=a;
while (b){
if (b%2) ans *= k;
k *= k;
b /= 2;
}
cout << ans;
ST表
一种用于解决区间最小/最大值的数据结构
模板:
int st[10005][20]; //st[i][j]表示a[i]到a[i+2^j-1]项的最大/小值
int a[10005];
for (int k=1; k<=n; k++) st[k][0] = a[k];
for (int j=1; (1<<j)<=n; j++){
for (int k=1; k+(1<<j)-1<=n; k++){
st[k][j] = max(st[k][j-1], st[k+(1<<(j-1))-1][j-1]);
}
}
int find(int l, int r){
// 找到[l, r]之间的最大值
int len=log2(r-l+1);
return max(st[l][len], st[r-(1<<len)+1][len]);
}
矩阵快速幂
矩阵作为倍增的对象
矩阵类乘法的实现:
struct matrix{
int x, y;
int m[105][105];
matrix operator*(matrix other){
matrix ans;
// y必须等于other.x矩阵才能进行乘法
// 矩阵乘法不符合分配律,但符合结合律
ans.x = x; ans.y = other.y;
memset(ans.m, 0, sizeof ans.m);
for (int j=1; j<=x; j++){
for (int k=1; k<=other.y; k++){
for (int u=1; u<=y; u++){
ans.m[j][k] += m[j][u] + other.m[u][k];
}
}
}
return ans;
}
};
可以用来加速一些递推方程的计算,例如:
斐波那契数列的地推方程可以表示为:f[n]=f[n-1]+f[n-2]
使用矩阵可以表示为:
其中 表示第 n 个Fibonacci数。
并查集
一种处理不相交集合的数据结构和算法
模板:
f[10005];
for (int i=1; i<=n; i++) f[i] = i;
int find(int x){
if (x == f[x]) return x;
f[x] = find(f[x]);
return f[x];
}
int union(int x, int y){
x = find(x); y = find(y);
f[x]=y;
}
这里空空如也
有帮助,赞一个