UVA 1558 - Number Game(博弈dp)
number DP UVa Game 博弈
2023-09-27 14:27:04 时间
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; }
相关文章
- <LeetCode OJ> 268. Missing Number
- _.clamp(number, [lower], upper)
- HDU 3948 The Number of Palindromes
- ZOJ 2836 Number Puzzle
- 第四十六章 Caché 函数大全 $NUMBER 函数
- HDU 5898 odd-even number (数位DP)
- number (1)eclipse 连接数据库报错 数据库信息不对导致的出错
- 《C++游戏编程入门(第4版)》——2.12 Guess My Number游戏简介
- 【LeetCode】191. Number of 1 Bits
- 1038. Recover the Smallest Number (30)
- [LeetCode] 1276. Number of Burgers with No Waste of Ingredients 不浪费原料的汉堡制作方案
- [LeetCode] Convert a Number to Hexadecimal 数字转为十六进制
- 【bzoj5064】B-number 数位dp
- 920. Number of Music Playlists
- C - Harmonic Number(调和级数+欧拉常数)