1628.txt

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

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

__int64 p[210],q[210];

inline int geti( char c )
{
	if( c <= 'Z' && c >= 'A' ) return c - 'A' + 26;
	else return c - 'a';
}
int n, m;

void print( __int64 b )
{
	int i;
	
	for( i=0; i<26; i++ )
	if( b & ((__int64)1<<i) ) printf( "%c", 'a'+i );
	
	for( i=26; i<52; i++ )
	if( b & ((__int64)1<<i) ) printf( "%c", 'A'+(i-26) );

	printf( "\n" );
}



void init()
{
	int i, j;
	char w1[200],w2[200];

	scanf( "%d %d", &n, &m );

	for( i=0; i<n; i++ )
	{
		scanf( "%s%*s%s", w1, w2 );
		p[i] = 0, q[i] = 0;
		
		for( j=0; w1[j]; j++ )
			p[i] |= ( (__int64)1 << geti( w1[j] ) );
		
		for( j=0; w2[j]; j++ )
			q[i] |= ( (__int64)1 << geti( w2[j] ) );

	}

}

__int64 b;


void doit()
{
	int s, i, j;
	bool key;
	char w[200];

	scanf( "%s", w );
	b = 0;
	for( j=0; w[j]; j++ )
	b |= ( (__int64)1 << geti( w[j] ) );

	for( key=true,s=n; key; )
	{
		key = false;
		
		for( i=0; i<s; i++ )
		{
			if( ( b | q[i] ) == b )
			{
				s--;
				swap( q[i], q[s] );
				swap( p[i], p[s] );
				i--;
				continue;
			}

			if( ( b | p[i] ) == b )
			{
				b |= q[i];
				key = true;
				break;
			}
		}
	}
	
	print( b );
}

int main()
{
	init();
	while( m-- )
		doit();

	return 0;
}