头像

不知不觉


访客:196

离线:10小时前


活动打卡代码 AcWing 839. 模拟堆

#include<istream>
#include<algorithm>
#include<string.h>
const int N=100010;
int h[N],ph[N],hp[N],cht;
void new_swap(int a,int b){
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}
viod down(int u){
    int t=u;
    if(u*2<=cht&&h[u*2]<h[t]) t=u*2;
    if(u*2+1<=cht&&h[u*2+1]<h[t]) t=u*2+1;
    if(u!=t){
        new_swap(u,t);
        down(t);
    }
}
void up(int u){
    while(u/2&&h[u/2]>h[u]) {
        new_swap(u/2,u);
        u=u/2;
    }
}
int main()
{
    int n,m=0;
    cin>>n;
    char op[4];
    int k,x;
    while(n--){
    cin>>op;
        if(!strcmp(op,"I")) {
            cin>>x;
            cht++;
            m++;
            ph[cht]=m;
            hp[m]=cht;
            h[cht]=x;
            uup(cht);
        }
        else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
        else if(!strcmp(op,"DM")){
            new_swap(1,cht);
            cht--,down(1);
        }
        else if(!strcmp(op,"D")){
            cin>>k;
            k=ph[k];
            new_swap(k,cht);
            cht--;
            up(k),down(k);
        }
        else{
            cin>>k>>x;
            k=ph[k];
            h[k]=x;
            up(k);
            down(k);
        }
    }
    return 0;
}



解释即在代码中

#include<iostream>
#include<string.h>
using namespace std;
const int N=100010;
int h[N],ph[N],hp[N],cht;
//ph[k]第k个插入点的下标,目的便于操作时寻找第k个插入点的下标
//hp[k]下标为k的点为第几个插入的点,目的便于操作时寻找下标为k的点为第几个插入的点
//满足ph[k]=u,hp[u]=k
//h[k]当前存储的值
void new_swap(int a,int b){
    swap(ph[hp[a]],ph[hp[b]]);//交换下标
    swap(hp[a],hp[b]);//交换k(第几个插入点)值
    swap(h[a],h[b]);//交换值
}
void down(int u){       //down操作
    int t=u;
    if(u*2<=cht&&h[u*2]<h[t]) t=u*2;
    if(u*2+1<=cht&&h[u*2+1]<h[t]) t=u*2+1;
    if(u!=t){
        new_swap(u,t);
        down(t);
    }
}
void up(int u){           //up操作
    while(u/2&&h[u/2]>h[u]){
        new_swap(u/2,u);
        u=u/2;
    }
}
int main()
{
    int n;
    cin>>n;
    char op[4];
    int k,x,m=0;
    while(n--){
        scanf("%s",op);
        if(!strcmp(op,"I")){
            cin>>x;
            cht++;//记录当前下标
            m++;//记录第几个插入的点
            ph[m]=cht;//记录下标
            hp[cht]=m;//记录下标cht时,为第几个插入点
            h[cht]=x;
            up(cht);
        }
        else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
        else if(!strcmp(op,"DM")) {
            new_swap(1,cht);
            cht--;
            down(1);}
        else if(!strcmp(op,"D")) {
            cin>>k;
            k=ph[k];//求第k个插入值的下标
            new_swap(k,cht);
            cht--;
            up(k);
            down(k);
        }
        else{
            cin>>k>>x;
            k=ph[k];
            h[k]=x;
            up(k);
            down(k);
        }
    }
    return 0;
}


活动打卡代码 AcWing 838. 堆排序

#include<iostream>
#include<algorithm>
const int N=100010;
int h[N],siz;
int n,m;
void down(int u){
    int t=u;
    if(u*2<=siz&&h[u*2]<h[t]) t=u*2;
    if(u*2+1<=siz&&h[u*2+1]<h[t]) t=u*2+1;
    if(u!=t){
        swap(h[t],h[u]);
        down(t);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    siz=n;
    for(int i=n/2;i>=1;i--) down(i);
    while(m--){
        printf("%d ",h[1]);
        h[1]=h[siz--];
        down(1);
    }
    return 0;
}


活动打卡代码 AcWing 240. 食物链

#include<iostream>
using namespace std;
const int N=500010;
int p[N],d[N];
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()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) p[i]=i;
    int res=0;
    while(k--){
        int t,x,y;
        scanf("%d%d%d",&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++;
                if(px!=py){p[px]=py;d[px]=d[y]-d[x];}
            }
            else{
                if(px==py&&(d[x]-d[y]-1)%3) res++;
                if(px!=py){p[px]=py;d[px]=d[y]+1-d[x];}
            }
        }
    }
    cout<<res;
    return 0;
}



#include<iostream>
using namespace std;
const int N=100010;
int p[N],se[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i,se[i]=1;
    char op[2];
    int a,b;
    while(m--){
        cin>>op;
        if(op[0]=='C'){
            cin>>a>>b;
            if(find(a)==find(b)) continue;
            se[find(b)]+=se[find(a)];
            p[find(a)]=find(b);
        }
        else if(op[1]=='1') {
            cin>>a>>b;
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
        else{
            cin>>a;
            cout<<se[find(a)]<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 836. 合并集合

#include<iostream>
using namespace std;
const int N=100010;
int p[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    char op[2];
    int a,b;
    while(m--){
     scanf("%s%d%d",op,&a,&b);
     if(op[0]=='M') p[find(a)]=find(b);
     else{
         if(find(a)==find(b)) puts("Yes");
         else puts("No");
     }
    }
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

#include<iostream>
using namespace std;
const int N=3100000;
int s[N][2],idx;
int n;
void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(!s[p][u]) s[p][u]=++idx;
        p=s[p][u];
    }
}
int query(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(s[p][!u]) {
            res+=1<<i;
            p=s[p][u];
        }
        else p=s[p][u];
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    int x,res=0
    while(n--){
        scanf("%d",&x);
        insert(x);
        res=max(res,query(x));
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

#include<iostream>
using namespace std;
const int N=100010;
int s[N][26],cnt[N],idx;
char str[N],n;
void insert(char str[]){
    int p=0;
    for(int i=0;str[i];i++){
    int u=str[i]-'a';
        if(!s[p][u]) s[p][u]=++idx;
        p=s[p][u];
    }
    cnt[p]++;
}
int query(char str[]){
    int p=0;
    for(int i=0;str[i];i++){
        int u=str[i]-'a';
        if(!s[p][u]) return 0;
        else p=s[p][u];
    }
    return cnt[p];
}
int main()
{
    cin>>n;
    while(n--){
        char op;
        cin>>op;
        if(op=='I') {
            cin>>str;
            insert(str);
        }
        else {
            cin>>str;
            cout<<query(str)<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

#include<iostream>
using namespace std;
const int N=100010,M=1000010;
char q[N],s[M];
int ne[N],n,m;
int main()
{
    cin>>n>>p+1>>m>>s+1;
    for(int i=2,j=0;i<=n;i++){
        while(j&&p[i]!=p[j+1]) j=ne[j];//寻找下一个匹配位置
        if(p[i]==p[j+1]) j++;
        ne[i]=j;//记录后缀长度
    }
    for(int i=1,j=0;i<=m;i++){
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n){
            cout<<i-n<<" ";
            j=ne[j];
        }
    }
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

#include<iostream>
const int N=1000010;
int a[i],q[i];
int n,k,,hh,tt;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)  scanf("%d",&a[i]);
    hh=0;tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++t]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts("");
     hh=0;tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++t]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts("");
    return 0;
}