2009.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2009 on 2005-10-17 at 11:15:12 */ 
#include <cstdio>
#include <cstring>
#define  MAX  256
#define  D_MAX  1024
#define  N_MAX  64

typedef struct {
	unsigned long long d;
	unsigned long long r;
} Deduction;

unsigned long long change(char*);

int main()
{
	int n, m;
	int i, j;
	char d[N_MAX], r[N_MAX];
	Deduction decu[MAX];
	unsigned long long result;
	bool proved[MAX], have;
	
	while(scanf("%d %d", &m, &n) == 2) {
		for(i = 0; i < m; i++) {
			scanf("%s %*s %s", d, r);
			decu[i].d = change(d);
			decu[i].r = change(r);
		}
		for(i = 0; i < n; i++) {
			scanf("%s", d);
			result = change(d);
			memset(proved, false, sizeof(proved));
			have = true;
			while(have) {
				have = false;
				for(j = 0; j < m; j++) {
					if(!proved[j] && ((result | decu[j].d) == result)) {
						result |= decu[j].r;
						proved[j] = true;
						have = true;
					}
				}
			}
			for(j = 0; j < 26; j++) {
				if(result == 0) {
					break;
				} else {
					if(result % 2 == 1) {
						putchar('a'+j);
					}
					result /= 2;
				}
			}
			for(j = 0; j < 26; j++) {
				if(result == 0) {
					break;
				} else {
					if(result % 2 == 1) {
						putchar('A'+j);
					}
					result /= 2;
				}
			}
			putchar('\n');
		}
	}
	
	return 0;
}

unsigned long long change(char *s)
{
	int i;
	unsigned long long r = 0;
	for(i = 0; s[i] != '\0'; i++) {
		if(s[i] >= 'a' && s[i] <= 'z') {
			r |= (long long)1 << (s[i] - 'a');
		} else {
			r |= (long long)1 << (s[i] - 'A' + 26);
		}
	}
	return r;
}