3188.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3188  User Id:fzk 
Memory:64K  Time:1278MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>

using namespace std;

char w[1000][11];

int button[26];


__int64 a[1000];
int n, B, L;
int flag[26];

void clac( int &s1, int &s2 ) {
	int i, j;
	s1 = 0, s2 = 0;
	flag[B] = 100;
	for( i=0, j=0; i<L; i++ ) {
		if( i == flag[j] )
			j++;
		button[i] = j+1;
	}

	__int64 t;
	for( i=0; i<n; i++ ) {
		t = 0;
		for( j=0; w[i][j]; j++ )
			t = ((t<<5) | button[ w[i][j] - 'A' ]);
		a[i] = t;
	}

	sort( a, a+n );

	for( i=0; i<n; i=j ) {
		for( j=i+1; j<n && a[i] == a[j]; j++ )
			;
		s1++;
		s2 += (j==i+1);
	}

	return ;
}

int ans;
int best[27];


void search( int k, int ch ) {
	if( ans == n )
		return;
	if( k == B-1 ) {
		int s1, s2;
		clac( s1, s2 );
		if( s2 > ans ) {
			ans = s2;
			for( int i=0; i<L; i++ )
				best[i] = button[i];
		}
		return;
	}

	int i;

	for( i=L-(B-k); i>=ch; i-- ) {
		flag[k] = i+1;
		search( k+1, i+1 );
	}
}

int main( ) {
	int i;
	scanf( "%d%d%d", &B, &L, &n );
	
	for( i=0; i<n; i++ )
		scanf( "%s", w+i );
	
	ans = 0;
	search( 0, 0 );

	printf( "%d\n", ans );
	for( i=0; i<L; i++ ) {
		printf( "%c", 'A'+i );
		if( best[i] != best[i+1] )
			printf( "\n" );
	}

	return 0;
}