有点好同学 阅读(102) 评论(0)

博客第一篇写在11月1号,果然die die die die die alone~

一道不太难的题,白书里被放到排序这一节,半年前用快排A过一次,但是现在做的时候发现可以用字典树加深搜,于是乐呵呵的开始敲了,后来被卡了两天,一直以为算法错了,最后发现是输出答案时忘了回溯,这问题之前没怎么注意过,也算不小的收获。

字典树A了之后换sort来写,没想到快排效率更高,时间减少了一半,在POJ上A了之后重新在UVA上提交,居然WA了,调试半个小时,发现是变长数组的问题,看来UVA上的编译器对c99的支持不太好。

虽然有点水题的感觉,但是收获不小:。

1.DFS处理的答案的时候要考虑是否回溯

2.更深理解哈希

3.VLA慎用

 

UVA上的代码如下,POJ上的和UVA有点不同,是单组输入,但算法是一样的

 

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 
  5 struct    trie
  6 {
  7     struct    trie    * next[10];
  8     int        count;
  9 };
 10 struct    trie    * ROOT = NULL;
 11 char    RULE[] = {'2','2','2','3','3','3','4','4','4','5','5','5','6','6','6','7','7','7','7','8','8','8','9','9','9','9'};
 12 char        BOX[200];
 13 int        FLAG;
 14 
 15 void    insert(char * s);
 16 void    dfs(struct trie * temp,int len);
 17 int    main(void)
 18 {
 19     int    t,n,len;
 20     char    s[200],number[200];
 21 
 22     scanf("%d",&t);
 23     while(t --)
 24     {
 25         FLAG = 1;
 26         ROOT = (struct trie *)malloc(sizeof(struct trie));
 27         for(int i = 0;i < 10;i ++)
 28             ROOT -> next[i] = NULL;
 29         ROOT -> count = 0;
 30 
 31         scanf("%d",&n);
 32         while(n --)
 33         {
 34             len = 0;
 35             
 36             scanf("%s",s);
 37             for(int i = 0;s[i];i ++)                //转化为纯数字形式
 38             {
 39                 if(s[i] >= '0' && s[i] <= '9')
 40                     number[len ++] = s[i];
 41                 else    if(s[i] >= 'A' && s[i] <= 'Z')
 42                     number[len ++] = RULE[s[i] - 'A']; 
 43             }
 44             number[len] = '\0';
 45             insert(number);
 46         }
 47         dfs(ROOT,0);
 48         if(FLAG)
 49             puts("No duplicates.");
 50         puts("");
 51     }
 52 
 53     return    0;
 54 }
 55 
 56 void    insert(char * s)                            //trie插入函数
 57 {
 58     struct    trie    * temp = ROOT;
 59 
 60     for(int i = 0;s[i];i ++)
 61         if(temp -> next[s[i] - '0'])
 62             temp = temp -> next[s[i] - '0'];
 63         else
 64         {
 65             temp -> next[s[i] - '0'] = (struct trie *)malloc(sizeof(struct trie));
 66             for(int j = 0;j < 10;j ++)
 67                 temp -> next[s[i] - '0'] -> next[j] = NULL;
 68             temp -> next[s[i] - '0'] -> count = 0;
 69 
 70             temp = temp -> next[s[i] - '0'];
 71         }
 72     temp -> count ++;
 73 
 74     return    ;
 75 }
 76 
 77 void    dfs(struct trie * temp,int len)                        //深搜输出
 78 {
 79     for(int i = 0;i < 10;i ++)
 80         if(temp -> next[i])
 81         {
 82             BOX[len] = i + '0';
 83             len ++;
 84             if(temp -> next[i] -> count >= 2)
 85             {
 86                 FLAG = 0;
 87                 BOX[len] = '\0';
 88                 for(int j = 0;BOX[j];j ++)
 89                 {
 90                     if(j == 3)
 91                         putchar('-');
 92                     printf("%c",BOX[j]);
 93                 }
 94                 printf(" %d\n",temp -> next[i] -> count);
 95                 len --;                        //注意回溯
 96 
 97                 continue;
 98             }
 99             dfs(temp -> next[i],len);
100             len --;
101         }
102 
103     return    ;
104 }
Trie + DFS

 

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int    RULE[] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
 8 
 9 int    main(void)
10 {
11     int    * ans;
12     int    t,n,sum,flag,times,count,i,j,k;
13     char    temp[200];
14 
15     scanf("%d",&t);
16     while(t --)
17     {
18         count = 0;
19         scanf("%d",&n);
20 
21         ans = (int *)malloc(sizeof(int) * n);                        //如果在UVA上用ans[n]的形式便会WA
22         while(n --)
23         {
24             scanf("%s",temp);
25             for(i = sum = 0;temp[i];i ++)                        //转化为纯数字形式(哈希)
26             {
27                 if(temp[i] >= '0' && temp[i] <= '9')
28                 {
29                     sum *= 10;
30                     sum += (temp[i] - '0');
31                 }
32                 else    if(temp[i] >= 'A' && temp[i] <= 'Z')
33                 {
34                     sum *= 10;
35                     sum += (RULE[temp[i] - 'A']);
36                 }
37             }
38             ans[count ++] = sum;
39         }
40         sort(ans,ans + count);                                //全部存入数组后排序
41     
42         for(i = flag = 0;i < count - 1;i ++)
43         {
44             times = 1;
45 
46             while(ans[i] == ans[i + 1])
47             {
48                 times ++;
49                 i ++;
50             }
51             if(times > 1)
52             {
53                 flag = 1;
54                 printf("%03d-%04d %d\n",ans[i] / 10000,ans[i] % 10000,times);    //除法:截去后n位 求余:计算出后n位
55             }
56         }
57         if(!flag)
58             puts("No duplicates.");
59         if(t)
60             puts("");
61     }
62     
63         return    0;
64 }
sort