大纲
完整堆操作
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第 k 个插入的数；C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,x,m=0,k;
int a[N],sz,ph[N],hp[N];
void heap_swap(int x,int y){
swap(ph[hp[x]],ph[hp[y]]);
swap(hp[x],hp[y]);
swap(a[x],a[y]);
}
void down(int u){
int t = u;
if(u*2<=sz && a[u*2]<=a[t]) t = u*2;
if(u*2+1<=sz && a[u*2+1]<=a[t]) t=u*2+1;
if(u!=t){
heap_swap(u,t);
down(t);
}
}
void up(int u){
while(u / 2 && a[u/2] > a[u]){
heap_swap(u/2,u);
u/=2;
}
}
int main(){
scanf("%d",&n);
while(n--){
char op[10];
scanf("%s",op);
if(!strcmp(op,"I")){
scanf("%d",&x);
sz++;
m++;
ph[m] = sz, hp[sz] = m;
a[sz] = x;
up(sz);
}
else if(!strcmp(op,"PM")){
printf("%d\n",a[1]);
}
else if(!strcmp(op,"DM")){
heap_swap(1,sz);
sz--;
down(1);
}
else if(!strcmp(op,"D")){
scanf("%d",&k);
k = ph[k];
heap_swap(k,sz);
sz--;
down(k), up(k);
}
else{
scanf("%d%d",&k,&x);
k = ph[k];
a[k] = x;
down(k), up(k);
}
}
return 0;
}
并查集应用：
食物链 AcWing240: 思路是存储到父节点的距离，并且每次做路径压缩的时候都要更新到根节点的距离，最后判断类型就依据到父节点的距离模3的余数来判断
#include<iostream>
using namespace std;
int n,m;
const int N=50010;
int p[N],d[N]; //d[x]表示到x父亲的距离
int find(int x){
if(p[x]!=x){
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main(){
cin>>n>>m;
int res=0;
for(int i=1;i<=n;i++) p[i]=i;
while(m--){
int t,x,y;
cin>>t>>x>>y;
if(x>n || y>n) res++;
else{
int px = find(x), py = find(y);
if(t==1){
if(px==py && (d[x] - d[y]) % 3) res++;
else if(px!=py){
p[px] = py;
d[px] = d[y] - d[x];
}
}
else{
if(px==py && (d[x] - d[y] - 1) % 3) res++;
else if(px!=py){
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n",res);
return 0;
}
哈希函数
主要作用： 1.将大范围映射到小范围内(可能有冲突) 2.开放寻址法或者拉链法
首先是拉链法:
#include<iostream>
#include<cstring>
using namespace std;
int n;
const int N=100003;
int h[N],e[N],ne[N],idx;
void search(){
for(int i=100000;;i++){
bool flag = true;
for(int j=2;j*j<=i;j++){
if(i % j == 0){
flag = false;
break;
}
}
if(flag){
cout<<i<<endl;
break;
}
}
}
void insert(int x){
int k = (x % N + N) % N; //余数变为正数
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
bool find(int x){
int k = (x % N + N) % N;
for(int i=h[k];i!=-1;i=ne[i]){
if(e[i]==x) return true;
}
return false;
}
int main(){
// cin.tie(0);cout.tie(0);
scanf("%d",&n);
memset(h,-1,sizeof h);
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
if(*op == 'I'){
insert(x);
}
else{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
然后是开放寻址法：
#include<iostream>
#include<cstring>
using namespace std;
int n;
const int N=200003, null = 0x3f3f3f3f;
int h[N],idx;
void search(){
for(int i=200000;;i++){
bool flag = true;
for(int j=2;j*j<=i;j++){
if(i % j == 0){
flag = false;
break;
}
}
if(flag){
cout<<i<<endl;
break;
}
}
}
int find(int x){
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x){
k++;
if(k == N) k = 0;
}
return k;
}
int main(){
scanf("%d",&n);
memset(h,0x3f,sizeof h);
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
int k = find(x);
if(*op == 'I') h[k] = x;
else{
if(h[k] != null) puts("Yes");
else puts("No");
}
}
return 0;
}
