头像

烧仙草

苏州大学


访客:310

离线:12小时前


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

烧仙草
21小时前
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int p[N],d[N];
int find(int x){
    if(p[x]!=x){
        int u=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=u;
    }
    return p[x];
}
int main(){
    int n,k;
    int res=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    while(k--){
        int t,x,y;
        cin>>t>>x>>y;
        if(x>n||y>n) res++;
        else{
            int px=find(x);
            int 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]-d[x]+1;
                }
            }
        }
    }
    cout<<res<<endl;
    return 0;
}



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


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

#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--){
        char op[2];
        int a, b;
        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>
#include<algorithm>
using namespace std;
const int N=1e5+10;
const int M=3e6+10;
int son[M][2],idx;
int a[N];
void insert(int x){
    int p=0;
    for(int i=30;~i;i--){
        int &s=son[p][x>>i&1];
        if(!s) s=++idx;
        p=s;
    }
}
int query(int x){
    int p=0;
    int res=0;
    for(int i=30;~i;i--){
        int s=x>>i&1;
        if(son[p][!s]){
            res+=1<<i;
            p=son[p][!s];
        }
        else p=son[p][s];
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    int res=0;
    for(int i=0;i<n;i++){
        res=max(res,query(a[i]));
    }
    cout<<res<<endl;
    return 0;
}



#include<iostream>
using namespace std;
const int N=1e5+10;
int son[N][26],cnt[N],idx;
char str[N];
void insert(char op[]){
    int p=0;
    for(int i=0;op[i];i++){
        int u=op[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;//idx代表绝对位置
        p=son[p][u];
    }
    cnt[p]++;
}
int query(char op[]){
    int p=0;
    for(int i=0;op[i];i++){
        int u=op[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main(){
    int n;
    cin>>n;
    while(n--){
        char s[2];
        cin>>s;
        if(s[0]=='I'){
            cin>>str;
            insert(str);
        }
        else{
            cin>>str;
            printf("%d\n",query(str));
        }
    }
}


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

#include<iostream>
using namespace std;
const int N=1e5+10;
int son[N][26],cnt[N],idx;
char str[N];
void insert(char op[]){
    int p=0;
    for(int i=0;op[i];i++){
        int u=op[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int query(char op[]){
    int p=0;
    for(int i=0;op[i];i++){
        int u=op[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main(){
    int n;
    cin>>n;
    while(n--){
        char s[2];
        cin>>s;
        if(s[0]=='I'){
            cin>>str;
            insert(str);
        }
        else{
            cin>>str;
            printf("%d\n",query(str));
        }
    }
}


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

include[HTML_REMOVED]

using namespace std;
const int N=1e5+10;
const int M=1e6+10;
int n,m;
char s[M],p[N];
int ne[N];
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){
        printf("%d ",i-n);
        j=ne[j];
    }
}

}



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

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int n,k;
int hh=0;
int tt=-1;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[i]<=a[q[tt]]) tt--;
        q[++tt]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    cout<<endl;
    hh=0;
    tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[i]>=a[q[tt]]) tt--;
        q[++tt]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    return 0;
}



#include<iostream>
using namespace std;
const int N=1e5+10;
int skt[N],tt;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(tt&&skt[tt]>=x) tt--;
        if(tt) cout<<skt[tt]<<" ";
        else cout<<"-1"<<" ";
        skt[++tt]=x;
    }
    return 0;

}


活动打卡代码 AcWing 830. 单调栈

#include<iostream>
using namespace std;
const int N=1e5+10;
int skt[N],tt;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(skt[tt]>=x&&tt){
            tt--;
        }
        if(tt) cout<<skt[tt]<<" ";
        else cout<<"-1"<<" ";
        skt[++tt]=x;
    }
    return 0;
}