[传智杯 #2 决赛] 补刀

题意

每个测试用例给出小兵血量 h、防御塔每次伤害 x、英雄每次伤害 y。

你可以在：

防御塔第一次攻击前
或每次防御塔攻击之后

选择是否让英雄攻击一次。

要求判断：能否让英雄在防御塔把小兵打死之前，亲自最后一下把它补掉。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include <bits/stdc++.h>
using namespace std;

int T;
long long h, x, y;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;

    while (T--) {
        cin >> h >> x >> y;

        // brute.cpp：小数据暴力。
        // 用集合维护“每次轮到英雄选择时，小兵可能剩下多少血”，
        // 枚举攻击/不攻击两种选择。
        set<long long> cur, nxt, seen;
        cur.insert(h);
        seen.insert(h);

        bool ok = false;

        while (!cur.empty() && !ok) {
            nxt.clear();

            for (long long hp : cur) {
                for (int atk = 0; atk <= 1; atk++) {
                    long long hp2 = hp - 1LL * atk * y;

                    if (atk == 1 && hp2 <= 0) {
                        ok = true;
                        break;
                    }

                    long long hp3 = hp2 - x;
                    if (hp3 <= 0) {
                        continue;
                    }

                    if (!seen.count(hp3)) {
                        seen.insert(hp3);
                        nxt.insert(hp3);
                    }
                }

                if (ok) {
                    break;
                }
            }

            cur.swap(nxt);
        }

        if (ok) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

brute.cpp 把“每次轮到英雄选择时，小兵可能剩余的血量”全部维护出来，枚举攻击和不攻击两种决策。

这可以帮助我们理解过程，但显然不适合 10^18 的数据范围。

把最后一次补刀单独拎出来

设英雄最后成功补刀时：

在这之前，防御塔已经攻击了 t 次
英雄也已经攻击了 t 次
接下来轮到英雄再攻击一次，把小兵打死

为什么英雄也是 t 次？

因为英雄可以在开头先打一次，然后每次塔打完后再决定要不要打。
如果我们只关心“最后一次补刀之前一共打了多少次”，显然最有利的策略是前面每轮都打，这样更容易把血量压到可补刀区间。

于是最后一次补刀前，小兵血量变成：

h - t * x - t * y

要让这一次英雄成功补刀，需要满足两件事：

这时小兵还活着
h - t * x > 0
英雄这一刀能把它打死
h - t * x - t * y <= y

第二个式子整理后得到：

h <= t * (x + y) + y

所以最早可能补刀的 t 是：

t = ceil((h - y) / (x + y))

当 h <= y 时，显然可以开头一刀直接补掉，这时 t = 0。

最后只剩一个判定

找到这个最早可能补刀的时刻 t 后，只需要检查：

t * x < h

这表示到了那时，防御塔还没有提前把小兵打死。

如果成立，答案就是 Yes；否则就是 No。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <bits/stdc++.h>
using namespace std;

int T;
long long h, x, y;

long long ceil_div(long long a, long long b) {
    return (a + b - 1) / b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;

    while (T--) {
        cin >> h >> x >> y;

        if (y == 0) {
            cout << "No\n";
            continue;
        }

        // 设在最后一次补刀之前，英雄一共已经攻击了 t+1 次，
        // 防御塔已经攻击了 t 次。
        // 那么此时小兵剩余血量为：
        // h - t * x - t * y
        // 只要它仍然大于 0，并且这一次英雄攻击能把它补死即可。
        long long t = 0;
        if (h > y) {
            t = ceil_div(h - y, x + y);
        }

        if ((__int128)t * x < h) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

复杂度

时间复杂度：每组 $O(1)$
空间复杂度： $O(1)$

总结

这题本质不是模拟，而是把“最后一次补刀发生时刻”抽象出来。

一旦设出：

塔已经打了 t 次
英雄已经打了 t 次

就能把过程压成一个简单不等式判定。