contact.cpp

IOI 1998 题目contact的解法

/*
 PROG: contact
 ID: wchk2001
 LANG: C++
 */

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
#define MAXCNT 10000

struct res{
	int value;
	int freq;
};

int a,b, n;
int pow2[14] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192};
int freq[MAXCNT];
int f[13];
res final[MAXCNT];
char c;

void init()
{
	scanf("%d%d%d\n", &a, &b, &n);

	for (int i = 0; i < a; i++)
	{
		scanf("%c", &c);
		if ( i == 0 )
			f[i+1] = c-'0';
		else
			f[i+1] = (f[i] << 1 ) + (c-'0');
	}

	memset(freq, 0, sizeof(int)*MAXCNT);

	
	freq[f[a] + pow2[a]]++;
}

void solve()
{
	int len = a;

	while ( len < b && scanf("%c", &c) != EOF)
	{
		if ( c== '\n' )
			continue;
			
			if ( c == '2' )
				break;

		f[len+1] = (f[len] << 1)+ (c-'0');

		for (int j = a; j <= b; j++)
		{
			if ( (len+1-j) < 0 )
				break;
			int temp = f[len+1] - (f[len+1-j]<<j) + pow2[j];
			freq[temp]++;
		}	

		len++;
	}

	while ( scanf("%c", &c) != EOF )
	{
		if ( c == '\n')
			continue;
			
			if ( c== '2' )
				break;
		
		int bit = f[1];

		for (int i = 1; i <= b; i++)
		{
			if ( i == b )
				f[b] = (f[b] - (bit<<(i-1)))*2 + c-'0';
			else
				f[i] = f[i+1] - (bit << i);
		}

		for (int j = a; j <= b; j++)
		{
			if ( (b-j) < 0 )
				break;

			int temp;

			if ( j == 1 )
			{
				temp = c-'0'+2;	
			}
			else
			{
				if ( j == b )
					temp = f[b] + pow2[b];
				else		
					temp = f[b] - (f[b-j] <<j ) + pow2[j];
			}

			freq[temp]++;
		}
	}
}

bool cmp(const res &x, const res &y)
{
	if ( x.freq > y.freq )
		return true;
	if ( x.freq < y.freq )
		return false;
	if ( x.freq == y.freq )
		return ( x.value > y.value );

	return false;
}

void print_result()
{
	for (int i = 1; i < MAXCNT; i++)
	{
		final[i].freq = freq[i];
		final[i].value = i;
	}

	sort ( &final[0], &final[MAXCNT], cmp);

	int j = 0;

	while ( final[j].freq > 0 && n > 0)
	{
		printf("%d ", final[j].freq);


		do{
			int temp = final[j].value;
			int k;

			for (k = 13; k >= 0; k--)
			{
				if ( temp >= pow2[k] )
					break;
			}

			temp -= pow2[k--];

			while ( k >= 0 )
			{
				printf("%d", temp / pow2[k]);
				if ( k == 0 )
					break;
				temp = temp % pow2[k--];
			}
	
			if ( final[j].freq == final[j+1].freq )
			{
				
					printf(" ");
			}
			
			j++;
		}
		while ( j < MAXCNT && final[j].freq  == final[j-1].freq );
		printf("\n");

		n--;
	}
}

int main()
{
	init();
	solve();
	print_result();

	return 0;
}