這個題有很多種方法, 大牛用靜態(tài)字典樹....哥不會,只會動態(tài)的, 結(jié)果  MLE 了20幾次...  , 很糾結(jié)的是,我的結(jié)構體用的是局部變量, 到現(xiàn)在還是

沒明白為什么他不會自動釋放...最后加了動態(tài)數(shù)組的釋放才A掉...............  然后嘗試了一下 STL ...比動態(tài)字典還快......

動態(tài)字典代碼:

/*

MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋

          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原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋

          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 大牛的 靜態(tài)代碼 :