算法:滑动窗口 + 区间枚举 + 二进制
时间复杂度: $O(12 \times 200000)$
基本思路:
先区间枚举,将所有 $A \le Lenth \le B$ 的 数值 和 个数 都记录下来,可用一个数组进行存储,注意 $A、B$ 的取值范围决定了枚举的区间范围,其次,按照双关键字排序,可用重载 $operator$ 或自定义 $cmp$ 函数,之后就是处理输出而已。
在记录对应数值时,可在前导加一个 1 (二进制下),即区分了相同数值不同长度对应的数,同时也利于排序,也就是无需再考虑 $Length$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int M = 1 << 13;
int A, B, m, n;
int cnt[M];
struct Data {
int k, num;
bool operator< (const Data& t) const {
if (k != t.k) return k > t.k;
return num < t.num;
}
}q[M];
string get_string(int x)
{
string s;
while (x) {
s += x % 2 + '0';
x /= 2;
}
s.pop_back();
reverse(s.begin(), s.end());
return s;
}
int main()
{
cin >> A >> B >> m;
string str, line;
while (cin >> line) str += line;
n = str.size();
for (int i = A; i <= B; ++i) {
for (int j = 0, x = 0; j < n; ++j) {
x = x * 2 + str[j] - '0';
if (j - i >= 0) x -= (str[j - i] - '0') << i; // 区间枚举
if (j - i >= -1) cnt[x + (1 << i)]++;
}
}
for (int i = 0; i < M; ++i) {
q[i].k = cnt[i];
q[i].num = i;
}
sort(q, q + M);
for (int i = 0, k = 0; i < M && k < m; ++i, ++k) {
if (!q[i].k) {
break;
}
cout << q[i].k << endl;
int j = i;
while (j < M && q[i].k == q[j].k) ++j;
int a, b;
for (a = i, b = 0; a < j; ++a, ++b) {
cout << get_string(q[a].num) << ' ';
if ((b + 1) % 6 == 0) cout << endl;
}
if (b % 6) cout << endl;
i = j - 1;
}
return 0;
}