UVa11732 Strcmp,Anyone?[Trie树]

本文主要是介绍UVa11732 Strcmp,Anyone?[Trie树]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1
题目2
题意：给定判断方式和字符串，输出字符串两两比较的次数；
分析：如果使用正常的字典树，空间复杂度为4000*1000*26，果断爆，但我静态数组没有爆反而RE了，不知道为什么，可能UVa没有MLE？等会试一下；然后还会超时，因为每个节点都要枚举，是4000*1000*26*26，，不过机智一点应该不会超时？就每次insert顺便求了。所以，采用树的压缩算法（左孩子右兄弟）。
第一次写多叉转二叉，本来以为会很麻烦，没想到比普通程序还要短一点，所以基本功要练扎实啊，这些都是基础的。
然后就是经验之谈，在明知道不是正解的情况下，尤其是MLE这么一开始就知道的问题，就不要写程序了，免得浪费自己的时间精力和心情。还有就是调试的时候一定要从逻辑入手，数据是弄不完的，太浪费时间了，理一下自己的思路看有哪些特殊情况没有处理，如果还是找不出来问题再自己举特殊例子调。这种类似递推的题一定要把公式的适用情况和逻辑关系理清楚；
程序：

#include<iostream>#include<cstdio>#include<cstring>#define clr(x) memset(x,0,sizeof(x))using namespace std;const int maxn=4000*1000+5;int fr[maxn],tov[maxn],inde,len,n,cnt;
char a[1005],ch[maxn];
long long ans,tot[maxn],sig[maxn];
void init()
{ans=0;inde=0;clr(fr);clr(tov);clr(tot);clr(ch);clr(sig);
}
void build(int u,long long dep)
{ans+=tot[u]*2LL;//ans-=sig[u];if(dep==len){tot[u]++;ans+=sig[u];sig[u]++;return;}tot[u]++;for(int i=fr[u];i;i=tov[i])if(ch[i]==a[dep]){build(i,dep+1);return;}tov[++inde]=fr[u];fr[u]=inde;ch[inde]=a[dep];build(inde,dep+1);
}
int main()
{freopen("UVa11732.in","r",stdin);freopen("Uva11732.out","w",stdout);for(scanf("%d",&n);n;scanf("%d",&n)){init();printf("Case %d: ",++cnt);for(int i=1;i<=n;i++){scanf("%s",a);len=strlen(a);build(0,0);}printf("%lld\n",ans-tot[0]*(tot[0]-1LL)/2LL);}return 0;
}