一、 堆与堆排序
1. 堆:
- 一种树，满足所有父节点都比它的子节点权值更大(堆的性质)
- 例题: P3378 【模板】堆
#include<bits/stdc++.h>
using namespace std;
class priority_queue{
private:
int a[1000002],siz;
public:
int top(){return a[1];}
void push(int x){
a[++siz] = x; int idx = siz;
while(idx){
if(a[idx]<a[idx>>1]) swap(a[idx],a[idx>>1]);
else break;
idx >>= 1;
}
}
void pop(){
swap(a[1],a[siz]); siz--;
int idx = 1;
while((idx<<1)<=siz){
int son = idx<<1;
if((son|1)<=siz && a[son|1]<a[son]) son |= 1;
if(a[son]<a[idx]) swap(a[son],a[idx]);
else break;
idx = son;
}
}
}q;
int n;
int main(){
cin >> n;
int o,t;
for(int i=1;i<=n;i++){
cin >> o;
if(o==1){
cin >> t;
q.push(t);
}
if(o==2){
cout << q.top() << endl;
}
if(o==3){
q.pop();
}
}
return 0;
}
2. 堆排序
- 利用堆的性质进行的排序(\textcolor[RGB]{255,255,255}{废话})
- 复杂度: O(nlogn)
二、并查集
1. 一些优化
- 按秩合并: 按集合的大小合并，减少操作
- 路径压缩: 将节点的父亲指向祖先，缩短查询路径
- 运用这两种优化后时间复杂度: O(\alpha(n))
2. 种类并查集
- 维护一种循环对称的关系，例如"A吃B，B吃C，C吃A"
- 例题: P2024 [NOI2001] 食物链
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50001;
int n,k,cnt,p[3*maxn],d[3*maxn];
int find(int x){return (x==p[x])?x:(p[x]=find(p[x]));}
int main(){
cin >> n >> k;
for(int i=1;i<=n;i++){
p[i] = i;
p[i+maxn] = i+maxn;
p[i+2*maxn] = i+2*maxn;
}
for(int i=0;i<k;i++){
int q,x,y;
cin >> q >> x >> y;
if((x>n || y>n) || (q==2 && x==y))
cnt++;
else if(q==1){
if(find(x+maxn)==find(y) || find(x)==find(y+maxn))
cnt++;
else{
p[find(x)] = find(y);
p[find(x+maxn)] = find(y+maxn);
p[find(x+(maxn<<1))] = find(y+(maxn<<1));
}
}
else if(q==2){
if(find(x)==find(y) || find(x)==find(y+maxn))
cnt++;
else{
p[find(x+maxn)] = find(y);
p[find(x+(maxn<<1))] = find(y+maxn);
p[find(x)] = find(y+(maxn<<1));
}
}
}
cout << cnt;
return 0;
}
三、STL模板
这个就没有必要讲了罢
四、平板电视
1. 前置:
#include<ext/pb_ds/assoc_container.h>(都要)#include<ext/pb_ds/tree_policy.h>(树)using namespace __gnu_pbds(命名空间)
2. 红黑树:
- 定义:
tree<int,null_type,less<int>,rb_tree_tag,tree_node_statistics_update> tr - 别的不知道，现在去学(雾)