头像

WansitHepburn




离线:11天前


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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int  N =1e5+10;
int ne[N][26],cnt[N],idx;
char s[N];
int n;

void insert(char *s){
    int p = 0;
    for(int i=1; s[i];++i){
        int temp = s[i] - 'a';

        if(!ne[p][temp]) ne[p][temp] = ++idx;
        p = ne[p][temp];
    }

    cnt[p]++;
}

int find(char *s){
    int p=0;
    for(int i=1;s[i];++i){
        int temp = s[i] - 'a';

        if(!ne[p][temp]) return 0;
        p = ne[p][temp];
    }

    return cnt[p];
}


int main(){
    cin>>n;

    char op[2];
    while(n--){
        scanf("%s",&op);

        if(op[0] == 'I'){
            cin>> s + 1;
            //cout<<"I"<<s + 1<<endl;
            insert(s );

        }

        if(op[0] == 'Q'){
            cin>> s + 1;
            //cout<<"Q"<<s + 1<<endl;
            cout<<find(s )<<endl;

        }
    }
    return 0;
}


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

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1e5+10;
const int M = 1e6+10;

char p[N];
char s[M];
int ne[N];

int 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){
            printf("%d ",i-n);
            j = ne[j];//从最后一个点回到末尾开头的位置
        }
    }
    return 0;
}




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

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1e5+10;
const int M = 1e6+10;

char p[N];
char s[M];
int ne[N];

int 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){
            printf("%d ",i-n);
            j = ne[j];//从最后一个点回到末尾开头的位置
        }
    }
    return 0;
}




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

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1e6+10;
int n,k;
int i,head;
int datas[N];
int idx[N];

int main(){
    cin>>n>>k;


    for(int i=0;i<n;++i){
        scanf("%d",&datas[i]);
    }


    int head=0,tail=-1;
    for(int i=0;i<n;++i){
        if(i - k +1 > idx[head]) head++;
        while(head<= tail && datas[idx[tail]] > datas[i]) tail--;
        idx[++tail] = i;

        if(i >= k - 1) cout<<datas[idx[head]]<<' ';
    }

    cout<<endl;

    head=0,tail=-1;
    for(int i=0;i<n;++i){
        if(i - k +1 > idx[head]) head++;
        while(head<= tail && datas[idx[tail]] < datas[i]) tail--;
        idx[++tail] = i;

        if(i >= k - 1) cout<<datas[idx[head]]<<' ';
    }
    return 0;
}


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

#include<iostream>
#include<cstdio>

using namespace  std;
const int N = 1e5+10;

int stk[N],n,idx;

int main(){
    cin>>n;
    int temp;

    while(n--){
        scanf("%d",&temp);
        while(idx && stk[idx] >= temp) idx--;
        if(!idx) cout<<"-1 ";
        else cout<<stk[idx]<<' ';
        stk[++idx] = temp;

    }
    return 0;
}


活动打卡代码 AcWing 829. 模拟队列

#include<iostream>
#include<cstdio>

using namespace std;
const int N = 1e5+10;

int q[N];
int m,head,tail;

int main(){
    cin>>m;
    string s;
    tail = -1;
    while(m--){
        cin>>s;
        int nums;
        if(s == "push"){
            scanf("%d",&nums);
            q[++tail] = nums;
        }
        if(s == "pop"){
            head++;
        }
        if(s == "empty"){
            if(head > tail) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        if(s == "query"){
            cout<<q[head]<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 828. 模拟栈

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 1e5+10;
int datas[N],m;
int sizes;

int main(){
    cin>>m;

    string  s;
    int nums;
    while(m--){
        cin>>s;
        if(s == "push"){
            scanf("%d",&nums);
            datas[++sizes] = nums;
        }
        if(s == "pop"){
            sizes--;
        }
        if(s == "empty"){
            if(sizes == 0)
                cout<<"YES"<<endl;
            else 
                cout<<"NO"<<endl;
        }
        if(s == "query"){
            cout<<datas[sizes]<<endl;
        }

    }
    return 0;
}




活动打卡代码 AcWing 827. 双链表

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N  = 1e5+10;
int e[N],l[N],r[N];
int n,idx,head;

void insert(int k,int nums){//在节点右侧插入一个数
    e[idx] = nums;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx++;
}

void del(int k){//删除节点
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(){
    r[0] = 1,l[1] = 0;
    idx  = 2;

    cin>>n;

    string op;
    int k,nums;

    while(n--){
        cin>>op;

        if(op == "L"){
            scanf("%d",&nums);
            insert(0,nums);
        }
        if(op == "R"){
            scanf("%d",&nums);
            insert(l[1],nums);
        }
        if(op == "D"){
            scanf("%d",&k);
            del(k+1);
        }
        if(op == "IL"){
            scanf("%d %d",&k,&nums);
            insert(l[k+1],nums);
        }
        if(op == "IR"){
            scanf("%d %d",&k,&nums);
            insert(k+1,nums);
        }
    }

    for(int i=r[0];i!= 1;i = r[i])
        printf("%d ",e[i]);
    return 0;
}


活动打卡代码 AcWing 826. 单链表

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N  = 1e5+10;
int e[N],ne[N],n,idx,head;

void head_insert(int nums){
    e[idx] = nums;
    ne[idx] = head;
    head = idx++;
}

void insert(int k,int nums){
    e[idx] = nums;
    ne[idx] = ne[k];
    ne[k] = idx++;

}

void del(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    head = -1;
    idx = 0;
    cin>>n;

    char op;
    int k,nums;

    while(n--){
        scanf("%s",&op);

        if(op == 'H'){
            scanf("%d",&nums);
            head_insert(nums);
        }
        else{
            if(op == 'I'){
                scanf("%d %d",&k,&nums);
                insert(k-1,nums);
            }
            else{
                scanf("%d",&k);
                if (!k) head = ne[head];//位置0只可能是head
                else del(k-1);
            }

        }
    }
    for(int i=head;i!= -1;i = ne[i])
        printf("%d ",e[i]);
    return 0;
}


活动打卡代码 AcWing 826. 单链表

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N  = 1e5+10;
int e[N],ne[N],n,idx,head;

void head_insert(int nums){
    e[idx] = nums;
    ne[idx] = head;
    head = idx++;
}

void insert(int k,int nums){
    e[idx] = nums;
    ne[idx] = ne[k];
    ne[k] = idx++;

}

void del(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    head = -1;
    idx = 0;
    cin>>n;

    char op;
    int k,nums;

    while(n--){
        scanf("%s",&op);

        if(op == 'H'){
            scanf("%d",&nums);
            head_insert(nums);
        }
        else{
            if(op == 'I'){
                scanf("%d %d",&k,&nums);
                insert(k-1,nums);
            }
            else{
                scanf("%d",&k);
                if (!k) head = ne[head];//位置0只可能是head
                else del(k-1);
            }

        }
    }
    for(int i=head;i!= -1;i = ne[i])
        printf("%d ",e[i]);
    return 0;
}