记录编号	431938	评测结果	AAAAAAAAAA
题目名称	2695.strcmp()函数	最终得分	100
用户昵称	joel	是否通过	通过
代码语言	C++	运行时间	1.020 s
提交时间	2017-08-02 14:58:35	内存使用	7.07 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int M=1000+10;
class Node//左孩子右兄弟表示法
{
public:
	Node *LeftChild,*RightBrother;
	char c;
	int size;//以当前结点为根的子树上叶节点的个数
	Node():LeftChild(NULL),RightBrother(NULL),c(' '),size(0){}
};
class Trie
{
public:
	Node* root;//根节点
	long long ans;
	Trie():root(NULL),ans(0){}
	
	void INS(Node *p,const char *s)//插入字符串
	{
		int lens=strlen(s);
		Node* v;
		p->size++;//叶子结点数+1
		for(int i=0;i<=lens;i++)//在众多子节点中查找s[i]
		{
			bool found=false;
			for(v=p->LeftChild;v!=NULL;v=v->RightBrother)
				if(v->c==s[i])
				{
					found=true;
					break;
				}
			if(!found)//没有找到建立新节点
			{
				v=new Node;
				v->size=0;
				v->LeftChild=NULL;
				v->RightBrother=p->LeftChild;
				p->LeftChild=v;//成为父节点的第一个孩子
				v->c=s[i];
			}
			p=v;//往下一层走
			p->size++;
		}
	}
	
	void dfs(int depth,Node *p)
	{
		if(p->LeftChild==NULL)//到叶节点时比较结束，比较次数为以叶节点为结束的单词个数x*(x-1)*单词长度
			ans+=p->size*(p->size-1)*depth;
		else
		{
			int sum=0;//sum代表需要比较的单词个数，即叶节点个数
			for(Node* i=p->LeftChild;i!=NULL;i=i->RightBrother)
				sum+=i->size*(p->size - i->size);//每颗子树都要与其他任意一颗子树比较
			ans+=sum/2*(2*depth+1);//因为算了两次所以先/2,每次比较最小代价为2*depth+1
			for(Node* i=p->LeftChild;i!=NULL;i=i->RightBrother)
				dfs(depth+1,i);
		}
	}
	
	long long Count()
	{
		ans=0;
		dfs(0,root);
		return ans;
	}
};
char s[M];
int main()
{
	freopen("strcmp.in","r",stdin);
	freopen("strcmp.out","w",stdout);
	int kase=1,n;
	while(scanf("%d",&n)&&n)
	{
		Trie T;
		T.root=new Node;
		for(int i=1;i<=n;i++)
		{
			scanf("%s",s);
			T.INS(T.root,s);
		}
		printf("Case %d: %lld\n", kase++, T.Count());
	}
	return 0;
}