首页 > 代码库 > CSU1115 最短的名字

CSU1115 最短的名字

题解:

字典树构建,然后dfs一下就可以了

代码:

#include<bits/stdc++.h>#define CLR(x) memset(x,0,sizeof x)using namespace std;const int maxnnode=10000010;const int maxn=100000;int sum;//字母表为全体小写字母的Trie struct Trie{    int ch[maxn][26];    int val[maxnnode];    int sz;//节点总数     void Clear(){sz=1;CLR(ch[0]);CLR(val);}//初始时只有一个根节点     int idx(char c){return c-a;}//字符c的编号     void Insert(const char*s){        int u=0,n=strlen(s);        for(int i=0;i<n;i++){            int c=idx(s[i]);            if(!ch[u][c])//创建新的节点             {                CLR(ch[sz]);                val[sz]=1;//过程中的节点                ch[u][c]=sz++;//新建节点的编号             }            else val[ch[u][c]]++;            u=ch[u][c];        }    }    int Judge(int u,int tmp){        int sum=0;        for(int i=0;i<26;i++){            if(!val[ch[u][i]]) continue;            if(val[ch[u][i]]==1) sum+=tmp;            else  sum+=Judge(ch[u][i],tmp+1);        }        return sum;    }};Trie T;char Line[maxnnode];int main(){    int t,n;    scanf("%d",&t);    while(t--){        scanf("%d",&n);        T.Clear();        for(int i=1;i<=n;i++){            scanf("%s",Line);            T.Insert(Line);        }        sum=0;        printf("%d\n",T.Judge(0,1));    }    return 0;}

 

CSU1115 最短的名字