• <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)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

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

             

              

            題目分析:

               這個題有很多種方法, 大牛用靜態(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)代碼 :

             

            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片无码下载蜜桃 | 综合久久一区二区三区| 久久香综合精品久久伊人| 久久亚洲国产精品成人AV秋霞 | 中文字幕久久亚洲一区| 久久夜色精品国产www| 精品无码久久久久久久动漫| 97超级碰碰碰碰久久久久| 91久久婷婷国产综合精品青草| 久久久久人妻一区精品色| 久久久久亚洲AV无码麻豆| 久久w5ww成w人免费| 99久久免费国产精精品| 狠狠干狠狠久久| 国产精品综合久久第一页| 久久久不卡国产精品一区二区 | 久久精品国产秦先生| 热久久这里只有精品| 久久激情五月丁香伊人| 一级女性全黄久久生活片免费| 久久妇女高潮几次MBA| 久久精品人人做人人妻人人玩| 国产精品福利一区二区久久| 国产激情久久久久影院老熟女| 理论片午午伦夜理片久久| 亚洲va久久久噜噜噜久久狠狠| 国产成人久久激情91| 无码人妻少妇久久中文字幕 | 久久久久人妻一区精品色| AA级片免费看视频久久| 人人狠狠综合久久亚洲| 亚洲精品无码久久千人斩| 天天久久狠狠色综合| 色妞色综合久久夜夜| 嫩草影院久久99| 国产精品亚洲综合久久| 国产成人AV综合久久| 亚洲乱码精品久久久久.. | 久久精品女人天堂AV麻| 中文字幕乱码久久午夜|