https://codeforces.com/contest/1902/problem/E
题目大意
给出 $n \ (\le 10^6)$ 个字符串,且 $\sum |S_i| \le 10^6$。两个串的运算 $C(a, b)$ 规则如下:
- $a$ 为空则 $C(a, b) = b$
- $b$ 为空则 $C(a, b) = a$
- 若 $a[|a| - 1] = b[0]$ 即 $a$ 的末尾字符与 $b$ 的开头字符相同则 $C(a, b) = C(a', b')$,$a'$ 为 $a$ 去掉尾字符的串,$b'$ 为 $b$ 去掉首字符的串。
- 其他情况:$C(a, b) = a + b$ 即 $a$ 与 $b$ 直接拼接。
问 $\sum_i \sum_j |C(S_i, S_j)|$。
简要题解
考虑枚举串 $s_i$ 相当于我们要知道,$s_i$ 的末尾和多少串的前缀重复。于是思路很直观的把所有串插到字典树里,之后用每个串反着查询减去这部分贡献即可。
复杂度
$T$:$O(\sum(S_i))$
$S$:$O(\sum(S_i))$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename T = char, T Base = 'a', int Sigma = 26,
size_t PRE_ALLO = 100000>
struct Trie {
struct TN {
int ch[Sigma];
int cnt;
};
vector<TN> tn;
Trie() : tn(2) { tn.reserve(PRE_ALLO); }
void init() { tn.resize(1); newnode(); }
int newnode() { tn.emplace_back(); return tn.size() - 1; }
int append(int o, T c) {
int cc = c - Base;
if (!tn[o].ch[cc]) { tn[o].ch[cc] = newnode(); }
return tn[o].ch[cc];
}
};
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
Trie trie;
for (int i = 0; i < n; i++) {
int u = 1;
for (char c : s[i]) {
u = trie.append(u, c);
trie.tn[u].cnt++;
}
}
LL ans = 0;
for (int i = 0; i < n; i++) {
ans += 1LL * n * s[i].length();
}
ans *= 2;
// cerr << ans << '\n';
for (int i = 0; i < n; i++) {
int u = 1;
for (int j = s[i].length() - 1; j >= 0; j--) {
int c = s[i][j] - 'a';
if (!trie.tn[u].ch[c]) break;
u = trie.tn[u].ch[c];
ans -= trie.tn[u].cnt * 2;
}
// cerr << ans << '\n';
}
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Robot Queries - Educational Codeforces Round 159 (Rated for Div. 2)