題目分析:
這個題有很多種方法, 大牛用靜態字典樹....哥不會,只會動態的, 結果 MLE 了20幾次...
, 很糾結的是,我的結構體用的是局部變量, 到現在還是
沒明白為什么他不會自動釋放...最后加了動態數組的釋放才A掉............... 然后嘗試了一下 STL ...比動態字典還快......
動態字典代碼:
/*
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
http://www.cnblog.com/MiYu
Author By : MiYu
Test : 1
Program : 1671
*/
#include <iostream>
using namespace std;
typedef struct dict DIC;
int f = 0;
DIC *root = NULL;
struct dict {
dict (){ n = 0; flag = false;memset ( child , 0 , sizeof ( child ) ); }
~dict () { del ( root ); }
static void insert ( char *ins )
{
DIC *cur = root,*now;
int len = strlen ( ins );
if ( len == 0 ) return ;
for ( int i = 0; i != len; ++ i )
{
if ( cur->flag || ( i == len - 1 && cur->child[ ins[i] - '0' ] != NULL ) )
f = 1;
if ( cur->child[ ins[i] - '0' ] != NULL )
{
cur = cur->child[ ins[i] - '0' ];
cur->n ++;
}
else
{
now = new DIC;
cur->child[ ins[i] - '0' ] = now;
now->n ++;
cur = now;
}
}
cur->flag = true;
}
void del ( DIC * node )
{
if ( node == NULL )
return;
for ( int i = 0; i != 10; ++ i )
{
if ( node->child[i] != NULL )
del ( node->child[i] );
}
free ( node );
}
private:
DIC *child[10];
int n;
bool flag;
};
char num[11];
int main ()
{
int T,N;
scanf ( "%d",&T );
while ( T -- )
{
DIC dict;
root = &dict;
f = 0;
scanf ( "%d",&N );
for ( int i = 0; i != N; ++ i )
{
scanf ( "%s",num );
if ( f == 0 ) dict.insert ( num );
}
puts ( f ? "NO" : "YES" );
}
return 0;
}
STL 代碼 :
/*
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
http://www.cnblog.com/MiYu
Author By : MiYu
Test :
Program :
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
char num[11];
bool cmp ( const string &a, const string &b )
{
return strcmp ( a.c_str(), b.c_str() ) < 0;
}
int main ()
{
int T,N;
scanf ( "%d",&T );
while ( T -- )
{
int f = 0;
scanf ( "%d",&N );
vector < string > vec;
for ( int i = 0; i != N; ++ i )
{
scanf ( "%s",num );
vec.push_back ( string ( num ) );
}
sort ( vec.begin(), vec.end(),cmp1 );
for ( int i = 1; i < N; ++ i )
{
if ( vec[i].find ( vec[i-1] ) == 0 )
{
f = 1;
break;
}
}
puts ( f ? "NO" : "YES" );
}
return 0;
}
AMB 大牛的 靜態代碼 :
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int MAXNODE=500000;
- const int BRANCH=10;
- int Tree[MAXNODE][BRANCH],SIZE;
- bool Key[MAXNODE];
- bool Insert(char *str) {
- int Node=0;bool tof=false;
- for (int i=0;str[i];i++){
- int c=str[i]-'0';
- if(Tree[Node][c]==-1){
- Tree[Node][c]=++SIZE;tof=true;
- memset(Tree[SIZE],-1,sizeof(Tree[SIZE]));
- }
- if(Key[Node]) return false;
- Node=Tree[Node][c];
- }
- Key[Node]=true;
- return tof;
- }
- void Trie(){
- memset(Tree[0],-1,sizeof(Tree[0]));
- SIZE=0;
- }
- char str[15];
- int main()
- {
- int t,n;bool tof;
- scanf("%d",&t);
- while(t--){
- memset(Key,false,sizeof(Key));
- Trie();tof=true;
- scanf("%d",&n);
- for(int i=0;i<n;i++){
- scanf("%s",str);
- if(tof){
- tof=Insert(str);
- }
- }
- if(tof) puts("YES");
- else puts("NO");
- }
- }