uva 11732-strcmp()Anyone?悪くないTrieは書きます
3966 ワード
クイズ:http://blog.csdn.net/u013480600/article/details/23122503
私のコードはずっとTLEです.人の家を見た後、1、チェーン式の前の星がいいと思います.2、*depthは各ノードを過ぎるごとに計算するのではなく、この点がいいです.
基本コードです.自分で注釈を付けて、記号を残して、後で書き直します.
この問題は同じくチェーン式の前星のTrieのテンプレートとして使われています.
私のコードはずっとTLEです.人の家を見た後、1、チェーン式の前の星がいいと思います.2、*depthは各ノードを過ぎるごとに計算するのではなく、この点がいいです.
基本コードです.自分で注釈を付けて、記号を残して、後で書き直します.
この問題は同じくチェーン式の前星の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;
}