题解：http://blog.csdn.net/u013480600/article/details/23122503
我的代码一直TLE,,,看了人家的之后，认为1、链式前向星比較好，2、*depth而不是每过一个节点就计算，这一点非常好
我是基本copy别人的代码，自己加了凝视，留个记号，随后重写，
这道题相同作为链式前向星的Trie的模板
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std;
#define ll long long
const int MAXN=4002*1002+100; struct Trie
{
int head[MAXN];//其值为在边集的下标
int next[MAXN];//next[j]第j条边的下一条边在边集的下标
int tot[MAXN];
char str[MAXN];//相当于边集了 边存储字符
int sz;//head下标的上界,也相当于节点
ll ans;
void clear()
{
ans=0;
sz=1;
head[0]=next[0]=tot[0]=0; }
void insert(char *s)
{
int n=strlen(s),u=0;
tot[u]++;
for(int i=0;i<=n;i++)//空字符也插入
{
bool found=false;
for(int j=head[u];j;j=next[j])
if(str[j] == s[i])
{
u=j;
found=true;
break;
}
if(!found)//节点不存在
{
next[sz]=head[u];
head[u]=sz; head[sz]=0;//
tot[sz]=0;//新的节点还没有连边
str[sz]=s[i];//初始化边信息，边存储字符
u=sz++;//u存储新的子结点
}
tot[u]++;
}
}
void dfs(int dep, int u)
{
if(!head[u])//到了叶子节点
{
ans+=tot[u]*(tot[u]-1)*dep;
}
else
{
int sum=0;
for(int v=head[u];v;v=next[v]) //**
sum+=tot[v]*(tot[u]-tot[v]);//**
ans+= sum/2*(dep*2+1);//这里我自己做的时候没有想到，，，，事实上分叉后跟分叉前都能够用上面标注**的方法计算
for(int v=head[u];v;v=next[v])
dfs(dep+1,v);
}
}
ll cal()
{
ans=0;
dfs(0,0);
return ans;
}
};
Trie trie;
char word[1000+100];
int main()
{ int icase=0,n;
while(scanf("%d",&n) && n)
{
trie.clear();
for(int i=0;i<n;i++)
{
scanf("%s",word);
trie.insert(word);
}
printf("Case %d: %lld\n",++icase,trie.cal());
}
return 0;
}
我的tle的代码 随后改动
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std; #define ll long long const int N = 4011*1000+10;
const int tk = 75;
const int tb = '0'; // tk叉; 起始字母为tb;
int top, tree[N][tk + 2]; // N: 最大结点个数 top: 第一层有多少节点
char str[1010];
void init(){
top = 1;
memset(tree[0], 0, sizeof(tree[0]));
} void Insert(char*s, int Rank = 1){
int rt, nxt;
for(rt = 0; *s; rt = nxt, ++s) {
nxt = tree[rt][*s - tb]; if(0 == nxt) {//没被使用时插入
tree[rt][*s - tb] = nxt = top;
memset(tree[top], 0, sizeof(tree[top]));
top++;
}
tree[nxt][tk]++;//其值表示有多少单词经过
}
tree[rt][tk+1] = Rank;//1表示存在0表示不存在，也能够赋予其其它含义
} ll solve(int rt,int last)
{
if(tree[rt][tk] <= 1)return 0;
//到结尾仅仅须要比較一次，假设仅仅有一个，也仅仅须要比較一次
ll ans=0;
for(int i=0;i<tk;i++)
if(tree[rt][i])
{
ans=ans+tree[tree[rt][i]][tk]*(last-tree[tree[rt][i]][tk]);//计算子树森林
} ans/=2;
for(int i=0;i<tk;i++)
{
if(tree[rt][i])
{
ans+=solve(tree[rt][i],tree[tree[rt][i]][tk]);
} }
//return ans+2*C[tree[rt][tk]][2];
return ans+tree[rt][tk]*(tree[rt][tk]-1);
}
int main()
{
freopen("uva11732.txt","r",stdin);
int icase=0,n,len;
//calC();
while(scanf("%d",&n)==1 && n)
{
init();
tree[0][tk]=n;
for(int i=0;i<n;i++)
{
scanf("%s",str);
Insert(str);
} printf("Case %d: %lld\n",++icase,solve(0,n)-n*(n-1));
}
return 0;
}