首页 > 代码库 > 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;}