首页 > 代码库 > poj2418（Hardwood Species）

poj2418（Hardwood Species）

2024-07-15 05:56:30   219人阅读

题目地址 :  Hardwood Species

 

题目大意：

    给你多组字符串，算出其占所有给出字符串占的比重。

 

解题思路：

    字典树，将每个字符的最后一个字符的节点里count++。  最后求出count/sum。 即可。关键是字符串的输出。因为存到字典树里的值就是本身字符的ASCII码值，所以最后输出的时候，i（0->MAX）判断有没有该节点，有的将i 赋值到一个字符串即可。

 

代码:

  1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 32 /***************************************/ 33 void openfile() 34 { 35     freopen("data.in","rb",stdin); 36     freopen("data.out","wb",stdout); 37 } 38 priority_queue<int> qi1; 39 priority_queue<int, vector<int>, greater<int> >qi2; 40 /**********************华丽丽的分割线,以上为模板部分*****************/ 41 const int MAX=150; 42 struct Trie 43 { 44     Trie *next[MAX];  //存储下一层 45     int v;  //存储到此有多少相同前缀的数目 46     int count; 47 }; 48 Trie *root; 49 int sum; 50 int d=0; 51 char str[35]= {‘\0‘}; 52 void creatTrie(char s[]) 53 { 54     Trie *p,*q; 55     p=root; 56     int len=strlen(s); 57     for(int i=0; i<len; i++) 58     { 59         int ce=s[i]; 60         if (p->next[ce]==NULL) 61         { 62             q=(Trie *)malloc(sizeof(Trie)); 63             q->v=1; 64             for(int j=0; j<MAX; j++) 65             { 66                 q->next[j]=NULL; 67                 q->count=0; 68             } 69             p->next[ce]=q; 70             p=p->next[ce]; 71         } 72         else 73         { 74             p->v++; 75             p=p->next[ce]; 76         } 77     } 78     p->v=-1; 79     p->count++; 80 } 81 int find(char s[]) 82 { 83     int len=strlen(s); 84     Trie *p=root; 85     for(int i=0; i<len; i++) 86     { 87         int ce=s[i]; 88         p=p->next[ce]; 89         if (p==NULL) 90             return 0; 91         if (p->v==-1) 92             return 1; 93     } 94     return 1; 95 } 96 void outp(Trie *T) 97 { 98     if (T->count!=0) 99     {100         for(int j=0;j<d;j++)101             printf("%c",str[j]);102         printf(" %.4lf\n",(double)(T->count)/(double)sum*100.0);103     }104     for(int i=0; i<MAX; i++)105         if (T->next[i]!=NULL)106         {107             str[d]=i;108             d++;109             outp(T->next[i]);110             d--;  //树的构造，-1到上一层的d值。111         }112 }113 int dealTrie(Trie *T)114 {115     if (T==NULL)116         return 0;117     for(int i=0; i<MAX; i++)118         if (T->next[i]!=NULL)119             dealTrie(T->next[i]);120     free(T);121     return 0;122 }123 int main()124 {125     char s[35];126     root=(Trie *)malloc(sizeof(Trie));127     for(int i=0; i<MAX; i++) //初始化128     {129         root->next[i]=NULL;130         root->count=0;131     }132     while(gets(s))133     {134         if (s[0]==0)135             break;136         sum++;137         creatTrie(s);138     }139     outp(root);140     dealTrie(root);141     return 0;142 }
View Code

 


联系
我们