POJ3630

Tire树裸题，一开始写动态的字典树，然后TLE，每次new一个新节点耗费时间较多。后来改成数组模拟的。

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std ; 
const int maxN = 10010 ; struct stringStruct {char str[ 20 ] ; int len ; 
}ss[ maxN ] ; struct tireNode {int cnt ; bool last ; struct tireNode *next[ 10 ] ; tireNode ( ) {cnt = 0 ; last = false; memset ( next , 0 , sizeof ( next ) ) ;}
};bool cmp ( stringStruct a , stringStruct b ) {return a.len < b.len ; 
}bool insert ( tireNode *root , char str[ ] ) {int len = strlen ( str ) ; tireNode *cur = root ;for ( int i=0 ; i<len ; ++i ) {char ch = str[ i ] - '0' ; if ( cur -> next[ ch ] == NULL ) {tireNode* newNode = new tireNode ; cur -> next[ ch ] = newNode ; } if ( cur -> last ) return true ; cur = cur -> next[ ch ] ;cur->cnt++ ; }cur -> last = true ;return false ; 
}int main ( ) {int T ; for ( scanf( "%d" , &T ) ; T ; --T ) {tireNode* root = new tireNode ; int N ; scanf ( "%d\n" , &N ) ;for ( int i=1 ; i<=N ; ++i ) {char ch = getchar ( ) ;int lenn = 0 ; while ( ch != '\n' ) {ss[ i ].str[ lenn++ ] = ch ; ch = getchar ( ) ;}ss[ i ].len = lenn ; } sort ( ss + 1 , ss + N + 1 , cmp ) ; bool flag = true ; for ( int i=1 ; i<=N ; ++i ) {if ( insert ( root , ss[ i ].str ) ) {flag = false ; break ; }}if ( flag ) printf ( "YES\n" ) ;else printf ( "NO\n" ) ;}return 0 ; 
}

#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std ; 
const int maxN = 100100 ;
typedef long long LL ; struct stringStruct {char str[ 20 ] ; int len ; 
}ss[ maxN ] ; int trie[ maxN ][ 10 ] ; 
bool end[ maxN ] ; 
bool cmp ( stringStruct a , stringStruct b ) {return a.len < b.len ; 
}int _cnt ;bool insert ( char str[ ] ) {int cur = 1 , len = strlen ( str + 1 ) ;  for ( int i=1 ; i<=len ; ++i ) {int ch = str[ i ] - '0' ; if ( !trie[ cur ][ ch ] ) trie[ cur ][ ch ] = ++_cnt ; if ( end[ cur ] ) return true ; cur = trie[ cur ][ ch ] ; }end[ cur ] = true ; return false ; 
}int main ( ) {int T , N ; for ( scanf ( "%d" , &T ) ; T ; --T ) {memset ( trie , 0 , sizeof ( trie ) ) ;memset ( end , false , sizeof ( end ) ) ;_cnt = 1 ; scanf ( "%d" , &N ) ; for ( int i=1 ; i<=N ; ++i ) {scanf ( "%s" , ss[ i ].str + 1 ) ; ss[ i ].len = strlen ( ss[ i ].str + 1 ) ;}sort ( ss + 1 , ss + N + 1 , cmp ) ; bool flag = true ; for ( int i=1 ; i<=N ; ++i ) {if ( insert ( ss[ i ].str ) ) {flag = false ; break ; } }if ( flag )printf ( "YES\n" ) ; else printf ( "NO\n" ) ; }    return 0 ; 
}