1 条题解
-
0
[K] Stones(dp_k)题解
题意简述
一堆 个石子,给定可取集合 。两人轮流从 中选 取走 个石子,不能动者输。判断先手胜负。
思路
状态
设 = 面对 个石子的玩家是否必胜(
true为必胜)。转移
$$w(x) = \bigvee_{a \in A,\; a \le x} \lnot w(x - a).$$即:只要存在一种取法,使得取完之后对手处于必败态,当前玩家就必胜。
边界: 当所有 都大于 (无法操作)。
答案: 为真输出
First,否则Second。为什么正确
这是经典的"正常博弈 / 无偏博弈"结论——在有限、无环、双方可选动作相同的游戏里,局面胜负由"能否到达必败态"完全决定,可以自底向上递推。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <vector> using namespace std; int main() { int n, k; scanf("%d %d", &n, &k); vector<int> a(n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); vector<char> win(k + 1, 0); for (int x = 1; x <= k; x++) for (int i = 0; i < n; i++) if (a[i] <= x && !win[x - a[i]]) { win[x] = 1; break; } puts(win[k] ? "First" : "Second"); return 0; }易错点
- 输出是
First/Second(首字母大写),不是Yes/No。 - 边界 一律必败——循环里
a[i] <= x的条件保证正确。 - 别用" 什么"这类找规律的做法;样例 4/5 就是专门反直觉的( 必败, 必胜)。
- 如果 : 为偶数时必败(样例 6 用 验证)。
数据说明
共 21 组:6 组官方样例; 的多个 (奇偶、、); 为 全部、 为 中随机 100 个、 在大范围内随机取 100 个(与 组合);另有多组满规模随机,覆盖"存在/不存在必败后继"两种情形。
- 输出是
- 1
信息
- ID
- 20
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者