hihoCoder #1656 前后缀查询

题目大意

给定 $n$（$n\le 50000$）个由小写英文字母构成的字符串，每个串的长度不超过 10，每个串有一个权值 $v$ （$1\le v\le 100000$）。

回答 $m$（$m\le 50000$）组询问，询问格式为两个字符串 $p,s$，求输入中满足「以 $p$ 为前缀并且以 $s$ 为后缀」的串的最大权值。

解法

我的做法：字典树套字典树。

标程做法：将输入中长为 $k$ 的字符串变成 $k$ 个新字符串；

例子：

abc 变成

a#cba

ab#cba

abc#cba

用所有新串建一棵字典树。

对于查询 $p,s$ ，在字典树中查询 $p+`\#`+ \mathrm{reverse}(s)$ 。

实现要点

字典树的每个节点开长为 26 的数组（可能）会 MLE，可以用「左儿子-右兄弟」方式建树。

Highlights

我写了一个字典树模板类，自认为很 fancy。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<class T>

struct trie{

    struct node{

        char x;

        size_t l, r;

    };

    using val_t = T;

    vector<pair<node,val_t>> a;

    val_t _null;

    trie(){

        a.push_back({});

    }

    size_t size()const {

        return a.size();

    }

    // LC-RS: left-child right-sibling

    size_t get_child(size_t i, char x)const{

        for(i=a[i].first.l; ; i=a[i].first.r){

            if(a[i].first.x == x || !a[i].first.r)

                return i;

        }

    }

    template <typename lambda>

    void insert(const string &s, lambda &&upd){

        size_t i=0;

        upd(a[i].second);

        for(auto x: s){

            auto _i = get_child(i, x);

            if(a[_i].first.x == x)

                i = _i;

            else{

                if(!_i){

                    a[i].first.l=a.size();

                }

                else{

                    a[_i].first.r=a.size();

                }

                i = a.size();

                a.push_back({});

                a.back().first.x = x;

            }

            upd(a[i].second);

        }

    }

    const val_t &operator[](const string &s)const {

        size_t i = 0;

        for(auto x: s){

            i = get_child(i, x);

            if(a[i].first.x != x)

                return _null;

        }

        return a[i].second;

    }

};

trie<trie<int>> a;

int main(){

#ifdef LOCAL

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

#endif

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n, m;

    cin >> n >> m;

    for(int i=0; i<n; i++){

        string s;

        int v;

        cin >> s >> v;

        auto upd = [s, v](auto &val)mutable {

            reverse(s.begin(), s.end());

            val.insert(s, [v](auto &val){val=max(val, v);});

        };

        a.insert(s, upd);

    }

    for(int i=0; i<m; i++){

        string pre, suf;

        cin >> pre >> suf;

        reverse(suf.begin(), suf.end());    // error-prone

        int res = a[pre][suf];

        cout << (res? res: -1) << '\n';

    }

    return 0;

}

代码中用到了 generic lambda：

auto upd = [s, v](auto &val)mutable {

            reverse(s.begin(), s.end());

            val.insert(s, [v](auto &val){val=max(val, v);});

 };

这是 C++ 14 引入的新特性，如果你使用的编译器尚不支持 C++ 14，可以将「lambda 表达式」改成「generic functor」。

巴特西

hihoCoder #1656 前后缀查询

题目大意

解法

实现要点

Highlights

最新文章

热门文章