Contact_usaco3.1_暴力

NO IMAGE

題目描述 Description


奶牛們開始對用射電望遠鏡掃描牧場外的宇宙感興趣。最近,他們注意到了一種非常奇怪的脈衝調製微波從星系的中央發射出來。他們希望知道電波是否是被某些地外生命發射出來的,還是僅僅是普通的的星星發出的。

幫助奶牛們用一個能夠分析他們在檔案中記下的記錄的工具來找到真相。他們在尋找長度在A到B之間(包含A和B本身)在每天的資料檔案中重複得最多的位元序列 (1 <= A <= B <= 12)。他們在找那些重複得最多的位元序列。一個輸入限制告訴你應輸出多少頻率最多的序列。

符合的序列可能會重疊,並且至少出現一次的序列會被計數。

輸入描述 Input Description


第一行: 三個用空格分隔的整數: A, B, N; (1 <= N < 50)

第二行及以後: 一個最多200,000字元的序列,全是0或1; 每行字元數不大於80。

輸出描述 Output Description


輸出N個頻率最高的序列(按照頻率由高到低的次序)。由短到長排列頻率相同的這些序列,如果長短相同,按二進位制大小排列。如果出現的序列個數小於N,輸出存在的序列。

對於每個存在的頻率,先輸出單獨包含該頻率的一行,再輸出以空格分隔的這些序列。每行六個(除非少於六個剩下)。

題解 Analysis


題解眾說紛紜,然而我用暴力過了(笑)

暴力出奇跡!!

列舉合法長度的子串壓成二進位制,用cal[i][j]cal[i][j]表示長度為ii的子串jj的個數
為什麼要加第一維jj呢?
考慮到會出現如00010001和001001的兩個不同子串,然而壓成二進位制後他們是相等的,為了避免這種情況就加上長度的限制條件,最後暴力找一下就可以了
輸出略坑,每六個換行。usaco出題人是強迫症重度患者?

陣列大小?不清楚,隨手開的;-D

看來是時候要搞一發字典樹了(flag)

Code


/*
ID:wjp13241
PROG:contact
LANG:C  
*/
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;
struct mes
{
int st,ed;
};
queue<mes>ans;
bool vis[13][8193];
mes rec[13][8193];
int cal[13][8193];
int num[200011];
char s[255];
int get(int st,int ed)
{
int bnry=0;
for (int i=ed;i>=st;i--)
bnry =(num[i]<<(ed-i 1));
return bnry;
}
int main()
{
freopen("contact.in","r",stdin);
freopen("contact.out","w",stdout);
int a,b,n;
scanf("%d%d%d",&a,&b,&n);
int limit=(1<<(b 1));
while (scanf("%s",s)!=EOF)
{
for (int i=0;i<strlen(s);i  )
num[  num[0]]=s[i]-'0';
}
for (int i=a;i<=b;i  )
{
for (int j=1;j<=num[0]-i 1;j  )
{
int tmp=get(j,j i-1);
cal[i][tmp]  ;
if (!rec[i][tmp].st)
rec[i][tmp]=(mes){j,j i-1};
}
}
while (n--)
{
int max=0,cnt=0;
for (int i=a;i<=b;i  )
for (int j=0;j<=limit;j  )
if ((max<cal[i][j])&&(!vis[i][j]))
max=cal[i][j];
if (!max)
break;
printf("%d\n",max);
for (int i=a;i<=b;i  )
for (int j=0;j<=limit;j  )
if (max==cal[i][j])
{
vis[i][j]=true;
ans.push(rec[i][j]);
}
while (ans.size()>1)
{
mes now=ans.front();ans.pop();
for (int i=now.st;i<=now.ed;i  )
printf("%d",num[i]);
if (!(  cnt%6))
printf("\n");
else
printf(" ");
}
mes now=ans.front();ans.pop();
for (int i=now.st;i<=now.ed;i  )
printf("%d",num[i]);
printf("\n");
}
return 0;
}