CF1902E Collapsing Strings 题解

FFTotoro · 2023-12-10 19:43:16 · 题解

字典树板子题。

正难则反，考虑所有字符串对的长度和之和减去重叠部分长度之和得到答案。

重叠部分的长度只需将所有字符串正着插入字典树中，令每个结点的权值为经过的次数。

查询时反着询问经过所有结点的权值和即可。

因为空间限制 256\mathrm{MiB}，所以开 2.6\times 10^7 的 int 数组不会爆。

放代码：

#include<bits/stdc++.h>
using namespace std;
int t[1000001][26],w[1000001],o;
void insert(string s){
  int p=0;
  for(char i:s)
    if(!t[p][i-97])w[p=t[p][i-97]=++o]=1;
    else w[p=t[p][i-97]]++;
} // 插入
int f(string s){
  int p=0; long long c=0;
  for(char i:s)
    if(!t[p][i-97])break;
    else c+=w[p=t[p][i-97]];
  return c;
} // 查询
int main(){
  ios::sync_with_stdio(false);
  int n; long long l=0,c=0; cin>>n;
  vector<string> a(n);
  for(auto &i:a)cin>>i,l+=i.length(),insert(i);
  for(auto &i:a)reverse(i.begin(),i.end()),c+=f(i);
  cout<<(l*n-c<<1)<<endl; // 答案
  return 0;
}