洛谷P5335 [THUSC2016]补退选 题解

传送门

一道字典树的例题吧

先说下思路前1,2两个条件都易满足，字典树插入修改即可，第三个条件可用动态数组来实现，存下它的size表示当前有几个节点经过（即人数），其下标表示第几次出现，里面存入操作次数（即时刻），然后字典树修改即可。

上代码

#include<bits/stdc++.h>
using namespace std;
const int N=300000;//开大点200000有一个点没过
struct node{
	int ch[30],size;
	vector<int> cmp;//动态数组
}trie[N];
int n,k,tot,a,b,c,ans;
char str[100];
struct tr{
	 void ins(char a[],int num){//插入
	 	int len=strlen(a);
        int p=0;
        for(int i=0;i<len;++i){
            int v=a[i]-'a';
            if(!trie[p].ch[v]) trie[p].ch[v]=++tot;
            p=trie[p].ch[v];
            trie[p].size++;
            if(trie[p].size>trie[p].cmp.size())trie[p].cmp.push_back(num);
        }
    }
    void deal(char a[]){//删除
    	int p=0,len=strlen(a);
    	for(int i=0;i<len;++i){
    		int v=a[i]-'a';
    		p=trie[p].ch[v];
    		trie[p].size--;
    	}
    	
    }
    int found(char s[],long long a,long long b,long long c){//找答案
    	int p=0,len=strlen(s);
    	long long tmp=(a*abs(ans)+b)%c;
    	for(int i=0;i<len;++i){
    		int v=s[i]-'a';
    		p=trie[p].ch[v];
    		if(trie[p].cmp.size()<=tmp) return -1;//没超过
    	}
    	return trie[p].cmp[tmp];
    }
}tr;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&k);
		if(k==1){
			scanf("%s",str);
			tr.ins(str,i);
		} 
		if(k==2){
			scanf("%s",str);
			tr.deal(str);
		}
		if(k==3){
			scanf("%s",str);
			scanf("%d %d %d",&a,&b,&c);
			printf("%d
",ans=tr.found(str,a,b,c));//记得修改答案
		}
	}
	return 0;
}