1150.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1150 on 2006-08-21 at 16:04:02 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int B = 19;
const int S = 1 << B;
 
int g[S], seq[B], sn;
 
int erase(int, int);
int move(int, int);
 
int main()
{
	int T, n;
 
	memset(g, -1, sizeof(g));
	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		scanf("%d", &n);
		int st = sn = 0;
		for(int i = 0; i < n; i++) {
			int a; scanf("%d", &a);
			st |= 1 << (a-2);
		}
		move(st, 0);
		printf("Scenario #%d:\n", t);
		if(sn == 0) printf("There is no winning move");
		else {
			printf("The winning moves are:");
			for(int i = 0; i < sn; i++) printf(" %d", seq[i]);
		}
		printf(".\n\n");
	}
	
	return 0;
}
 
int erase(int st, int m)
{
	st ^= 1 << (m-2);
	for(int i = 0; i+m <= B; i++)
		if(!(st&(1<<i)) && (st&(1<<(m+i)))) st ^= 1 << (m+i);
	return st;
}
int move(int st, int d)
{
	if(d == 0 || g[st] == -1) {
		for(int i = 0; i < B; i++) {
			if(!(st&(1<<i))) continue;
			int nst = erase(st, i+2), r = move(nst, d+1);
			if(d == 0 && r == 0) seq[sn++] = i+2;
			if(r == 0) g[st] = 1;
		}
		if(g[st] != 1) g[st] = 0;
	}
	return g[st];
}