1906.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1906 on 2006-08-24 at 16:32:05 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 12;
const int LMT = 1 << N;
const int TOTAL = (N+1)*LMT;
 
class Seg {
public:
	int value, len, fre;
	void set(int v, int l, int f) { value = v; len = l; fre = f; }
	void print() const;
	bool operator <(const Seg&) const;
};
void Seg::print() const {
	putchar(' ');
	for(int i = len-1; i >= 0; i--)
		if(value&(1<<i)) putchar('1');
		else putchar('0');
}
bool Seg::operator <(const Seg& s) const {
	if(fre != s.fre) return fre > s.fre;
	else if(len != s.len) return len > s.len;
	else return value > s.value;
}
 
int main()
{
	Seg seg[TOTAL];
	int a, b, n, i, j;
	
	while(scanf("%d %d %d", &a, &b, &n) != EOF) {
		getchar();
		for(i = 0; i <= N; i++)
			for(j = 0; j < LMT; j++)
				seg[i*LMT+j].set(j, i, 0);
		int cur = 0, ch;
		for(i = 0; (ch = getchar()-'0') != 2; i++) {
			cur &= ((1 << b-1) - 1);
			cur = cur * 2 + ch;
			if(i + 1 >= a) {
				int p = cur & ((1 << a) - 1);
				int l = (i + 1) < b ? (i + 1) : b;
				for(j = a; j <= l; j++) {
					seg[j*LMT+p].fre++;
					p |= (cur & (1 << j));
				}
			}
		}
		sort(seg, seg+TOTAL);
		int diff = 0, prev = 5000000;
		for(i = 0; i < TOTAL; i++) {
			if(prev == seg[i].fre) seg[i].print();
			else {
				if(i != 0) putchar('\n');
				diff++;
				if(diff > n || seg[i].fre == 0) break;
				else {
					prev = seg[i].fre;
					printf("%d", prev);
					seg[i].print();
				}
			}
		}
	}
	
	return 0;
}