7-27 学习笔记

常规
1

7-27 堆与堆排序、并查集、STL表

小组：林育辰，郑荣，许文博，刘天顺

  • 堆与堆排序
  • 并查集
  • STL表

二叉堆

有关操作: 二叉堆插入、 二叉堆删除

Code: (一般没啥用)

struct Priority_queue{
	int heap[MAX];
    int tot=0; 
    void push(int k){    //插入
		heap[++tot]=k;
        int u=tot;
        while(u){
            int fa=(u>>1);
            if(heap[fa]<heap[u]) swap(heap[fa],heap[u]);
            else break;
            u=fa;
        }
    }
    void push_down(int u){   
        while(ls(u)<=tot){
            if(heap[u]<max(heap[ls(u)],heap[rs(u)])){
                if(rs(u)<=tot&&heap[rs(u)]>heap[ls(u)])
                    swap(heap[u],heap[rs(u)]),u=rs(u);
                else swap(heap[u],heap[ls(u)]),u=ls(u);
            }
            else break;
        }
    }
    void pop(){  //弹出
        swap(heap[tot],heap[1]);
        tot--;
        push_down(1);
    }
    void build(){
        for(int i=n/2;i;i--) push_down(i);
    }
};

例题:

例 1 : 洛谷 P1631 序列合并
例 2: 洛谷 P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
  • AC\ Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[30050],sum=0;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	priority_queue<int,vector<int>,greater<int> > Q;
	cin>>n;
	for(int i=1;i<=n;i++){
		int t;
		cin>>t;
		Q.push(t);
	}
	while(Q.size()!=1){
		int x1=Q.top();Q.pop();
		int x2=Q.top();Q.pop();
		sum+=(x1+x2);
		Q.push(x1+x2);
	}
	cout<<sum;
	return 0;
}

并查集

删除、移动 的对象为 叶子

例题

例 1 : P2024 [NOI2001] 食物链

  • 让我薅一篇题解 AC\ Code:

    #include <cstdio>
inline int read(){
	char c = getchar(); int n = 0;
	while (c < '0' || c > '9') { c = getchar(); }
	while (c >='0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar();}
	return n;
}
const int maxN = 100005;
int n, m, ans, fa[maxN * 3];
int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }
int main() {
	n = read(), m = read();
	for (int i = 1; i <= n * 3; i++) { fa[i] = i; }
	for (; m; m--) {
		int opt = read(), u = read(), v = read();
		if (u > n || v > n) { ans++; continue; }
		if (opt == 1) {
			if (find(u + n) == find(v) || find(u) == find(v + n))  ans++;
			else {
				fa[find(u)] = find(v);
				fa[find(u + n)] = find(v + n);
				fa[find(u + n + n)] = find(v + n + n);
			}
		}
        else {
			if (find(u) == find(v) || find(u) == find(v + n))  ans++;
			else {
				fa[find(u + n)] = find(v);
				fa[find(u + n + n)] = find(v + n);
				fa[find(u)] = find(v + n + n);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}
例 2 : 洛谷 P2391 白雪皑皑

  • AC\ Code:

    #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m,x,y,q,p,f;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);	
	n=read(),m=read(),p=read(),q=read();
	for(int i=1;i<=n;i++){
		f=0;
		for(int j=m;j>=m-n;j--){
			x=(j*p+q)%n+1;
			y=(j*q+p)%n+1;
			if(x>y) swap(x,y);
			if(i>=x&&i<=y){
				cout<<j;
				f=1;
				break;
			}
		}
		if(f==0) cout<<0;
		cout<<"\n";
	}
	return 0;
}

STL

标准STL

重载运算符 operator

(我不会用欸)

vector

  • A.push\_back(x) 末尾添加元素
  • A.pop\_back() 末尾删除元素
  • A.size() 元素个数
  • A.resize(x) 将 size 改为 x

迭代器

auto it=___; //某地址
cout<<*it;

遍历元素:

//方法1
vector<int> v;
for(auto it=v.begin();it!=v.end();it++)
//方法2
for(auto i:v) cout<<i;

queue

(会 bfs 的人都会)

priority_queue

是一个封装好的优先队列(堆);

查询堆顶O(1); 弹出O(log n)

map

(一般人都会用)

时间复杂度O(log n)

空间复杂度O(n);

unordered map

！不能存重复元素

时间复杂度O(1)

set

自带 lower\_bound(),upper\_bound() 返回迭代器

自动去重

mutset

相比于 set 不会去重, 操作与 set 相似;

2 个赞
2

最后一个是multiset吧
tjl

1 个赞