【USACO3.1.5】【洛谷P2724】联系 Contact【模拟】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P2724
帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在A到B之间（包含A和B本身）在每天的数据文件中重复得最多的比特序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。一个输入限制告诉你应输出多少频率最多的序列。
符合的序列可能会重叠，并且至少出现一次的序列会被计数。

思路：

由于 $A,Bleq12$ ，所以显然把01串状压。
状压之后用 $cnt[S]$ 表示压缩后为 $S$ 的状态个数。
但是这样忽略了前导零的情况。
也就是说，如果我们能找到这样的两个子串

00101
101

我们都会压缩成5。但是这两个串是不同的。
所以我们在 $cnt$ 数组上再加上一维，设 $cnt[S][i]$ 表示状态为 $S$ ，有 $i$ 个前导零的子串个数。（其实也可以设01串位数为 $i$ 位，但是敲完了就懒得改了XD）
那么考虑如何枚举出长度在 $lsim r$ 的所有子串。
如果我们知道了第 $isim j$ 位压缩后的状态，第 $j+1$ 位是 $x$ ，需要我们推出 $isim j+1$ 位压缩后的状态，显然就是把i∼j位的状态左移一位，然后加上x。
所以当我们枚举到原串第 $i$ 位开始的子串时，设 $num[j]$ 表示长度为 $j$ 的子串压缩后的状态（即 $isim j$ 维压缩后的状态）。那么显然可以这样推出

for (int j=min(i,r);j>=1;j--)
	num[j]=(num[j-1]<<1)+x;

然后更新 $cnt$

for (int i=l;i<=min(j,r);i++)
	cnt[num[i]][count(i,num[i])]++;

其中 $count$ 用来计算有多少位前导零。
接下来就需要给 $cnt$ 数组按值排序了。
显然是不可能用 $sort$ 的。因为一个值可能会对应多个状态。
所以可以考虑用队列。
设 $q[i]$ 表示出现次数为 $i$ 的子串集合。 $q[i].first$ 表示该子串状压后的状态， $q[i].second$ 表示该子串的长度。
然后按照题目要求，先枚举子串长度，然后按字典序枚举子串的状态。并加入队列。

for (int j=l;j<=r;j++)
	for (int i=0;i<(1<<j);i++)
		q[cnt[i][count(j,i)]].push(make_pair(i,j));

然后就是输出的事情了。
根据 $redbag$ 大爷的题解，有以下几点输出要求：

输出完频率要换行。
输出6个序列要换行。
输出完序列要换行。
如果该频率的序列刚好是6个的话只要换一次行。
每行第一个序列之前不能有空格。
每行最后一个序列之后不能有空格。

细节处理一下就好了。从大到小枚举子串出现次数 $i$ ，如果存在出现 $i$ 次的子串，一一输出就好了。我们在加入队列的时候已经保证了子串长度和字典序，所以可以不用在意输出顺序。
时间复杂度大约是 $O(|S| imes r+max{cnt})$ 。

代码：

/*
ID:ssl_zyc2
TASK:contact
LANG:C++
*/
#include <cstdio>
#include <queue>
#include <iostream>
#define mp make_pair
using namespace std;

const int N=200010;
int l,r,n,x,maxn,num[15],cnt[1<<12][15];

int count(int s,int x)
{
	if (!x) return s-1;
	int sum=0;
	while (x)
	{
		x>>=1;
		sum++;
	}
	return s-sum; 
}

void print(int x)
{
	if (x>1) print(x>>1);
	printf("%d",x&1);
}

int main()
{
	freopen("contact.in","r",stdin);
	freopen("contact.out","w",stdout);
	scanf("%d%d%d",&l,&r,&n);
	for (int j=1;scanf("%1d",&x)==1;j++)
	{
		for (int i=min(j,r);i>=1;i--)
			num[i]=(num[i-1]<<1)+x;
		for (int i=l;i<=min(j,r);i++)
		{
			cnt[num[i]][count(i,num[i])]++;
			maxn=max(maxn,cnt[num[i]][count(i,num[i])]);
		}
	}
	queue<pair<int,int> > q[maxn+1];
	for (int j=l;j<=r;j++)
		for (int i=0;i<(1<<j);i++)
			q[cnt[i][count(j,i)]].push(mp(i,j));
	for (int i=maxn;i>=1&&n;i--)
		if (q[i].size())
		{
			n--;
			printf("%d
",i);
			int len=q[i].size();
			for (int j=1;j<=len;j++)
			{
				for (int k=1;k<=count(q[i].front().second,q[i].front().first);k++)
					putchar(48);
				print(q[i].front().first);
				q[i].pop();
				if (!(j%6)) printf("
");
					else if (j!=len) printf(" ");
			}
			if (len%6) printf("
");
		}
	return 0;
}