首页 > 代码库 > POJ 2418 Hardwood Species (哈希，%f 和 %lf)
POJ 2418 Hardwood Species (哈希，%f 和 %lf)
我的错因： 本来改用%f输出，我用了%lf，结果编译器直接判定为错误（一部分编译器认为lf是没有错的）。当时我还以为是hash出错了。。
方法不止一种：
方法 时间 空间
Hash 891ms 596k
map<string,int> 2735ms 1316k
sort 5000ms+ 30000k+
%lf 与 %f的具体区别：
printf的%f说明符的确既可以输出float型又可以输出double型。根据“默认参数提升”规则float型会被提升为double型。因此printf()只会看到双精度数。对于scanf，情况就完全不同了，它接受指针，这里没有类似的类型提升。向float存储和向double存储大不一样，因此，scanf区别%f和%lf。
也就是说输出的时候不管输出的是双精度还是单精度都用%f就没错了，但是输入的时候，输入单精度要用%f而输入双精度要用%lf。
哈希
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<sstream>using namespace std;struct Tree{ char name[33]; int sum;} tree[10005];int SDBMHash(char *str){ int Hash = 0; while(*str) { Hash = (*str++) + (Hash << 6) + (Hash << 16) - Hash; } return (Hash&0x7FFFFFFF);}bool cmp(Tree a,Tree b){ return strcmp(a.name,b.name)<0;}map<int,int> pos;int main(){// freopen("H.in.cpp","r",stdin); char tmp[33]; pos.clear(); int tot = 0,all = 0; while(gets(tmp)) { if(strcmp(tmp,"") == 0) break; all++; int H = SDBMHash(tmp); int id = pos[H]; if(id == 0) { strcpy(tree[++tot].name,tmp); tree[tot].sum = 1; pos[H] = tot; } else { tree[id].sum++; } } sort(tree+1,tree+1+tot,cmp); for(int i = 1; i <= tot; i++) { printf("%s %.4f\n",tree[i].name,tree[i].sum*100.0/all); } return 0;}
map<string,int>
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<sstream>using namespace std;struct Tree{ string name; int sum;} tree[10005];bool cmp(Tree a,Tree b){ return a.name < b.name;}map<string,int> vis;int main(){// freopen("H.in.cpp","r",stdin); char a[33]; string tmp; vis.clear(); int tot = 0,all = 0; while(gets(a)) { all++; int len = strlen(a); tmp = ""; for(int i = 0; i < len; i++) { tmp += a[i]; } int id = vis[tmp]; if(id == 0) { tree[++tot].name = tmp; tree[tot].sum = 1; vis[tmp] = tot; } else { tree[id].sum++; } } sort(tree+1,tree+tot+1,cmp); for(int i = 1; i <= tot; i++) { cout<<tree[i].name<<" "; printf("%.4f\n",tree[i].sum*100.0/all); } return 0;}
排序
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<sstream>using namespace std;struct Tree{ char name[33];} tree[1000005];bool cmp(Tree a,Tree b){ return strcmp(a.name,b.name)<0;}int main(){// freopen("H.in.cpp","r",stdin); int all = 0; while(gets(tree[all].name) && strlen(tree[all].name)) { all++; } sort(tree,tree+all,cmp); int tot = 1; for(int i = 0; i < all; i++) { if(strcmp(tree[i].name,tree[i+1].name) == 0) tot++; else { printf("%s %.4f\n",tree[i].name,tot*100.0/all); tot = 1; } } return 0;}
POJ 2418 Hardwood Species (哈希，%f 和 %lf)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。