2220.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2220 on 2006-04-26 at 13:21:46 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int PN = 128;
const int L = 24;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

map<const char*, int, cmp> dict;

int winner(int[][PN], int[], int, int);
void mul(int[][PN], int[][PN], int);

int main()
{
	int t, T, i, j;
	int m[PN][PN], b[PN], nn[PN];
	char nxt[PN][PN][L], name[PN][L];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int n, turn; scanf("%d %d", &n, &turn); dict.clear();
		memset(m, 0, sizeof(m)); memset(b, 0, sizeof(b));
		for(i = 0; i < n; i++) {
			scanf("%s %d %d", name[i], &b[i], &nn[i]);
			b[i] &= 1; dict[name[i]] = i;
			for(j = 0; j < nn[i]; j++) scanf("%s", nxt[i][j]);
		}
		for(i = 0; i < n; i++)
			for(j = 0; j < nn[i]; j++)
				m[i][dict.find(nxt[i][j])->second] = 1;
		for(i = 0; i < n; i++) m[i][i] = m[i][i]^1;
		printf("%d\n", winner(m, b, n, turn-1));
	}
	
	return 0;
}

int winner(int u[][PN], int b[], int n, int t)
{
	int r[PN][PN], i, j, bit;
	memcpy(r, u, sizeof(r));
	for(bit = 31; (t&(1<<bit)) == 0; bit--);
	for(bit--; bit >= 0; bit--) {
		mul(r, r, n);
		if(t & (1<<bit)) mul(r, u, n);
	}
	int win = 0;
	for(i = 0; i < n; i++) {
		int ts = 0;
		for(j = 0; j < n; j++) ts += b[j] & r[j][i];
		if(ts&1) win++;
	}
	return win;
}
void mul(int a[][PN], int b[][PN], int n)
{
	int c[PN][PN], d[PN][PN], i, j, k;
	memcpy(c, a, sizeof(c)); memcpy(d, b, sizeof(d));
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++) {
			int x = 0;
			for(k = 0; k < n; k++) x += c[i][k] & d[k][j];
			a[i][j] = x & 1;
		}
}