UVA 1558 - Number Game

题目链接

题意：20之内的数字，每次能够选一个数字，然后它的倍数，还有其它已选数的倍数组合的数都不能再选，谁先不能选数谁就输了，问赢的方法

思路：利用dp记忆化去求解，要输出方案就枚举第一步就可以，状态转移过程中，选中一个数字，对应的变化写成一个函数，然后就是普通的博弈问题了，必胜态之后必有必败态，必败态之后全是必胜态

代码：

#include <stdio.h>

#include <string.h>

const int N = 1050005;

int t, n, w, start, dp[N], ans[25], an;

int getnext(int state, int x) {

	for (int i = x; i <= 20; i += x)

 		if (state&(1<<(i - 2)))

   			state ^= (1<<(i - 2));

	for (int i = 2; i <= 20; i++) {

		if (state&(1<<(i - 2))) {

			for (int j = x; i - j >= 2; j += x) {

				if (!(state&(1<<(i - j - 2)))) {

					state ^= (1<<(i - 2));

					break;

				}

   			}

  		}

 	}

 	return state;

}

int dfs(int state) {

	if (dp[state] != -1) return dp[state];

	if (state == 0) return dp[state] = 0;

	for (int i = 2; i <= 20; i++) {

		if (state&(1<<(i - 2))) {

			if (dfs(getnext(state, i)) == 0)

				return dp[state] = 1;

  		}

 	}

 	return dp[state] = 0;

}

int main() {

	int cas = 0;

	scanf("%d", &t);

	memset(dp, -1, sizeof(dp));

	while (t--) {

		start = 0; an = 0;

		scanf("%d", &n);

		for (int i = 0; i < n; i++) {

			scanf("%d", &w);

			start |= (1<<(w - 2));

  		}

  		for (int i = 2; i <= 20; i++) {

  			if (start&(1<<(i - 2))) {

  				if (dfs(getnext(start, i)) == 0)

  					ans[an++] = i;

     		}

    	}

    	printf("Scenario #%d:\n", ++cas);

    	if (an) {

    		printf("The winning moves are:");

    		for (int i = 0; i < an; i++)

    			printf(" %d", ans[i]);

  			printf(".\n");

     	}

     	else printf("There is no winning move.\n");

     	printf("\n");

 	}

	return 0;

}