最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

当前报道:2022 ICPC 杭州站 K - Master of Both // Trie

来源:博客园

K - Master of Both

题目来源:The 2022 ICPC Asia Hangzhou Regional Programming Contest K题目链接:https://codeforces.com/gym/104090/problem/K

题意


【资料图】

给定 \(n\) 个仅包含小写字母的字符串(\(1 \le |s_i| \le 10^6\),\(1 \le \sum\limits_{i=1}^{n} s_i \le 10^6\)),以及 \(q\) 个询问(\(1 \le q \le 5 \times 10^4\))。

对于每个询问:给出一种字母表,越靠前的字母越小,要求输出该种字母表下,这 \(n\) 个字符串有多少个逆序对,即有多少个 \((i,j)\),满足 \(1\le i < j \le n\),且 \(s_i>s_j\) 。

思路:Trie

首先我们思考下如何比较两个字符串的字典序大小(记为 \(s_i\),\(s_j\)),我们从第一个不相等的字符比较,假设分别为 \(c_i\),\(c_j\),那么若有 \(c_i > c_j\),则 \(s_i > s_j\) 。

也就是说,实际上所有的字符对情况只能是 \(a \le c_i \le z\),且 \(a \le c_j \le z\) 。

我们可以预处理出 \(f_{x,y}\),表示 \(1 \le i < j \le n\) 的有序对中满足 \(s_{i,LCP(\large s_i,s_j)} = x\),\(s_{j,LCP(\large s_i,s_j)} = y\) 的数量。

那么对于每个询问,统计逆序对数量时,若有字母 \(x > y\),答案就可以增加 \(f_{x,y}\) 。

对于边界情况,当 \(s_j\) 为 \(s_i\) 的真前缀时,显然有 \(s_i > s_j\),因此也需要预处理出这类情况 \(f_{x,null}\) 。

预处理 \(f_x,y\) 时,可以利用字典树,从前到后遍历所有字符串,对于每个字符串,先计算后插入。

代码

#include using namespace std;const int N = 1000010;int n, q;int son[N][26], cnt[N], idx;long long f[26][27];char s[N];void insert(char* str){    int p = 0;    for(int i = 0; str[i]; ++ i) {        int u = str[i] - "a";        if(!son[p][u]) son[p][u] = ++ idx;        p = son[p][u];        ++ cnt[p];    }}int main(){    cin >> n >> q;    for(int i = 1; i <= n; ++ i) {        cin >> s;        int p = 0;        for(int k = 0; k < 26; ++ k) {            f[k][s[0]-"a"] += cnt[son[0][k]];        }        for(int j = 0; s[j]; ++ j) {            int u = s[j] - "a";            if(!son[p][u]) break;            p = son[p][u];            for(int k = 0; k < 26; ++ k) {                if(s[j+1]) {                    f[k][s[j+1]-"a"] += cnt[son[p][k]];                }                else f[k][26] += cnt[son[p][k]];            }        }        insert(s);    }    for(int i = 1; i <= q; ++ i) {        char alphabet[26];        cin >> alphabet;        long long ans = 0;        for(int j = 0; j < 26; ++ j) {            ans += f[j][26];            for(int k = 0; k < j; ++ k) {                ans += f[alphabet[j]-"a"][alphabet[k]-"a"];            }        }        cout << ans << "\n";    }    return 0;}

关键词: 也就是说 首先我们 可以利用