---
# System prepended metadata

title: 题解：猫萌的敌人

---

# 题解：猫萌的敌人

[题目链接](https://vjudge.net/contest/475403#problem/B)

## 分析

极度容易WA的题，特殊情况有点多，由攻击至少1这个点，会产生很多细节坑。具体有哪些细节坑在下面的参考代码的注释里有列出。

在去除掉特殊情况后，重点关注点在枚举的方法上。首先，对于血和防守力的分配上，方案其实是唯一的，因为防守力必然分配为对方攻击力-1，剩下的就是血，这样必然是能支撑最多个回合的方案。所以说，防守力可以算为已知量，那么剩下的两个量，就是在解一个不等式方程组，枚举方法可以有多种，可以枚举回合数，可以直接枚举分配的点数（攻击或血），这样就得到一个时间复杂度为 $O(n)$ 级的算法。

## 参考代码

```cpp
#include <algorithm>
#include <iostream>

using namespace std;

bool solve(int v, int l, int d, int a) {
    if (v == 0)         // 自己没有点数
        return false;
    a = max(1, a);      // 对方攻击至少1
    if (v >= l + d + 1) // 全力进攻，留1点血
        return true;
    if (v >= a + l - 1) // 全力防守，血比对方多
        return true;
    if (l <= 1)         // 对方支撑不住1次攻击
        return true;

    // 枚举攻击次数
    for (int i = 2; i < v; i++) {
        int at = (l + (i - 1)) / i;    // 最少需要的攻击力
        int lv = v - (at + d);         // 分配攻击力后剩余点数
        if (lv >= (a - 1) + i) // 先分配a-1的防守，再判断血够不够
            return true;
    }
    return false;
}

int main(int argc, char *argv[]) {
    int n, k, a, b, c;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> k >> a >> b >> c;
        bool res = solve(k, a, b, c);
        cout << (res ? "Yes" : "No") << endl;
    }
    return 0;
}
```