3139.txt

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

Source

Problem Id:3139  User Id:fzk 
Memory:2304K  Time:906MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>
using namespace std;

int has_one[1<<16];

int ans[1<<16];
int result[1<<16][24];

int a[16];

void clac_has_one( ) {
	int i;
	has_one[0] = 0;
	for( i=1; i<(1<<16); i++ )
		has_one[i] = has_one[ i&(i-1) ] + 1;
}

void clac_result( ) {
	int i, j, k;
	int index[4];

	for( i=0; i<(1<<16); i++ ) {
		if( has_one[i] == 4 ) {
			k = 0;
			for( j=0; j<16; j++ )
				if( i & (1<<j) )
					index[k++] = j;
			j = 0;
			do{
				result[i][j] = a[index[0]]*4 + a[index[1]]*3 
					+ a[index[2]]*2 + a[index[3]];
				j++;
			}while( next_permutation( index, index+4 ) );

			sort( result[i], result[i]+j );
		}
	}
}

int c_8_4[100][4];
int m;

void clac_c84( ) {
	int i, j, k;
	m = 0;
	for( i=0; i<(1<<7); i++ ) {
		if( has_one[i] == 4 ) {
			k = 0;
			for( j=0; j<7; j++ )
				if( i & (1<<j) )
					c_8_4[m][k++] = j;
			m++;
		}
	}
}



void clac_ans( ) {
	int i, j, k, a, b, *ra, *rb, *ka, *kb, t;
	char counter[11000] = { 0 };

	int id[8];

	for( i=0; i<(1<<16); i++ ) {
		if( has_one[i] == 8 && ( i<(1<<15) || ans[((1<<16)-1)^i] ) ) {

			k = 0;
			for( j=0; j<16; j++ )
				if( i & (1<<j) )
					id[k++] = j;
			t = 0;

			for( j=0; j<35; j++ ) {
				a = (1<<id[c_8_4[j][0]]) | (1<<id[c_8_4[j][1]]) 
					| (1<<id[c_8_4[j][2]]) | (1<<id[c_8_4[j][3]]);
				b = i ^ a;
				ra = result[a];
				rb = result[b];
				ka = result[a] + 23;
				kb = result[b] + 23;
				if( *ra > *kb || *rb > *ka )
					continue;

				while( ra<=ka )
					counter[ *ra++ ]++;
				while( rb<=kb )
					t += counter[ *rb++ ];
				ra = result[a];
				while( ra<=ka )
					counter[ *ra++ ] = 0;
			}
			
			ans[i] = t;
		}
		else
			ans[i] = 0;
	}
	return ;
}

long long clac( ) {
	long long sum = 0;
	int i;

	for( i=0; i<(1<<15); i++ ) {
		if( has_one[i] == 8 ) {
			sum += (long long)ans[i]*ans[((1<<16)-1)^i];
		}
	}
	return sum;
}

int main( ) {
	int i, count=1;
	clac_has_one( );
	clac_c84( );

	while( true ) {
		scanf( "%d", &a[0] );
		if( a[0] == 0 ) break;

		for( i=1; i<16; i++ )
			scanf( "%d", &a[i] );

		clac_result( );

		clac_ans( );

		printf( "Case %d: %lld\n", count++, clac() );
	}
	return 0;
}