NOTE
比赛链接：The 2026 ICPC China Wuhan National Invitational and Hubei Provincial Programming Contest 补题 - QOJ.ac

C - Believe in You#

关键词：模拟

思路#

只需要维护整个过程玩家造成的伤害即可，首先考虑能否使用尽可能多的攻击牌斩杀，如果不能的话考虑先用尽可能少的防御牌保命，再将剩余的出牌次数全部用来攻击即可。由于防御只影响本回合是否存活，因此在保证存活的前提下，使用尽可能多的攻击牌一定不会差。

Code#

1
// Problem: C
2
// Contest: QOJ - The 2026 ICPC China Wuhan National Invitational and Hubei Provincial Programming Contest 补题
3
// URL: https://qoj.ac/contest/3757/problem/22150/statement/zh_cn
4
// Time: 2026-05-21 15:30:48
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n, s, d, hp;
29
    cin >> n >> s >> d >> hp;
30

31
    int damage = 0;
32
    for (int i = 1; i <= n; i++)
33
    {
34
        int a, k;
35
        cin >> a >> k;
36

37
        int damagemx = min(a, 3) * s;
38
        if (damage + damagemx >= hp)
39
        {
40
            cout << "Yes" << endl << i << endl;
41
            return;
42
        }
43

44
        int def = (k + d - 1) / d;
45
        if (def > 5 - a || def > 3)
46
        {
47
            cout << "No" << endl;
48
            return;
49
        }
50

51
        int cnt = min(a, 3 - def);
52
        damage += cnt * s;
53
    }
54
    cout << "No" << endl;
55
}
56

57
int main()
58
{
59
    fastio();
60

61
    int T = 1;
62
    // cin >> T;
63

64
    while (T--)
65
        solve();
66

67
    return 0;
68
}

H - Rectangle Cutting#

关键词：STL

思路#

初始有一个 n × m 的矩形。每次沿着某条完整的竖线 x = k 或横线 y = k 切一刀，要求每次切完后输出当前所有小矩形中的最大面积。题面给出 n, m ≤ 1e9，q ≤ 5e5，所以不能模拟所有的小矩形。

所有的竖切只会影响宽度段，所有的横切只会影响高度段，因此最大面积一定是最大宽度段乘以最大高度段。

所以问题变成，动态插入切割位置，并维护当前相邻切割线之间的最大间距。

使用 set<long long> pos 维护所有切割位置**（包括边界）**，使用 multiset<long long> len 维护所有相邻切割线之间的长度，初始时 xLen = {n}, yLen = {m}，因为可能有多个长度相同的区间，所以要使用 multiset。

当插入一刀时，我们先找到它所在的原区间，原来有一个长度，切完后变成两个长度，擦除原先的并更新。

NOTE
访问 set 的最后一个元素的反向迭代器是 s.rbegin()。

Code#

1
// Problem: H
2
// Contest: QOJ - The 2026 ICPC China Wuhan National Invitational and Hubei Provincial Programming Contest 补题
3
// URL: https://qoj.ac/contest/3757/problem/22155/statement/zh_cn
4
// Time: 2026-05-21 16:09:40
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void split(set<ll> &pos, multiset<ll> &len, ll k)
27
{
28
    auto itR = pos.upper_bound(k);
29
    auto itL = prev(itR);
30

31
    ll L = *itL;
32
    ll R = *itR;
33

34
    len.erase(len.find(R - L));
35
    len.insert(k - L);
36
    len.insert(R - k);
37

38
    pos.insert(k);
39
}
40

41
void solve()
42
{
43
    ll n, m, q;
44
    cin >> n >> m >> q;
45

46
    set<ll> xs, ys;
47
    multiset<ll> xlen, ylen;
48

49
    xs.insert(0);
50
    xs.insert(n);
51
    ys.insert(0);
52
    ys.insert(m);
53

54
    xlen.insert(n);
55
    ylen.insert(m);
56

57
    while (q--)
58
    {
59
        int op;
60
        ll k;
61
        cin >> op >> k;
62

63
        if (op == 1)
64
            split(xs, xlen, k);
65
        else
66
            split(ys, ylen, k);
67

68
        ll maxw = *xlen.rbegin();
69
        ll maxh = *ylen.rbegin();
70

71
        cout << maxw * maxh << endl;
72
    }
73
}
74

75
int main()
76
{
77
    fastio();
78

79
    int T = 1;
80
    // cin >> T;
81

82
    while (T--)
83
        solve();
84

85
    return 0;
86
}