首页 > 代码库 > [UOJ Round#4 A] [#51] 元旦三侠的游戏
[UOJ Round#4 A] [#51] 元旦三侠的游戏
题目链接：UOJ - 51
据说这题与 CF 39E 类似。
题目分析
一看题目描述，啊，博弈论，不会！等待爆零吧...
这时，XCJ神犇拯救了我，他说，这题可以直接搜啊。
注意！是用记忆化搜索，状态为 (a, b) 。
是这样的：我们从后面倒着推，对于一个无法再增加 a 或 b 的 (a, b) 状态，当前走的人必败。这是终止的状态。
而对于一个不是终止状态的状态 (a, b) ，可能有两种后继状态 (a + 1, b) || (a, b + 1) ，我们递归先求出这两个后继状态是必败还是必胜。
如果两个后继状态中有一个是必败的，那么就存在走法使得下一个走的人必败，那么一定会走那个状态（因为所有人都足够聪明），当前状态就是必胜的。
否则，无论怎么选择，下一个走的人都必胜，那么当前状态就是必败的。
注意，如果某一个后继状态不合法，那么就当作一个必胜状态吧，因为当前不能那样走。
需要注意的是，当 b = 1，合法的 a 有 n 个，是不能搜完也不能存储的，我们把 b = 1 的状态分为两类：
1) a <= sqrt(n) 这种状态下，b 可能会增加， 所以和别的状态一样处理。
2) a > sqrt(n) 这样的状态，b是不能增加的，直接看 n - a 的奇偶就好了。每次用到这种状态的时候就单独做一下。
这样能求出所有可行状态的必胜或必败属性，由于对于每个 b ，可行 a 的个数差别过大，我们对每个 b 用一个 vector 存所有可行 a 的答案 （STL就是好！）。
对于每一个查询直接输出就好了。
特别注意的是！一定要记忆化搜索啊！不记忆化就TLE到爆啊！！状态重复搜了太多太多次啊！！
写代码时出现的错误：这样判断了后继状态 if (DFS(x + 1, y) && DFS(x, y + 1)) 这样是万万不可以的！！后面的一个 DFS(x, y+1) 放在了&& 之后，只要前面的值为 true ，后面的这个 DFS 直接就不调用了！！就跪了！！
代码
#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>using namespace std;const int MaxN = 1000000 + 5;int n, m, a, b, SqrtN, Top;vector<int> E[35];typedef long long LL;bool Pow(int a, int b) { LL f, ret; f = a; ret = 1ll; while (b) { if (b & 1) { ret *= f; if (ret > n) return true; } b >>= 1; f *= f; } if (ret > n) return true; return false;}bool DFS(int x, int y) { if (y != 1 && (int)E[y].size() > x && E[y][x] != 0) return (E[y][x] == 1); if (Pow(x, y)) return true; if (y == 1 && x > SqrtN) { if ((n - x) & 1) return true; else return false; } bool Flag1, Flag2; Flag1 = DFS(x + 1, y); Flag2 = DFS(x, y + 1); while ((int)E[y].size() <= x) E[y].push_back(0); if (Flag1 && Flag2) { E[y][x] = -1; return false; } else { E[y][x] = 1; return true; }}bool WillWin(int x, int y) { if (y == 1 && x > SqrtN) { if ((n - x) & 1) return true; else return false; } return (E[y][x] == 1);}int main() { scanf("%d%d", &n, &m); SqrtN = (int)sqrt(n * 1.0); DFS(2, 1); for (int i = 1; i <= m; ++i) { scanf("%d%d", &a, &b); if (WillWin(a, b)) printf("Yes\n"); else printf("No\n"); } return 0;}
[UOJ Round#4 A] [#51] 元旦三侠的游戏