zju 1039 number game(博弈搜索).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>

bool num[25];
char hash[550000];
int n;

inline int hash_num()
{
	int dig = 1,i,t = 0;
	for (i=2;i<=20;i++) {
		if (num[i]) {
			t |= 1<<(i-2);
		}
	}
	return t;
}

char dfs()
{
	int i,j,t,state;
	bool temp[25];
	memcpy(temp,num,sizeof(num));
	
	for (i=2;i<=20;i++) {
		if (num[i]) {
			int i2,j2;
			i2 = i;
			while (i2<=20) {
				num[i2] = false;
				for (j2=2;i2+j2<=20;j2++) {
					if (!num[j2]) {
						num[i2+j2] = false;
					}
				}
				i2 += i;
			}
			state = hash_num();
			if (hash[state] == -1) {
				hash[state] = dfs();
			}
			memcpy(num,temp,sizeof(num));
			if ( hash[state] == 'L') {
				return 'W';
			}
		}
	}
	return 'L';
}

int main()
{
	int i,j,t=1,ct;
	bool temp[25];
	int state;
	bool flag;
	memset(hash,-1,sizeof(hash));
	scanf("%d",&ct);
	while (ct--) {
		scanf("%d",&n);
		printf("Scenario #%d:\n",t++);
		
		memset(num,false,sizeof(num));
		for (i=0;i<n;i++) {
			scanf("%d",&j);
			num[j] = true;
		}
		memcpy(temp,num,sizeof(num));
		
		state = hash_num();
		if (hash[state] == -1) {
			hash[state] = dfs();
		}
		if (hash[state] == 'W') {
			printf("The winning moves are:");
			for (i=2;i<=20;i++) {
				if (num[i]) {
					int i2,j2;
					i2 = i;
					while (i2<=20) {
						num[i2] = false;
						for (j2=2;i2+j2<=20;j2++) {
							if (!num[j2]) {
								num[i2+j2] = false;
							}
						}
						i2 += i;
					}
					state = hash_num();
					if (hash[state] == -1) {
						hash[state] = dfs();
					}
					memcpy(num,temp,sizeof(num));
					if ( hash[state] == 'L') {
						printf(" %d",i);
					}
				}
			}
			
		}
		else {
			printf("There is no winning move");
		}
		printf(".\n\n");
	}
}