• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(lèi)(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

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

             

            題目地址:

                  http://acm.hdu.edu.cn/showproblem.php?pid=1671 

            題目描述:

            Phone List

            Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 1733    Accepted Submission(s): 572


            Problem Description
            Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
            1. Emergency 911
            2. Alice 97 625 999
            3. Bob 91 12 54 26
            In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.
             

            Input
            The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
             

            Output
            For each test case, output “YES” if the list is consistent, or “NO” otherwise.
             

            Sample Input
            2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
             

            Sample Output
            NO YES
             

             

              

            題目分析:

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

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

             

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

            /*

            MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(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)帖請(qǐng)注明 : 轉(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)代碼 :

             

            1. #include<cstdio>
            2. #include<cstring>
            3. using namespace std;
            4. const int MAXNODE=500000;
            5. const int BRANCH=10;

            6. int Tree[MAXNODE][BRANCH],SIZE;
            7. bool Key[MAXNODE];
            8. bool Insert(char *str) {
            9.     int Node=0;bool tof=false;
            10.     for (int i=0;str[i];i++){
            11.         int c=str[i]-'0';
            12.         if(Tree[Node][c]==-1){
            13.             Tree[Node][c]=++SIZE;tof=true;
            14.             memset(Tree[SIZE],-1,sizeof(Tree[SIZE]));
            15.         }
            16.         if(Key[Node]) return false;
            17.         Node=Tree[Node][c];
            18.     }
            19.     Key[Node]=true;
            20.     return tof;
            21. }

            22. void Trie(){
            23.     memset(Tree[0],-1,sizeof(Tree[0]));
            24.     SIZE=0;
            25. }

            26. char str[15];
            27. int main()
            28. {
            29.     int t,n;bool tof;
            30.     scanf("%d",&t);
            31.     while(t--){
            32.         memset(Key,false,sizeof(Key));
            33.         Trie();tof=true;
            34.         scanf("%d",&n);
            35.         for(int i=0;i<n;i++){
            36.             scanf("%s",str);
            37.             if(tof){
            38.                 tof=Insert(str);
            39.             }
            40.         }
            41.         if(tof) puts("YES");
            42.         else puts("NO");
            43.     }
            44. }

             

             

             

            亚洲精品高清国产一久久| 久久精品免费一区二区三区| 久久噜噜电影你懂的| 国产成年无码久久久久毛片| 婷婷五月深深久久精品| 少妇高潮惨叫久久久久久| 久久精品国产亚洲AV无码娇色| 久久99国内精品自在现线| 曰曰摸天天摸人人看久久久| 久久www免费人成看国产片| 欧美午夜A∨大片久久| 色欲久久久天天天综合网| 国产精品美女久久久| AAA级久久久精品无码区| 一本色道久久88综合日韩精品| 伊人久久大香线焦AV综合影院| a高清免费毛片久久| 日韩亚洲国产综合久久久| 久久亚洲欧美国产精品| 国内精品久久久久久久涩爱| 午夜精品久久久久9999高清| 精品久久久久久无码中文字幕一区| 999久久久国产精品| 无码人妻久久一区二区三区免费丨 | 久久亚洲精品无码播放| 久久婷婷五月综合成人D啪| 99久久无码一区人妻a黑| 久久人妻少妇嫩草AV蜜桃| 久久久久久久97| 精品久久亚洲中文无码| 伊人久久大香线蕉影院95| 漂亮人妻被黑人久久精品| 久久精品国产第一区二区| 99久久精品毛片免费播放| 久久狠狠爱亚洲综合影院| 国产伊人久久| 丁香五月综合久久激情| 男女久久久国产一区二区三区| 日韩久久久久中文字幕人妻| 久久精品国产亚洲精品2020| 久久久久久伊人高潮影院|