• <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. }

             

             

             

            久久综合噜噜激激的五月天| 亚洲午夜久久久久久噜噜噜| 色婷婷综合久久久久中文字幕| 性高湖久久久久久久久AAAAA| 四虎国产精品成人免费久久| 99久久er这里只有精品18| AAA级久久久精品无码区| 少妇无套内谢久久久久| AV色综合久久天堂AV色综合在| 久久精品国产一区二区三区不卡| 国内高清久久久久久| 国产 亚洲 欧美 另类 久久| 性欧美丰满熟妇XXXX性久久久| 亚洲综合精品香蕉久久网97| 日本久久久久亚洲中字幕| 久久激情亚洲精品无码?V| 国产69精品久久久久777| 伊人久久大香线蕉综合热线| 国产精品99久久久久久猫咪| 欧美精品久久久久久久自慰| 久久只这里是精品66| 久久精品亚洲精品国产欧美| 久久精品国产亚洲欧美| 国产精品99久久99久久久| 久久精品极品盛宴观看| 久久夜色精品国产亚洲av| 999久久久免费精品国产| 午夜精品久久久久久中宇| 亚洲国产成人精品久久久国产成人一区二区三区综 | 色偷偷88888欧美精品久久久| 久久精品成人免费观看97| 日韩一区二区久久久久久| 国产精品久久国产精麻豆99网站 | 久久精品国内一区二区三区 | 久久本道久久综合伊人| 国产精品VIDEOSSEX久久发布| 久久96国产精品久久久| 久久99热精品| 成人精品一区二区久久久| 青青草原综合久久大伊人精品| 精品熟女少妇a∨免费久久|