• <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年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

            題目地址:

                  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
             

             

              

            題目分析:

               這個題有很多種方法, 大牛用靜態字典樹....哥不會,只會動態的, 結果  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 大牛的 靜態代碼 :

             

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

             

             

             

            久久r热这里有精品视频| 亚洲综合婷婷久久| 久久婷婷色综合一区二区| 成人午夜精品久久久久久久小说 | 亚洲国产精品综合久久网络| 成人久久精品一区二区三区| 久久国产精品国产自线拍免费| 一本久久a久久精品综合夜夜| 人妻中文久久久久| 精品久久久久香蕉网| 久久人搡人人玩人妻精品首页| 一本久久知道综合久久| 国产精品美女久久久久av爽 | 久久久久亚洲AV成人网人人网站 | 天天躁日日躁狠狠久久| 99久久国产亚洲高清观看2024 | 麻豆av久久av盛宴av| 久久青青草原综合伊人| 久久久久se色偷偷亚洲精品av| 97精品久久天干天天天按摩| 亚洲国产成人久久综合野外| 久久―日本道色综合久久| 久久久一本精品99久久精品88| 91精品国产色综久久| 久久久久无码精品国产不卡| 久久婷婷午色综合夜啪| 久久国产精品偷99| 99久久国产综合精品五月天喷水 | 粉嫩小泬无遮挡久久久久久| 日韩欧美亚洲综合久久影院Ds| 亚洲欧美日韩精品久久| 国产精品9999久久久久| 国内精品伊人久久久久777| 无码人妻少妇久久中文字幕| 国产精品免费久久久久影院| 精品久久一区二区三区| 国产精品久久久久9999高清| 久久狠狠高潮亚洲精品| 久久精品a亚洲国产v高清不卡| 国产aⅴ激情无码久久| 亚洲欧美日韩久久精品第一区 |