uva 11732 - strcmp() Anyone? 괜 찮 은 퀴즈.

문제 풀이: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
",++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
",++icase,solve(0,n)-n*(n-1));
    }
    return 0;
}