题目核心分析

本题是博弈论中的最优策略对抗问题，黑客与主席轮流行动（黑客先手），需判断黑客是否能在主席最优防御下，将服务器算力 $c_G$ 降至 $0$ 或以下。核心矛盾在于“黑客攻击/破墙”与“主席反击/破墙”的策略博弈，需通过数学推导简化状态，避免暴力搜索所有可能。

关键概念与公式定义

在分析代码前，先明确题目中核心变量与操作的数学表达：

• $S$：单个防火墙对攻击的固定削弱值。
• 黑客状态：算力 $c_H$、防火墙数 $f_H$（代码中对应 $a0, b0$）。
• 服务器状态：算力 $c_G$、防火墙数 $f_G$（代码中对应 $a1, b1$）。
• 攻击伤害公式：
  黑客攻击服务器时，实际伤害为 $\max\{c_H - f_G \cdot S, 0\}$；
  主席攻击黑客时，实际伤害为 $\max\{c_G - f_H \cdot S, 0\}$。
• 破墙操作：黑客破墙使 $f_G$ 减 $1$，主席破墙使 $f_H$ 减 $1$（均最低至 $0$）。

代码核心逻辑解析

代码采用 记忆化搜索（DFS）+ 数学剪枝 策略，通过递归探索所有可能的博弈状态，并利用哈希表存储中间结果避免重复计算，同时通过公式推导减少无效状态遍历。

1. 状态简化与初始化

代码首先对初始状态进行预处理，消除“防火墙过量导致攻击无效”的冗余状态：

cin(a0, b0, a1, b1), puts(dfs(a0 - b1 * S, b1, a1 - b0 * S, b0) ? "YES" : "NO");

• 黑客实际有效算力：$a0 - b1 \cdot S$（减去服务器 $b1$ 个防火墙的总削弱）。
• 服务器实际有效算力：$a1 - b0 \cdot S$（减去黑客 $b0$ 个防火墙的总削弱）。
• 目的：若初始有效算力 $\leq 0$，可直接判断攻击无效，简化后续递归。

2. 记忆化搜索主体（DFS函数）

dfs(a0, b0, a1, b1) 函数返回值为 bool，表示当前状态下（黑客：$a0$ 算力、$b0$ 防火墙；服务器：$a1$ 算力、$b1$ 防火墙），黑客是否能必胜。

函数内通过 多条件分支 覆盖所有博弈场景，核心分支逻辑如下：

（1）终止状态判断

直接判断当前状态是否为“必胜/必败”终点：

if (b0 < 0 || (a0 <= 0 && b0 == 0))
    return 0;  // 黑客无防火墙且算力≤0，无法行动，必败
if (b1 < 0 || (a1 <= 0 && b1 == 0))
    return 1;  // 服务器无防火墙且算力≤0，黑客必胜

（2）冗余状态消除

当双方算力均 $\leq 0$ 时，通过“同步破墙”减少重复状态：

if (a0 <= 0 && a1 <= 0) {
    // 计算最多可同步破墙次数x（双方各破x次，算力同步增加x*S）
    ll x = min(b0, b1, min(-a0, -a1) / S + 1);
    b0 -= x, b1 -= x, a0 += x * S, a1 += x * S;
}

（3）核心场景分支

针对“黑客算力≤0”“服务器算力≤0”“攻击直接有效”等关键场景，直接推导结果，避免递归深入：

3. 数学剪枝与辅助函数

代码通过多个辅助函数推导“攻击有效性”“最小破墙次数”等关键参数，大幅减少递归深度：

（1）攻击有效性判断（chk 函数）

判断当前状态下，黑客是否能通过后续操作让攻击始终有效：

bool chk(ll a0, ll b0, ll a1, ll b1) {
    ll pa0 = a0 + b0 * (S - a1);  // 黑客破b0次墙后的算力
    return pa0 > S;  // 若算力> S，攻击始终有效（服务器无防火墙后伤害=pa0）
}

（2）破墙次数计算（calc 函数）

通过二分查找，计算黑客需要的最小初始算力，确保能在主席干扰下获胜：

ll calc(ll b0, ll a1, ll b1) {
    if (mp.find({b0, a1, b1}) != mp.end())
        return mp[{b0, a1, b1}];  // 记忆化：返回已计算结果
    ll &l = mp[{b0, a1, b1}] = 0, r = S, mid;
    // 二分查找最小a0，使黑客在该算力下必胜
    for (; l < r;)
        if (chk1(mid = (l + r) >> 1, b0, a1, b1))
            r = mid;
        else
            l = mid + 1;
    return l;
}

（3）双向攻击判断（chk1 函数）

判断主席两种反击方式（破墙/攻击）是否均能让黑客必败：

bool chk1(ll a0, ll b0, ll a1, ll b1) {
    // 主席破墙：黑客算力+a0+S，防火墙-1；主席攻击：黑客算力-a0，服务器算力不变
    return (!dfs(a1, b1, a0 + S, b0 - 1)) || (!dfs(a1 - a0, b1, a0, b0));
}

代码复杂度分析

• 时间复杂度：单次查询复杂度为 $O(\log S)$（二分查找），结合记忆化搜索，避免重复计算相同状态，总复杂度为 $O(Q \cdot \log S)$，可轻松处理 $Q \leq 2.5 \times 10^5$ 的数据规模。
• 空间复杂度：记忆化哈希表存储的状态数与 $b0, a1, b1$ 相关，实际运行中因剪枝策略，空间占用可控，满足 $256\text{MB}$ 限制。