★Contact 聯(lián)系
奶牛們開始對用電波望遠(yuǎn)鏡掃描牧場外的宇宙感興趣.最近,他們注意到了一種非常奇怪的脈沖調(diào)
制微波被從星系的中央發(fā)射出來.他們希望知道電波是否是被某些地外生命發(fā)射出來的,還是僅僅
是普通的的星星的心跳.
幫助奶牛們用一個能夠分析他們在文件中記下的記錄的工具來找到真相.他們在尋找長度在 A 到 B
之間（含）在每天的數(shù)據(jù)文件中重復(fù)得最多的比特序列 (1 <= A <= B <= 12).他們在找那些重復(fù)
得最多的比特序列.一個輸入限制告訴你應(yīng)輸出多少頻率最多的序列.
符合的序列可能會重疊,并且至少重復(fù)一次的序列會被計數(shù).
PROGRAM NAME: contact
INPUT FORMAT
第一行:三個用空格分隔的整數(shù): A, B, N; (1 <= N < 50)
第二行及以后:一個最多200,000字符的序列,全是0或1; 每行有80個字符,除了可能的最后一行.
SAMPLE INPUT (file contact.in)
2 4 10
01010010010001000111101100001010011001111000010010011110010000000
在樣例里,序列 100 出現(xiàn)了 12 次,而序列 1000 出現(xiàn)了 5 次.次數(shù)最多的序列是 00,出現(xiàn)了 23 次.
OUTPUT FORMAT
輸出 N 個頻率最高的序列（按照頻率由高到低的次序）.由短到長排列頻率相同的這些序列,如果長

短相同,按二進(jìn)制大小排列.如果出現(xiàn)的序列個數(shù)小于 N,輸出存在的序列

看一個大神的想法真的厲害比什么官方題解前面加一更容易理解。

/*
ID: jinbo wu
TASK: contact
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
string str,temp;
int sta[15][5000];
int d[13];
bool v[200005];
int main()
{freopen("contact.in","r",stdin);freopen("contact.out","w",stdout);d[0]=1;for(int i=1;i<=12;i++)d[i]=2*d[i-1];int a,b,n;cin>>a>>b>>n;while(cin>>temp){str+=temp;if(temp.length()<80)break;}for(int i=0;i<str.length();i++){int sum=0;for(int j=0;j<12&&str[i+j]!='\0';j++){sum=sum*2+str[i+j]-'0';sta[j+1][sum]++;}}int maxn=0;for(int i=1;i<=12;i++)for(int j=0;j<=d[i];j++){if(maxn<sta[i][j])maxn=sta[i][j];}int count2=0;if(a>str.length())  a=str.length();if(b>str.length())  b=str.length();for(int i=maxn;i>0;i--){int flag=0;int count=0;for(int j=a;j<=b;j++)for(int k=0;k<=d[j];k++){if(sta[j][k]==i){if(count%6!=0)cout<<" ";if(count%6==0&&count)cout<<endl;if(!v[i]){printf("%d\n",i);v[i]=1;}for(int c=1;c<=j;c++){if(d[j-c]&k)//看k的第c位（順著數(shù)）是1還是0.cout<<'1';else cout<<'0';}count++;flag=1;}}if(flag==1){count2++;cout<<endl;}if(count2==n)break;	}
}

總結(jié)

以上是生活随笔為你收集整理的usaco contact的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。