Contact USACO 3.1

这题好烦了,看着蛮简单,开始用map<string ,int>存,最后排序要用到value值,但map的compare只传key...

换成set<pair<string,int> >勉强能跑但是好慢,后来看题解最后直接把map里的传到vector<pair<string,int>>

再排序,我怎么就没想到多用个容器...

不想写了贴个别人的过了先,不过有点注意,算起点时我这么些j=0;j<=str.length()-A;j++

本来当A>str.length()时,循环应该自动退出.结果却不是.

后来看提示才明白,str.length()返回的是unsigned int,我的A是int

而当unsigned int和int运算时,结果作为unsiged...那自然是j一直小于...

然后又是vector不能用于copy...

  1 /*
  2 
  3 ID: hubiao cave
  4 
  5 PROG: contact
  6 
  7 LANG: C++
  8 
  9 */
 10 
 11 
 12 
 13 
 14 #include<iostream>
 15 #include<fstream>
 16 #include<string>
 17 #include<algorithm>
 18 #include<map>
 19 #include<vector>
 20 #include<utility>
 21 
 22 
 23 using namespace std;
 24 
 25 
 26 
 27 string str;
 28 int A,B,N;
 29 
 30 
 31  class  mycom
 32      {
 33      public:
 34          bool operator ()(const std::pair<string,int>&,const std::pair<string,int>&);
 35  };
 36 
 37 
 38 
 39 map<string,int> msi;
 40 vector<pair<string,int> >vt;
 41 int main()
 42 
 43 {
 44 
 45     ifstream fin("contact.in");
 46     ofstream fout("contact.out");
 47     
 48    fin>>A>>B>>N;
 49     string temp,sub;
 50     while(fin>>temp)
 51     {
 52         str+=temp;
 53     }
 54 
 55     for(int i=A;i<=B;i++)
 56     {
 57         for(int j=0;j<=(int)str.length()-i;j++)
 58         {
 59             sub=str.substr(j,i);
 60             msi[sub]++;
 61         }
 62     }
 63 
 64     for(map<string,int>::iterator it=msi.begin();it!=msi.end();it++)
 65         vt.push_back(*it);
 66     sort(vt.begin(),vt.end(),mycom());
 67 
 68     int m=0;
 69     int prt=0;
 70     int re=0;
 71     int Old=-1;
 72     int counter=0;
 73 
 74     while(re<vt.size())
 75     {
 76         if(vt[re].second!=Old)
 77         {
 78             if(m==N)break;
 79             if(re!=0)fout<<endl;
 80             counter=0;
 81             fout<<vt[re].second<<"
"<<vt[re].first;
 82             Old=vt[re].second;
 83             m++;
 84             re++;
 85         }
 86         else
 87         {
 88             counter++;
 89             if(counter%6==0)
 90                 fout<<endl<<vt[re].first;
 91             else 
 92                 fout<<" "<<vt[re].first;
 93             re++;
 94         }
 95     }
 96 
 97     fout<<endl;
 98     return 0;
 99 
100 
101 }
102 
103 bool mycom::operator()(const std::pair<string,int>& p1,const std::pair<string,int>& p2)
104 {
105     if(p1.second!=p2.second)
106         return p1.second>p2.second;
107     else
108     {
109         if(p1.first.length()!=p2.first.length())
110             return p1.first.length()<p2.first.length();
111         else
112             return p1.first<p2.first;
113     }
114 }