【LOJ】#2291. 「THUSC 2016」补退选

题解

在trie树上开vector记录一下这个前缀出现次数第一次达到某个值的下标，以及记录一下现在这个前缀有多少个

为什么thusc有那么水的题……是为了防我这种cai ji爆零么= =

代码

#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cmath>

#include <cstring>

//#define ivorysi

#define pb push_back

#define eps 1e-12

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define mo 974711

using namespace std;

typedef long long int64;

typedef double db;

struct node {

    vector<int> v;

    int cnt;

    int nxt[10];

    node() {cnt = 0;v.clear();memset(nxt,0,sizeof(nxt));}

}tr[6000005];

int rt = 1,nodecnt = 1,Q;

char s[65];

void Insert(int id,char *str,int on) {

    int p = 1,L = strlen(str + 1);

    for(int i = 1 ; i <= L ; ++i) {

	if(!tr[p].nxt[str[i] - 'a']) {

	    tr[p].nxt[str[i] - 'a'] = ++nodecnt;

	}

	p = tr[p].nxt[str[i] - 'a'];

	tr[p].cnt += on;

	if(tr[p].cnt > tr[p].v.size()) tr[p].v.pb(id);

    }

}

int Query(char *str,int x) {

    int p = 1,L = strlen(str + 1);

    for(int i = 1 ; i <= L ; ++i) {

	if(!tr[p].nxt[str[i] - 'a']) return -1;

	p = tr[p].nxt[str[i] - 'a'];

    }

    if(tr[p].v.size() - 1 < x) return -1;

    return tr[p].v[x];

}

void Solve() {

    scanf("%d",&Q);

    int K,ans = 0,a,b,c;

    for(int i = 1 ; i <= Q ; ++i) {

	scanf("%d",&K);scanf("%s",s + 1);

	if(K == 1) Insert(i,s,1);

	else if(K == 2) Insert(i,s,-1);

	else {

	    scanf("%d%d%d",&a,&b,&c);

	    int t = (1LL * abs(ans) * a + b) % c;

	    printf("%d\n",ans = Query(s,t));

	}

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}