cf1902E

以一种对新手比较友好的方式写了一下代码和注释
*一定不是因为我是蒟蒻所以只能这么写（

这道题算是比较简单的字典树，理解了字典树就很好做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define int long long
using namespace std;

class trie {
public:
    struct trie* nxt[26];
    int cnt = 0;
    //给字典树放入新字符串
    void ad(string s) {
        trie* tmp = this;
        for (char ch : s) {
            //cout<<ch;
            int i = ch - 'a';
            if (!tmp->nxt[i])
                tmp->nxt[i] = new trie();
            tmp = tmp->nxt[i];
            //在节点上统计数量
            tmp->cnt++;
        }
    }
    /*
    注意！这里返回值是被放弃的字符数量/2

    如字典树中已有以下字符串：
    aaab
    aab
    ab
    a
    假如这里输入s=ab进行查询
    那么在第一个字符'a'节点，cnt=4
    第二个字符'b'节点，cnt=1
    读者可以发现我们相当于是在同一时间同时扫描了所有字符串的第1个字符，然后是第2个……以此类推。这对理解字典树很重要。
    */
    int f(string s) {
        trie* tmp = this;
        int ret = 0;
        for (char ch : s) {
            int i = ch - 'a';
            if (!tmp->nxt[i])
                return ret;
            tmp = tmp->nxt[i];
            ret += tmp->cnt;
        }
        return ret;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    int n;cin >> n;
    string s, sr;
    int sum = 0, ans = 0;
    //这里用了两颗字典树，分别存储正序和倒序字符串
    trie* root = new trie(), * rootr = new trie();
    int k = 0, slen;
    while (n--) {
        //这五行字仅仅是为了后面写的清楚些
        cin >> s;
        reverse(s.begin(), s.end());
        sr = s;
        reverse(s.begin(), s.end());
        slen = s.length();
        /*
        分当前字符串放在前后两种情况更新答案（当前字符串与之前所有字符串的结果）
        这里的k是之前字符串的个数，这里的式子来源于最基本的两个字符串长度相加再减去被放弃的字符数，由此可以推出以下式子
        */
        ans += sum + k * slen - 2 * root->f(sr);
        ans += sum + k * slen - 2 * rootr->f(s);
        //更新当前字符串与它自己的结果
        int i = 0, j = slen - 1;
        while (i <= j && s[i] == s[j])i++, j--;
        if (i <= j)
            ans += slen * 2 - i * 2;
        //结束处理，更新所有字符串总长度和两棵字典树
        root->ad(s);
        rootr->ad(sr);

        sum += slen;
        ++k;
    }
    cout << ans << endl;
    return 0;
}