「THUSC 2016」补退选

题目链接

题目大意

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

解题思路

既然只是简单地查询前缀,我们就建一颗Trie。然后考虑如何解决询问。询问问最早什么时候姓名前缀为S的学生超过了x,于是我们只需在每个节点维护一个单调上升的序列,同时维护时间信息就好了。然后嘛,$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;
}


  Reprint please specify: chy's blog 「THUSC 2016」补退选

 Previous
「THUWC 2017」在美妙的数学王国中畅游 「THUWC 2017」在美妙的数学王国中畅游
题目链接 问题分析首先,有连边删边操作,那么LCT逃不了了。那么如何维护函数信息?注意到题目末尾的提示,结合题目所给的精度要求,我们取前十几项就可以了。那么我们就只需要维护多项式就行。 对于第一种函数$$f(x)=\sin(ax+b)\\\
2019-05-07
Next 
「THUSC 2016」成绩单 「THUSC 2016」成绩单
题目链接 题目大意题面还是比较好理解的。值得注意的是,如果取了中间一段,两边的会连成一段。 解题思路两维的DP看起来是不行的。看到$n$只有$50$,我们 考虑升维。令$F[l][r][A][B]$表示在区间$[l,r]$中,取走一部分,剩
2019-05-02
  TOC