2004.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2004 on 2006-05-26 at 11:24:02 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int WN = 32;

int n, st, best, cnt[WN], word[WN];

void find(int, int);

int main()
{
	int i, j, t, T;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		memset(cnt, 0 ,sizeof(cnt)); memset(word, 0, sizeof(word));
		for(i = 0; i < n; i++) {
			char w[64]; scanf("%s", w);
			for(j = 0; w[j] != 0; j++) word[i] ^= 1 << (w[j]-'a');
			for(j = 0; j < WN; j++)
				if(word[i]&(1<<j)) cnt[j]++;
		}
		st = best = 0; find(0, 0);
		printf("%d\n", best);
	}
	
	return 0;
}

void find(int o, int total)
{
	if(st == 0) best = max(best, total);
	if(o == n || total+n-o <= best) return;
	int i; bool can = true; st ^= word[o];
	for(i = 0; i < WN; i++) {
		if(word[o]&(1<<i)) cnt[i]--;
		if(cnt[i] == 0 && (st&(1<<i))) can = false;
	}
	if(can) find(o+1, total+1);
	st ^= word[o];
	if(word[o] != 0) find(o+1, total);
	for(i = 0; i < WN; i++)
		if(word[o]&(1<<i)) cnt[i]++;
}