1 条题解

  • 0
    @ 2026-11-12 21:57:37

    [K] Stones(dp_k)题解

    题意简述

    一堆 KK 个石子,给定可取集合 AA。两人轮流从 AA 中选 xx 取走 xx 个石子,不能动者输。判断先手胜负。

    思路

    状态

    设 w(x)w(x) = 面对 xx 个石子的玩家是否必胜(true 为必胜)。

    转移

    $$w(x) = \bigvee_{a \in A,\; a \le x} \lnot w(x - a).$$

    即:只要存在一种取法,使得取完之后对手处于必败态,当前玩家就必胜。

    边界:w(x)=falsew(x) = \text{false} 当所有 a∈Aa \in A 都大于 xx(无法操作)。

    答案:w(K)w(K) 为真输出 First,否则 Second。

    为什么正确

    这是经典的"正常博弈 / 无偏博弈"结论——在有限、无环、双方可选动作相同的游戏里,局面胜负由"能否到达必败态"完全决定,可以自底向上递推。

    复杂度

    时间 O(NK)≤107O(NK) \le 10^7,空间 O(K)O(K)。

    参考代码

    #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;
    }
    

    易错点

    1. 输出是 First / Second(首字母大写),不是 Yes/No。
    2. 边界 x<min⁡Ax < \min A 一律必败——循环里 a[i] <= x 的条件保证正确。
    3. 别用"K mod K \bmod 什么"这类找规律的做法;样例 4/5 就是专门反直觉的(K=20K=20 必败,K=21K=21 必胜)。
    4. 如果 N=1,a1=1N=1, a_1 = 1:KK 为偶数时必败(样例 6 用 K=105K=10^5 验证)。

    数据说明

    共 21 组:6 组官方样例;N=1N=1 的多个 KK(奇偶、K=a1K=a_1、K=105K=10^5);aa 为 1..1001..100 全部、aa 为 1..1001..100 中随机 100 个、aa 在大范围内随机取 100 个(与 K=105K=10^5 组合);另有多组满规模随机,覆盖"存在/不存在必败后继"两种情形。

    • 1

    信息

    ID
    20
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者