保研机试训练Day-09

大纲

字符哈希

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数，请你判断两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。

#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;

typedef unsigned long long ULL;
const int N = 100010, P = 131; // P = 13331
int n,m;
char str[N];
ULL h[N],p[N];

ULL get(int l,int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main(){
    scanf("%d%d%s",&n,&m,str+1);
    p[0]=1;
    for(int i=1;i<=n;i++){
        p[i] = p[i-1] * P; 
        h[i] = h[i-1] * P + str[i];
    }
    while(m--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1) == get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

字符哈希

大纲

字符哈希

CATALOG

FEATURED TAGS