1072.txt

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

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


//#define DEBUG
//#define PRINT_TREE 


#ifdef DEBUG
#include <time.h>
#endif

using namespace std;

const char NONE = 30;
const char WORD = 50;

struct node
{
	node(){ p=0; m='\0'; for(int i=0;i<27;i++)id[i]=NONE; }
		
	char id[27];
	int *p;
	char m;
}mem[150000];

node a_word,root;
int use_node=0;

int new_node()
{
	return use_node++;
}

void insert( node *pnd, char c )
{

	int *q = new int[ pnd->m + 1];
	
	copy( pnd->p, (pnd->p)+(pnd->m), q );
		
	q[pnd->m] = new_node();
		
	pnd->id[c-'A'] = pnd->m;
	pnd->m++;

	delete pnd->p;
	pnd->p = q;

	return ;
}

inline void set_word( node *pnd )
{
	pnd->id[27] = WORD;
}

inline node *get_child( node *pnd,char c)
{
	int s;
	if( (s=pnd->id[c-'A']) == NONE )return 0;
	else return &mem[ pnd->p[s] ];
}

inline bool is_word( node *pnd)
{
	return pnd->id[27] == WORD;
}

void creat(node *p,char *word)
{
	if( *word == '\0')
	{
		set_word( p );
	}
	else
	{
		node *q=get_child(p,*word);
	
		if( !q )
		{
			insert(p,*word);
			q=get_child(p,*word);
		}
	
		creat( q,word+1 );
	}
}

char *word[2000];
int n;


bool cmp( char *a, char *b )
{
	return *a > *b || ( *a == *b ) && strcmp(a,b) < 0;
}


char s[100];

void print( node *p, int k )
{
	if( !p ) return;
	
	if( is_word(p) )
	{
		s[k] ='\0';
		printf(":%s\n",s);
	}
	
	char a;
	for( a='A'; a<='Z'; a++ )
	{
		s[k]=a;
		print(get_child( p, a ), k+1 );
	}
}

char table[26];
char ans[26];
bool used[26];
int answer;



void init()
{
	char w[100], l, c;

	n=0;

	while( ( c = getchar() )=='\n' )
		;
	ungetc( c, stdin );

	while(1)
	{
		if(scanf( "%s", w )!=1)break;
		
		if( w[0] == '\0' ) break;
		
		l = strlen( w );

		word[n] = new char[l+2];
		word[n][0] = l;
		strcpy( word[n]+1, w );
		 
		n++;
		while( ( c = getchar() )==' ' )
			;
		if( c=='\n')
		{
			c=getchar();
			if(c=='\n')break;
			else ungetc(c,stdin);
		}
		else
		{
			ungetc(c,stdin);
		}
		if(n>1500)
		{
			n=n;
		}
	}
	
	sort(word, word+n, cmp);
	n=std::unique_copy(word, word+n,word )-word;

	int i;
	for( i=0;i<26;i++)
	{
		table[i]='*';
		used[i] = false;
	}
	answer=0;

#ifdef DEBUG
	printf("%d words\n",n);
#endif
}

char *d_word[50010];




void creat_dictionary()
{
	int i ,l, m;
	char w[100];
	scanf( "%d", &m );

	for( i=0; i<m; i++ )
	{
		scanf( "%s", w );
	
		l = strlen( w );
		d_word[i] = new	char[l+2];
		
		d_word[i][0] = l;
		strcpy( d_word[i]+1, w );

		creat( &root, w );
	}

}

inline int certain(char *s)
{
	int i,j;
	for(i=1,j=0; s[i]; i++)
		if(table[s[i]-'A']!='*')
			j++;
	return j;
}

int cmp2(char *a,char *b)
{
	return certain(a)>certain(b);
}


bool find( int wn, int cn, node *p )
{

	if( wn>=n ) 
	{
		answer++;
		copy(table,table+26,ans);

		return answer>1;
	}
	
	if( !p )return false;

	if( cn == word[wn][0] )
	{
		if( is_word(p) )
		{
			sort( word+wn+1,word+n,cmp2 );

			if( find( wn+1, 0, &root ) ) return true;
		}
	}
	else
	{
		char c = word[wn][cn+1], d;
		
		if( table[c-'A'] == '*' )
		{
			for( d='A'; d<='Z'; d++ )
			if(!used[d-'A'])
			{
				table[c-'A'] = d;
				
				used[d-'A'] = true;
				if( find( wn, cn+1, get_child(p,d) ) ) return true;
				used[d-'A'] = false;
			}
			table[c-'A'] = '*';
		}
		else	if( find( wn, cn+1, get_child(p, table[c-'A']) ) ) return true;
	}

	return false;
}		

int main()
{
	int cas;
#ifdef DEBUG
	freopen("E.in","r",stdin);
	long t=clock();
#endif

	creat_dictionary();


#ifdef PRINT_TREE	
	print(&root,0);
#endif

#ifdef DEBUG
	printf( "%dms\n", clock()-t );
#endif
	
	scanf("%d",&cas);
	
	while( cas-- )
	{
		init();
		if( find( 0, 0, &root ) )
			printf( "#More than one solution#\n" );
		else
		{
			if( answer == 0 )
				printf( "#No solution#\n" );
			else 
			{
				char out[26];
				int i;

				for( i=0; i<26; i++ )
					out[i]='*';
				
				for(i=0; i<26; i++ )
				if(ans[i-'A']!='*')
				{
					out[ans[i]-'A']=i+'A';
				}

				for( i=0; i<26; i++ )
					printf( "%c", out[i] );
				printf( "\n" );
			}
		}
	}

	return 0;
}