[Trie]2018计蒜之道初赛第二场【阿里巴巴的手机代理商】题解

Author Avatar
ZigZagK 2018年5月14日 13:51
remove_red_eye 111

题目概述

\(n\) 个询问:

  1. \(Insert\ s\ x\) :增加 \(x\)\(s\)
  2. \(Delete\ s\) :删除所有 \(s\)
  3. \(Query\ s\) :查询以 \(s\) 为后缀的字符串数量。
  4. \(Update\ s\ t\) :把后缀 \(s\) 换成 \(t\) ,保证 \(Query\ t=0\)

解题报告

神tm调代码能力大赛,先把串反一下,然后后缀就变成了前缀,用Trie搞就行了。

\(Update\) 操作实际上就是把 \(s\) 的子树截下来然后移到 \(t\) 的子树上,因为保证之前 \(t\) 不存在,所以不用考虑子树合并(而且我也不会啊)。

其实有进阶版的……就是多了个回退操作……可持久化一下就行了,懒得写了XD。

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxl=1e6,maxt=maxl<<1,maxi=26;

int te,n;char td[maxl+5],s[maxl+5],t[maxl+5];
int si,son[maxt+5][maxi];LL sum[maxt+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline int reads(char *s){
    int len=0;char ch=readc();while (!islower(ch)) ch=readc();
    while (islower(ch)) s[++len]=ch,ch=readc();return s[len+1]=0,len;
}
inline void Insert(char *s,LL num){
    int p=0;sum[p]+=num;
    for (int i=1;s[i];i++){
        if (!son[p][s[i]-'a']) son[p][s[i]-'a']=++si;
        p=son[p][s[i]-'a'];sum[p]+=num;
    }
}
inline LL val(int p){
    LL ans=sum[p];
    for (int i=0;i<maxi;i++)
        if (son[p][i]) ans-=sum[son[p][i]];
    return ans;
}
inline void Delete(char *s){
    int p=0;
    for (int i=1;s[i];i++){
        if (!son[p][s[i]-'a']) {puts("Empty");return;}
        p=son[p][s[i]-'a'];
    }
        LL tot=val(p);if (!tot) {puts("Empty");return;}
    p=0;sum[p]-=tot;for (int i=1;s[i];i++) sum[p=son[p][s[i]-'a']]-=tot;
}
inline LL Query(char *s){
    int p=0;
    for (int i=1;s[i];i++){
        if (!son[p][s[i]-'a']) return 0;
        p=son[p][s[i]-'a'];
    }
    return sum[p];
}
inline void Update(char *s,char *t){
    if (!Query(s)) {puts("Empty");return;} else if (Query(t)) {puts("Conflict");return;}
    int S=strlen(s+1),T=strlen(t+1),p,pp;
    p=0;for (int i=1;i<S;i++) p=son[p][s[i]-'a'];pp=son[p][s[S]-'a'];son[p][s[S]-'a']=0;
    p=0;sum[p]-=sum[pp];for (int i=1;i<S;i++) sum[p=son[p][s[i]-'a']]-=sum[pp];Insert(t,0);
    p=0;sum[p]+=sum[pp];for (int i=1;i<T;i++) sum[p=son[p][t[i]-'a']]+=sum[pp];son[p][t[T]-'a']=pp;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (readi(te);te;te--){
        si=0;memset(son,0,sizeof(son));memset(sum,0,sizeof(sum));
        for (readi(n);n;n--){
            reads(td);int len=reads(s);for (int i=1;i<=(len>>1);i++) swap(s[i],s[len-i+1]);
            if (!strcmp(td+1,"insert")) {int x;readi(x);Insert(s,x);}
            else if (!strcmp(td+1,"delete")) Delete(s);
            else if (!strcmp(td+1,"query")) printf("%lld\n",Query(s));
            else {len=reads(t);for (int i=1;i<=(len>>1);i++) swap(t[i],t[len-i+1]);Update(s,t);}
        }
    }
    return 0;
}

本文链接:https://zigzagk.top/2018/05/14/jisuanke26986
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。