2026 ICPC 武汉邀请赛

点击查看题面

Problem C 相信着你

题目大意

在游戏对决中，玩家已知未来 $n$ 个回合的抽牌情况与怪物的攻击数值。玩家初始生命值脆弱，无法承受任何未被格挡的伤害（即一旦单回合怪物攻击力大于玩家当前护盾值，玩家立即死亡）。

具体规则如下：

• 卡牌类型：

• 打击：造成 $S$ 点伤害；

• 防御：提供 $D$ 点格挡值。

• 每个回合中：

• 回合开始时，清空上手手牌及上一回合剩余的格挡值；

• 玩家抽到 $a_i$ 张打击，以及 $5-a_i$ 张防御；

• 玩家最多可打出 $3$ 张手牌，每张牌至多打出一次；

• 怪物受到伤害累计达到或超过 $HP$ 时立即死亡，玩家获胜且游戏结束；

• 若怪物未死亡，怪物发动攻击，造成 $k_i$ 点伤害。若 $k_i$ 严格大于玩家本回合获得的格挡值，玩家死亡。

要求判定玩家能否在 $n$ 个回合内击败怪物。若能，输出 "Yes" 及最早获胜的回合数；若不能击败或中途死亡，输出 "No"。

数据范围：

• $1\le n\le 100$
• $1\le S,D\le 10$
• $1\le HP\le 100$
• $0\le a_i\le 5$
• $0\le k_i\le 50$

---

思路

本题是一道具有阶段独立性的贪心模拟题。

由于手牌和格挡值在每回合开始时均会被重置，回合与回合之间的唯一关联量即为怪物的剩余生命值 $HP$。因此，在每一个回合内，我们的目标高度统一：在确保生存的前提下，尽可能打出更多的“打击”牌；或者在该回合满足斩杀条件时直接全力输出。

具体决策逻辑如下：

1. 斩杀优先级最高（直接获胜）

• 游戏行动顺序中，玩家行动先于怪物。若玩家在当前回合全额出攻击牌能够直接清空怪物血量，则怪物根本没有机会发动攻击。
• 本回合最多可打出的打击牌数量为 $a_{max}=min(a_i,3)$。
• 若 $a_{max}\times S\ge HP$，则本回合可直接取得胜利，输出 "Yes" 与当前回合编号 $i$，提前终止程序。

2. 生存底线判定

• 若无法在本回合击败怪物，则必须防御怪物的攻击 $k_i$。
• 抵挡 $k_i$ 点伤害至少需要打出的防御牌张数为：

$$b_{\text{need}}=\lceil \frac{k_i}{D}\rceil =\lfloor \frac{k_i+D-1}{D}\rfloor$$

• 由于每回合最多只能打出 $3$ 张牌，且手牌中防御牌的总数仅为 $b_i=5-a_i$，因此若出现：

$$b_{\text{need}}>3\text{或}{b}_{\text{need}}>b_i$$

则说明当前手牌无法防住该次攻击，玩家必定死亡，直接输出 "No" 并退出。

3. 贪心输出最大化

• 在确保打出 $b_{\text{need}}$ 张防御牌后，本回合剩余可用的出牌槽位为 $3-b_{\text{need}}$。
• 为尽快击败敌人，剩余槽位应全部尽可能用于打出打击牌，打出数量为：

$$\text{cnt}=min(a_i,3-b_{\text{need}})$$

• 扣减怪物的生命值：$HP\leftarrow HP-\text{cnt}\times S$。

若经历完完整的 $n$ 回合后怪物仍未死亡，则判定为无法击败，输出 "No"。

---

复杂度分析

时间复杂度：$\mathcal{O}(n)$。整个模拟过程仅需单层循环遍历 $n$ 个回合，每个回合内均为常数级别的算术运算与条件分支，总运行时间远低于评测时限（约几十微秒）。

空间复杂度：$\mathcal{O}(1)$。算法仅维护了若干标量变量用于记录状态，未开辟额外动态数组或辅助容器，空间占用为常数级别。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void fc() {
    int n, s, d, hp;
    std::cin >> n >> s >> d >> hp;
    for (int i = 1; i <= n; i++) {
        int a, k;
        std::cin >> a >> k;
        int b = 5 - a;
 
        int a_mx = std::min(a, 3);
        if (a_mx * s >= hp) {
            std::cout << "Yes\n" << i;
            return;
        }
 
        int b_need = (k + d - 1) / d;
        if (b_need > 3 || b_need > b) {
            std::cout << "No\n";
            return;
        }
 
        int cnt = std::min(a, 3 - b_need);
        hp -= cnt * s;
    }

    std::cout << "No\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) fc();
    return 0;
}

---

Problem H 矩形切割

题目大意

在第一象限内有一个左下角为 $(0,0)$、右上角为 $(n,m)$ 的初始矩形。现对其进行 $q$ 次贯穿全局的切割操作，切割方式分为两类：

• 纵向切割 ($op=1$)：给定正整数 $k$，沿直线 $x=k$ 切割；
• 横向切割 ($op=2$)：给定正整数 $k$，沿直线 $y=k$ 切割。

每次切割后，均会产生若干更小的矩形。要求在每次切割完成后，实时输出当前所有小矩形中面积的最大值。保证不会在同一位置进行重复切割。

数据范围：

• $1\le n,m\le {10}^9$
• $1\le q\le 5\times {10}^5$
• 对于 $op=1$，$1\le k<n$
• 对于 $op=2$，$1\le k<m$

---

思路

本题是一道经典的一维解耦与动态有序集合维护问题。

1. 维度独立性分析

由于每一次横向切割或纵向切割都是完全贯通整个矩形平面的：

• 任何纵向切割 $x=k$ 仅会将水平方向的某一段长度划分为两半，对垂直方向的所有线段长度没有任何影响；
• 任何横向切割 $y=k$ 仅会将垂直方向的某一段长度划分为两半，对水平方向的所有线段长度没有任何影响。

经过若干次切割后，网格状划分产生的所有子矩形，其面积均可表示为：

$$S=\mathrm{\Delta }x\times \mathrm{\Delta }y$$

其中 $\mathrm{\Delta }x$ 为某一水平分段长度，$\mathrm{\Delta }y$ 为某一垂直分段长度。因为 $\mathrm{\Delta }x$ 和 $\mathrm{\Delta }y$ 的取值相互独立，最大面积即为当前水平方向的最大线段长度与当前垂直方向的最大线段长度的乘积：

$$S_{max}=\mathrm{\Delta }{x}_{max}\times \mathrm{\Delta }{y}_{max}$$

因此，原二维问题可以直接解耦为两个完全独立的一维动态区间分裂与最大值维护问题。

2. 区间维护与更新机制

针对单一维度（以长度为 $n$ 的水平轴为例）：

• 初始时，仅有一个完整的连续线段 $[1,n]$，其长度为 $n$。
• 当在位置 $k$ 处进行切割时：

1. 定位区间：在已有的不相交区间集合中，找到包含切割点 $k$ 的区间 $[l,r]$。利用有序映射 std::map<ll, pair<ll, ll>>（以左端点 $l$ 为键），通过 prev(mp.upper_bound(k)) 可在 $\mathcal{O}(\log q)$ 时间内定位。
2. 删除旧区间：将原区间的长度 $w=r-l+1$ 从维护全局长度集合的 std::multiset<ll> 中移除（注意需使用迭代器删除单次出现）。
3. 分裂与插入：将 $[l,r]$ 分裂为两段连续新区间 $[l,k]$ 与 $[k+1,r]$，长度分别为 $x=k-l+1$ 与 $y=r-k$。将分裂出的两个新区间信息写回 map，并将新长度 $x,y$ 插入 multiset。
4. 查询最大值：multiset 内部自动保持升序，其逆向迭代器 *s.rbegin() 即为当前维度的最大分段长度。

---

复杂度分析

时间复杂度：

• 初始化单次建表开销为 $\mathcal{O}(1)$。
• 每次切割操作中，包含一次 map 的二分查找、一次原区间移除，以及两次新区间与长度的插入操作，涉及的平衡树/红黑树操作均为单次 $\mathcal{O}(\log q)$。
• $q$ 次操作的总时间复杂度为 $\mathcal{O}(q\log q)$。在 $q=5\times {10}^5$ 的规模下，整体操作次数在可接受的计算阈值内。

空间复杂度：

• 随着切割推进，两个维度维护的区间总数不超过 $q+2$ 个。
• map 与 multiset 中存储的节点数与切割次数呈线性关系，总空间复杂度为 $\mathcal{O}(q)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, q;
 
struct st {
    std::map<ll, std::pair<ll, ll>> mp;  
    std::multiset<ll> s;                

    void init(int n) {
        mp[1] = {n, n};
        s.insert(n);
    }

    void modify(int k) { 
        auto it = std::prev(mp.upper_bound(k));
        ll l = it->first;
        auto [r, w] = it->second;
 
        s.erase(s.find(w));
 
        ll x = k - l + 1, y = r - k;
        mp[l] = {k, x};
        mp[k + 1] = {r, y};
         
        s.insert(x);
        s.insert(y);
    }
 
    ll get() { return *s.rbegin(); }
};

void fc() {
    std::cin >> n >> m >> q;
    st l, r;
    l.init(n);
    r.init(m);

    while (q--) {
        int op, k;
        std::cin >> op >> k;
        if (op == 1) {
            l.modify(k);
        } else {
            r.modify(k);
        }
 
        std::cout << (ll)l.get() * r.get() << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // std::cin>>t;
    while (t--) fc();
    return 0;
}

---