Trie 字典树（附数据生成程序）
题意很好懂，就问一堆单词两两比较要多少次。
不过很忧伤的是卡优化了。写了个数据生成，然后我跟别人程序比，用时大概是别人的一倍。
别人635ms 过了。我就TLE…… 问题是2000ms啊。给跪了。
附数据生成程序，各位可以生成数据看看，愿不要TLE。
我的TLE了……：
#include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; int n,m; LL ans; struct Trie { int word[4001*1001][26*2+11]; int sz,cot; int ex[4001*1001]; int fin[4001*1001]; void intTrie() { sz=1; cot=1; memset(word[0],0,sizeof(word[0])); ex[0]=0; fin[0]=0; } int shift(char s) { int c=0; if(s>='a'&&s<='z') c=s-'a'; else if(s>='A'&&s<='Z') c=s-'A'+26; else if(s>='0'&&s<='9') c=s-'0'+52; return c; } int insert(char *s) { int u=0,c; ans+=ex[0]; ex[0]++; for(int i=0; s[i]!='\0'; i++) { c=shift(s[i]); if(!word[u][c]) { memset(word[sz],0,sizeof(word[sz])); ex[sz]=0; fin[sz]=0; word[u][c]=sz++; } u=word[u][c]; ans+=ex[u]*2; ex[u]++; } ans+=fin[u]; fin[u]++; } }wo; int main() { // freopen("in.txt","r",stdin); // freopen("1.txt","w",stdout); char str[1011]; int nn=1; while(scanf("%d",&n),n) { wo.intTrie(); ans=0; for(int i=0; i 数据生成： #include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; time_t t; void build() { t++; srand(t); int n=rand()%1000; printf("%d\n",n); while(n--) { t++; srand(t); int len=rand()%1000+1; for(int i=0;i
#include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; time_t t; void build() { t++; srand(t); int n=rand()%1000; printf("%d\n",n); while(n--) { t++; srand(t); int len=rand()%1000+1; for(int i=0;i