「THUSC 2016」补退选

题目链接

题目大意

题意应该算是比较明了。只是有一个坑点在于$(a\times |ANS|+b)\mod c$会爆$int$。

解题思路

既然只是简单地查询前缀，我们就建一颗Trie。然后考虑如何解决询问。询问问最早什么时候姓名前缀为S的学生超过了ｘ，于是我们只需在每个节点维护一个单调上升的序列，同时维护时间信息就好了。然后嘛，$vector$能完美地解决这个问题。空间最多是$n*len$的。

参考程序

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 100010;
const int MaxLen = 60;
const int AlphaSize = 10;
struct rec {
    int Val, Time;
    bool operator < ( const rec Other ) const {
        return Val < Other.Val;
    }
};
struct trie {
    int To[ AlphaSize ], Num;
    vector< rec > Rec;
};
trie Trie[ Maxn * MaxLen ];
int n, Used, Root = 0, LastAns = 0, Len;
char Ch[ MaxLen ];

void Insert( int k ) {
    int T = Root;
    for( int i = 0; i < Len; ++i ) {
        int t = Ch[ i ] - 'a';
        if( !Trie[ T ].To[ t ] ) Trie[ T ].To[ t ] = ++Used;
        T = Trie[ T ].To[ t ];
        ++Trie[ T ].Num;
        if( Trie[ T ].Rec.empty() || Trie[ T ].Rec[ Trie[ T ].Rec.size() - 1 ].Val < Trie[ T ].Num ) 
            Trie[ T ].Rec.push_back( ( rec ){ Trie[ T ].Num, k } );
    }
    return;
}

void Delete() {
    int T = Root;
    for( int i = 0; i < Len; ++i ) {
        int t = Ch[ i ] -'a';
        T = Trie[ T ].To[ t ];
        --Trie[ T ].Num;
    }
    return;
}

int Query( int k ) {
    int T = Root;
    for( int i = 0; i < Len; ++i ) {
        T = Trie[ T ].To[ Ch[ i ] - 'a' ];
        if( !T ) return -1;
    }
    int Temp = upper_bound( Trie[ T ].Rec.begin(), Trie[ T ].Rec.end(), ( rec ){ k, 0 } ) - Trie[ T ].Rec.begin();
    if( Temp == ( int )Trie[ T ].Rec.size() ) return -1;
    return Trie[ T ].Rec[ Temp ].Time;
}

int main() {
    scanf( "%d", &n );
    for( int i = 1; i <= n; ++i ) {
        int Opt; scanf( "%d", &Opt );
        scanf( "%s", Ch );
        Len = strlen( Ch );
        if( Opt == 1 ) Insert( i );
        if( Opt == 2 ) Delete();
        if( Opt == 3 ) {
            long long a, b, c;
            scanf( "%lld%lld%lld", &a, &b, &c );
            a = ( a * abs( LastAns ) % c + b ) % c;
            LastAns = Query( a );
            printf( "%d\n", LastAns );
        }
    }
    return 0;
}