https://www.lbxpace.com/index.php/tag/String/ https://www.lbxpace.com/index.php/archives/16/ 2023-08-28T23:08:00+08:00 题目描述阿里巴巴的手机代理商正在研究 infra 输入法的新功能。他们需要分析单词频率以改进用户输入法的体验。于是需要你在系统内核里面写一个 API。API有如下功能：添加操作 添加操作格式为$insert~~barty~~8$，意思为插入$barty$这个单词，这个单词词频为 $8$ 次。注意如果再次添加$insert~~barty~~8$操作时，就会将词频增加为 $16$ 次。（不会出现词频$\le 0$的情况）。删除操作删除操作格式为$delete~~barty$，意思为删除所有$barty$这个单词。如果当前没有删除的词汇，输出"$Empty$"。查询操作查询操作格式为$query~~ty$，意思为查询当前版本以$ty$结尾的单词词频总和。修改操作修改操作格式为$update~~ty~~tied$，意思为将所有结尾是$ty$的单词更新为$tied$结尾，比如$barty$会变为$bartied$。如果不存在$ty$结尾的单词，输出$Empty$。如果已经存在$tied$结尾的单词，那么说明存在$conflict$。 不做合并，输出$Conflict$。如果既不存在$ty$结尾的单词，也已经存在以$tied$结尾的单词，则输出$Empty$。输入格式第一行读入一个整数 $T$，代表数据组数。每组数据的第一行读入一个整数 $N$ 代表操作数。接下来 $N$ 行，每行形容一个操作。保证数据满足 $1\le T\le 10$，$1\le N\le 10^5$，$insert$和$update$操作的字符串总长度之和 $\le 10^6$，所有字符串长度 $≤10^6$，输入只有小写字母。输出格式输出题目中要求的结果样例输入1 10 update y ty insert barty 8 delete shawn update ty tied query tied insert party 9 update y tied query ty delete barty query tied样例输出Empty Empty 8 Conflict 9 Empty 8题目链接[button color="success" url="https://vjudge.net/problem/计蒜客-A1703" outline="default" target="_blank"]👉vjudge_阿里巴巴的手机代理商（中等）[/button] [quote color="info"]注:登陆了才能看到题目[/quote]思路逆序字典树，转移的时候把所有节点都移过去的ok了，这样每个操作效率是$O(n*26),n<10^6$。代码#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> typedef long long LL; struct trie { LL count; trie *next[26]; }; trie *root; trie* newtrie() { trie *t; t=(trie*)malloc(sizeof(struct trie)); memset(t,0,sizeof(struct trie)); return t; } char oo[100000+100]; char o2[100000+100]; void Insert(char *ch,LL num) { int i; trie *t,*s; s=root; for(i=0;ch[i];i++) { if(s->next[ch[i]-'a']) { s=s->next[ch[i]-'a']; s->count=s->count+num; } else { t=newtrie(); s->next[ch[i]-'a']=t; s=t; s->count=num; } } } LL Search(char *ch)/*搜索函数，返回0则代表字典树不存在该字符串，反之亦然 */ { int i; trie *s=root; if(ch[0]==0) return 0; for(i=0;ch[i];i++) { if(s->next[ch[i]-'a']) s=s->next[ch[i]-'a']; else break; } if(ch[i]==0) return s->count; else return 0; } bool Delete(char *ch)/*删除函数，将该字符串从字典树中删除（删除之前记得事先判断存不存在该字符串）*/ { int i; trie *s; s=root; if(ch[0]==0) return false; for(i=0;ch[i];i++) { // printf("%c -%lld\n",ch[i],s->count); if(s->next[ch[i]-'a']) s=s->next[ch[i]-'a']; else return false; } LL sum=0; sum+=s->count; for(i=0;i<26;i++) if(s->next[i]) sum-=s->next[i]->count; if(sum==0) return false; Insert(ch,-sum); return true; } LL Update(char *ch1,char *ch2) { LL t1,t2; t1=Search(ch1); t2=Search(ch2); if(t1==0) return -1;//printf("%d %d\n",t1,t2); if(t2!=0) return 1; // int i; trie *t,*s; s=root; for(i=0;ch1[i];i++) s=s->next[ch1[i]-'a']; trie *pp[26]; LL sum=s->count; for(i=0;i<26;i++) { pp[i]=s->next[i]; s->next[i]=NULL; } Insert(ch1,-sum); s=root; // for(i=0;ch2[i];i++) { if(s->next[ch2[i]-'a']) { s=s->next[ch2[i]-'a']; s->count+=sum; } else { t=newtrie(); s->next[ch2[i]-'a']=t; s=t; s->count=sum; } } for(int i=0;i<26;i++) s->next[i]=pp[i]; return 0; // } void swap(char *ch) { int len=strlen(ch); for(int i=0;i<len/2;i++) { char z=ch[i]; ch[i]=ch[len-1-i]; ch[len-1-i]=z; } } void clear(trie *now) { if(now==NULL) return ; for(int i=0;i<26;i++) clear(now->next[i]); free(now); } int main() { int T; scanf("%d",&T); root=newtrie(); while(T--) { int N; scanf("%d",&N); clear(root); root=newtrie(); while(N--) { char ope[10]; getchar(); scanf("%s",ope); if(ope[0]=='i') { LL tt; scanf("%s %lld",oo,&tt); swap(oo); Insert(oo,tt); } if(ope[0]=='d') { scanf("%s",oo); swap(oo); bool q=Delete(oo); if(q==false) printf("Empty\n"); } if(ope[0]=='q') { scanf("%s",oo); swap(oo); LL z=Search(oo); if(z==0) printf("0\n"); else printf("%lld\n",z); } if(ope[0]=='u') { scanf("%s %s",oo,o2); swap(oo); swap(o2); int z=Update(oo,o2); if(z==-1) printf("Empty\n"); if(z==1) printf("Conflict\n"); // printf("\n\n%d\n\n",z); } } } return 0; }