2425.txt

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

#include <stdio.h>
#include <vector>

using namespace std;

vector<int> e[1001];
bool sign[1001];
int nim[1001];
int n;

bool count[1001][1001];

void calc_nim( int k ) {
	
	int i;
	sign[k] = true;

	for( i=0; i<=e[k].size(); i++ )
		count[k][i] = false;

	for( i=0; i<e[k].size(); i++ ) {
		if( !sign[ e[k][i] ] )
			calc_nim( e[k][i] );
		count[k][ nim[ e[k][i] ] ] = true;
	}

	for( i=0; i<=e[k].size(); i++ )
		if( !count[k][i] ) {
			nim[k] = i;
			break;
		}
	return;
}

bool input( ) {
	int i, j, k;

	if( scanf( "%d", &n ) != 1 )
		return false;
	
	for( i=0; i<n; i++ ) {
		scanf( "%d", &k );
		e[i].resize( k );
		for( j=0; j<k; j++ )
			scanf( "%d", &e[i][j] );
		sign[i] = false;
	}
	for( i=0; i<n; i++ )
		if( !sign[i] )
			calc_nim( i );
	return true;
}

void doit( ){
	int i, v, k;
	while( 1 ) {
		scanf( "%d", &k );
		if( k == 0 )break;
		v = 0;
		while( k-- ) {
			scanf( "%d", &i );
			v ^= nim[i];
		}

		printf( "%s\n", v == 0 ? "LOSE" : "WIN" );
	}
}

int main( ) {
	while( input( ) )
		doit( );
	return 0;
}