首页 > 代码库 > poj水题-1002 STL是神器,得用啊
poj水题-1002 STL是神器,得用啊
很简单的一个,就是总超时。问题出在我使用的短平快,简单直接的方式已经不灵了。
这种情况我总结以下原因:
1.尽量用STL模板容器,qsort()等内置,他们优化得很好
2.不用的话需要了解哈希算法。
本题用了快排与哈希,自己写也行(麻烦),不写的话用qsort与STL map,否则超时。我用的当然是模板,短平快解决战斗。
#include <iostream>#include <map>#include <string>using namespace std;string s,t;map<string,int> cnt;int i,n,f;int main(){ cin>>n; while(n--) { cin>>s; f=0; for(i=0;i<s.size();i++) { if(s[i]==‘-‘) continue; else if(s[i]>=‘0‘&&s[i]<=‘9‘) t.push_back(s[i]); else if(s[i]>=‘A‘&&s[i]<=‘P‘) { s[i]-=‘A‘; s[i]/=3; s[i]+=‘0‘+2; t.push_back(s[i]); } else { s[i]-=‘A‘+1; s[i]/=3; s[i]+=‘0‘+2; t.push_back(s[i]); } } t.insert(3,"-"); ++cnt[t]; t.clear(); } for(map<string,int>::iterator p=cnt.begin();p!=cnt.end();p++) { if(p->second>1) { cout<<p->first<<" "<<p->second<<endl; f=1; } } if(!f)cout<<"No duplicates."<<endl;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。