3.1.5 Contact 联系
时间： 1ms 内存：64M
描述：
奶牛们开始对用电波望远镜扫描牧场外的宇宙感兴趣。最近，他们注意到了一种非常奇怪的脉冲调制微波被从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的，还是仅仅是普通的的星星的心跳。
帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在A到B之间（含）在每天的数据文件中重复得最多的比特序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。一个输入限制告诉你应输出多少频率最多的序列。 符合的序列可能会重叠，并且至少重复一次的序列会被计数。
输入：
第一行：
三个用空格分隔的整数: A, B, N; (1 <= N < 50) 第二行及以后: 一个最多200，000字符的序列，全是0或1; 每行有80个字符，除了可能的最后一行。
输出：
输出N个频率最高的序列（按照频率由高到低的次序）。由短到长排列频率相同的这些序列，如果长短相同，按二进制大小排列。如果出现的序列个数小于N，输出存在的序列。
对于每个存在的频率，先输出单独包含该频率的一行，再输出以空格分隔的这些频率。每行六个（除非少于六个剩下）。
示例输入：
2 4 10
01010010010001000111101100001010011001111000010010011110010000000示例输出：
23
00
15
01 10
12
100
11
11 000 001
10
010
8
0100
7
0010 1001
6
111 0000
5
011 110 1000
4
0001 0011 1100
提示：
参考答案（内存最优[1796]）：
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
map<string,int> m;
map<string,int> ::iterator it;
vector<pair<int,string> > v;
int a,b,n;
bool cmp(const pair<int,string> &a,const pair<int,string> &b)
{
if(a.first!=b.first)
return a.first>b.first;
if(a.second.size()!=b.second.size())
return a.second.size()<b.second.size();
return a.second<b.second;
}
int main()
{
int i,j;
int cur,old,cnt,res;
string str="";
string tmpstr;
cin>>a>>b>>n;
while(cin>>tmpstr)
str+=tmpstr;
for(i=a;i<=b;i++)
for(j=0;j+i<=str.size();j++)
m[str.substr(j,i)]++;
it=m.begin();
while(it!=m.end())
{
v.push_back(make_pair(it->second,it->first));
it++;
}
sort(v.begin(),v.end(),cmp);
cur=0;
old=-1;
cnt=0;
res=0;
while(cur<v.size())
{
if (v[cur].first!=old)
{
if(res==n)
break;
if(res!=0)
cout<<endl;
res++;
cnt=0;
cout<<v[cur].first<<endl<<v[cur].second;
old=v[cur].first;
cur++;
}
else
{
cnt++;
if (cnt%6==0)
cout<<endl<<v[cur].second;
else
cout<<" "<<v[cur].second;
cur++;
}
}
cout<<endl;
return 0;
}
参考答案（时间最优[132]）：
/*
ID: supersnow0622
PROG: contact
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include<memory.h>
#include<algorithm>
using namespace std;
struct Node
{
int Count,index;
char str[14];
};
Node n[20000];
int used[20000];
int cmp(Node n1,Node n2)
{
if(n1.Count==n2.Count)
return n1.index<n2.index;
else return n2.Count<n1.Count;
}
int main() {
ofstream fout ("contact.out");
ifstream fin ("contact.in");
int A,B,N;
string s,temp;
int count,num;
cin>>A>>B>>N;
getline(cin,temp);
while(getline(cin,temp))
s+=temp;
if(s.length()<B)B=s.length();
for(int i=A;i<=B;i++)
for(int j=0;j<s.length()-i+1;j++)
{
int count=0;num=1;
while(count<i)
{
num=num<<1;
num=num|(int)(s[j+count]-'0');
count++;
}
n[num].Count++;
if(n[num].Count==1){
n[num].index=num;
for(int k=0;k<i;k++)
n[num].str[k]=s[k+j];
}
}
sort(n,n+20000,cmp);
memset(used,0,sizeof(used));
bool judge=true;count=0;
for(int i=0;i<20000;i++)
{
if(n[i].Count!=0){
if(!used[n[i].Count])
{
count++;num=1;
if(count>N)break;
if(!judge)cout<<endl;judge=false;
cout<<n[i].Count<<endl<<n[i].str;
used[n[i].Count]=1;
}
else{
if(num%6==0)cout<<endl<<n[i].str;
else cout<<" "<<n[i].str;num++;
}
}
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。