2842.txt

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

Source

Problem Id:2842  User Id:fzk 
Memory:2040K  Time:858MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>

int an[10], bn[10];
int sa[10], sb[10];
int p[10], n, m, g, h;
int S[500000], T[500000];

int get_T( int *a ) {
	int index = 0, i;
	for( i=0; i<n; i++ )
		index += a[i]*sa[i];
	return T[ index ];
}

int get_S( int *a ) {
	int index = 0, i;
	for( i=0; i<n; i++ )
		index += (a[i]+p[i])*sb[i];
	return S[ index ];
}

bool check( ) {
	int a[10] = { 0 }, i, k;
	for( i=0; i<m; i++ ) {
		if( get_T( a ) != get_S( a ) )
			return false;
		for( k=n-1; a[k] == an[k]-1 && k; k-- )
			;
		a[k]++;
		while( k++ < n-1 )
			a[k] = 0;
	}
	return true;
}

void search( ) {
	int i, k;
	for( i=0; i<g; i++ ) {
		if( check( ) )
			return;
		for( k=n-1; p[k] == bn[k]-an[k] && k; k-- )
			;
		p[k]++;
		while( k++ < n-1 )
			p[k] = 0;
	}
	return;
}

int main( ) {
	int i;
	g = m = h = 1;

	scanf( "%d", &n );

	for( i=0; i<n; i++ )
		scanf( "%d", bn+i );
	for( i=0; i<n; i++ ) {
		scanf( "%d", an+i );
		m *= an[i];
		g *= bn[i]-an[i]+1;
		h *= bn[i];
	}

	for( i=0; i<h; i++ )
		scanf( "%d", S+i );
	for( i=0; i<m; i++ )
		scanf( "%d", T+i );

	sb[n-1] = sa[n-1] = 1;

	for( i=n-2; i>=0; i-- ) {
		sa[i]=an[i+1]*sa[i+1];
		sb[i]=bn[i+1]*sb[i+1];
	}

	search( );
	for( i=0; i<n; i++ )
		printf( "%d ", p[i]+1 );
	printf( "\n" );
	return 0;
}