题意很简单：给一些单词，统计单词出现的频率（注意可以有多个单词一组，一行算一个单词）。
这题时间限制10s，map勉强过了。
#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<map> using namespace std; int main() { // freopen("E:\\ACM\\test.txt","r",stdin); string s; map<string,double> m; //map会自动排序 map<string,double> ::iterator it; int n=0; while(getline(cin,s)) { m[s]++; n++; } for(it=m.begin();it!=m.end();it++) { cout<<it->first; printf(" %.4f\n",(it->second)*100/n); //注意如果这里用%lf 就 WA了。。 } return 0; }
接下来是字典树。看代码就懂：
#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<vector> #include<algorithm> using namespace std; struct Tire { int num; //统计单词出现的次数 char str[50]; //存放单词 Tire *next[256]; Tire() { num=0; memset(next,0,sizeof(next)); } }*root; char s[100]; int n=0; void insert(char *s) //将单词插入到字典树中 { Tire *p=root; for(int i=0;s[i];i++) { int index=s[i]; if(!p->next[index]) p->next[index]=new Tire; p=p->next[index]; } p->num++; //增加次数 strcpy(p->str,s); //存储单词 } void print(Tire *p) //这样是有序的，因为字典树本来就是按字母顺序建立的 { if(!p) return ; if(p->num) printf("%s %.4f\n",p->str,p->num*100.0/n); for(int i=0;i<256;i++) { if(p->next[i]) print(p->next[i]); } } int main() { // freopen("E:\\ACM\\test.txt","r",stdin); root=new Tire; while(gets(s)) { insert(s); ++n; } print(root); //输出 return 0; }
