【USACO题库】3.1.5 Contact联系

这题因为输出是按照个数来的，所以我们也只能按照个数来做咯~
暴力看每个位置长a~b的即可。用哈希来存。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 1000000007
using namespace std;
char s[200010],c;
int tot[50010],pri[50010],t[5010];
int a,b,n,now,k,len=0;

void qsort(int l,int r)
{
	int i=l,j=r,mid=tot[l+r>>1],mid1=pri[l+r>>1];
	while (i<=j)
	{
		while (tot[i]>mid || tot[i]==mid && pri[i]<mid1) i++;
		while (tot[j]<mid || tot[j]==mid && pri[j]>mid1) j--;
		if (i<=j) swap(tot[i],tot[j]),swap(pri[i++],pri[j--]);
	}
	if (i<r) qsort(i,r);
	if (l<j) qsort(l,j);
}

void change(int x)
{
	int ss=0;
	while (x>1) t[++ss]=x%2,x>>=1;
	for (int i=ss;i>0;i--) printf("%d",t[i]);
}

int main()
{
	scanf("%d%d%d
",&a,&b,&n);a--,b--;
	while (scanf("%c",&s[++len])!=EOF)
		if (s[len]!=48 && s[len]!=49) len--;
	while (s[len]!=48 && s[len]!=49) len--;
	for (int i=1;i<=len-a+1;i++)
	{
		now=1;
		for (int j=0;j<=b;j++)
		{
			if (i+j>len) break;
			now=(now<<1)+(s[i+j]^48);
			if (j>=a) tot[now]++;
		}
	}
	for (int i=0;i<=50000;i++) pri[i]=i;
	qsort(1,50000);
	now=1;
	for (int i=1;i<=n;i++)
	{
		if (!tot[now]) return 0;
		printf("%d
",tot[now]);
		change(pri[now++]);printf(" ");k=1;
		while (tot[now]==tot[now-1])
		{
			change(pri[now++]),k++;
			if (k==6) puts(""),k=0;
			else printf(" ");
		}
		if (k%6) puts("");
	}
	return 0;
}