题意：
给你n个字符串。要你两两进行比较。求总共的比较次数。
思路：
用trie去优化。
细心观察可以发现，可以边读入边计算ans。
-
每读入一个word进trie里时，就可以计算
不过中间的逻辑关系要理清。 -
本题结点的val，改为记录字符串的个数。
-
当insert一个word时，即遍历word时。假设当前结点为u，那么儿子为v。此时就可以计算答案。
ans+=(val[u]-val【ch【u】【c】】) x （len-1） x 2+
(val[u]-val【ch【u】【c】】)（这一步运用了容斥）
化简一下
ans+=(val[u]-val【ch【u】【c】】) x (（len-1） x 2+1) -
最后遍历完word时，还要考虑一下，之前是否有和这个单词相同的单词。或者当前word是之前读入的前缀。这两种情况的答案是不同的。这里就加一个变量记录当前结点是几个字符串的结尾。
反思：
中间的逻辑没理清楚，导致一直wa。。。qwq（康复训练还在继续）。
AC
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
using namespace std;
typedef long long ll;
const int maxnode=4000*1000+10;///最多有多少层
const int sigma_size=100;///字母的话就是26
struct Trie{
int ch[maxnode][sigma_size];///ch[u][0]代表这个结点不存在int is_end[maxnode];ll val[maxnode];///结点的权值(相当于标记是否为一个字符串的最后一个元素)int sz;///结点总数void clear(){
sz=1; memset(ch[0],0,sizeof(ch[0]));memset(val,0,sizeof(val));memset(is_end,0,sizeof(is_end)); }// Tire(){sz=1; memset(ch[0],0,sizeof(ch[0])); }///初始化第一个根结点int idx(char c){
if(isalpha(c)){
if(c>='a')return c-'a';///'a'的ascll码在后面else return c-'A'+26;}return c-'0'+52;}/////插入字符串s，附加信息v（权值）。注意v必须非0，因为0代表“本结点不是单词结点”void insert(char *s, ll &tmp){
int u=0, len_s=strlen(s);tmp=0;for(int i=0; i<len_s; i++){
int c=idx(s[i]);if(!ch[u][c]){
///结点不存在memset(ch[sz],0,sizeof(ch[sz]));val[sz]=0;///中间结点的附加信息为0.ch[u][c]=sz++;///新建结点}tmp+=(val[u]-val[ch[u][c]])*2*i+(val[u]-val[ch[u][c]]);val[u]++;u=ch[u][c];///往下走。//cout<<u<<endl;}// cout<<tmp<<endl;tmp+=(ll)is_end[u]*(len_s+1)*2;tmp+=(val[u]-is_end[u])*(2*len_s+1);is_end[u]++;val[u]++;///最后一个字符的附加信息为v。}
}trie;
int num;
ll work(){
char s[1100];ll ans=0,tmp;For(i,1,num){
scanf("%s", s);trie.insert(s,tmp);ans+=tmp;}return ans;
}
int main()
{
int kase=0;while(scanf("%d", &num)&&num){
trie.clear();printf("Case %d: %lld\n", ++kase,work());}return 0;
}
/* 2 a b 4 cat hat mat sir 0 */