[蓝桥杯]三体攻击

三体攻击

题目描述

三体人将对地球发起攻击。为了抵御攻击，地球人派出 A × B × CA × B × C 艘战舰，在太空中排成一个 AA 层 BB 行 CC 列的立方体。其中，第 ii 层第 jj 行第 kk 列的战舰（记为战舰 (i, j, k)(i, j, k)）的生命值为 d(i, j, k)d(i, j, k)。

三体人将会对地球发起 mm 轮"立方体攻击"，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 tt 轮攻击用 7 个参数 lat, rat, lbt, rbt, lct, rct, htlat, rat, lbt, rbt, lct, rct, ht 描述；

所有满足 i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct]i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct] 的战舰 (i, j, k)(i, j, k) 会受到 htht 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。

地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

输入描述

输入格式：

第一行包括 4 个正整数 A, B, C, mA, B, C, m；

第二行包含 A × B × CA × B × C 个整数，其中第((i − 1)×B + (j − 1)) × C + (k − 1)+1((i − 1)×B + (j − 1)) × C + (k − 1)+1 个数为 d(i, j, k)d(i, j, k)；

第 3 到第 mm + 2 行中，第 (t − 2)(t − 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, htlat, rat, lbt, rbt, lct, rct, ht。

其中, A × B × C ≤ 106, m ≤ 106, 0 ≤ d(i, j, k), ht ≤ 109A × B × C ≤ 106, m ≤ 106, 0 ≤ d(i, j, k), ht ≤ 109。

输出描述

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

输入输出样例

示例

输入

2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

输出

2

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

总通过次数: 1178  |  总提交次数: 1761  |  通过率: 66.9%

难度: 困难   标签: 2018, 差分, 省赛

算法思路：三维差分 + 二分查找

核心思想

• ​​问题本质​​：在三维空间中执行区间修改（增加伤害值），并找到第一次有战舰生命值≤0的攻击轮次
• ​​关键挑战​​：直接暴力模拟复杂度为O(m·ABC)，高达10¹²，会超时
• ​​优化策略​​：
  1. ​​三维差分​​：将区间修改转化为8个端点的O(1)操作
  2. ​​二分查找​​：利用伤害累积的单调性，在O(logm)时间内定位爆炸轮次
  3. ​​前缀和还原​​：差分数组通过三维前缀和计算实际伤害值

代码实现（C++）

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;

const int MAXN = 1e6 + 10;
int A, B, C, m;
LL s[MAXN];      // 存储初始生命值
LL diff[MAXN];   // 三维差分数组
int attacks[MAXN][7];  // 存储攻击参数

// 三维坐标转一维索引
inline int get_idx(int i, int j, int k) {
    return i * (B + 2) * (C + 2) + j * (C + 2) + k;
}

// 原始生命值索引
inline int get_orig_idx(int i, int j, int k) {
    return (i - 1) * B * C + (j - 1) * C + (k - 1);
}

// 检查前mid轮攻击是否导致爆炸
bool check(int mid) {
    memset(diff, 0, sizeof(diff));
    
    // 1. 应用差分修改
    for (int t = 0; t < mid; ++t) {
        int lat = attacks[t][0], rat = attacks[t][1];
        int lbt = attacks[t][2], rbt = attacks[t][3];
        int lct = attacks[t][4], rct = attacks[t][5];
        LL ht = attacks[t][6];
        
        diff[get_idx(lat, lbt, lct)] += ht;
        diff[get_idx(rat + 1, lbt, lct)] -= ht;
        diff[get_idx(lat, rbt + 1, lct)] -= ht;
        diff[get_idx(lat, lbt, rct + 1)] -= ht;
        diff[get_idx(rat + 1, rbt + 1, lct)] += ht;
        diff[get_idx(rat + 1, lbt, rct + 1)] += ht;
        diff[get_idx(lat, rbt + 1, rct + 1)] += ht;
        diff[get_idx(rat + 1, rbt + 1, rct + 1)] -= ht;
    }
    
    // 2. 三维前缀和计算
    // k方向
    for (int i = 1; i <= A; ++i)
        for (int j = 1; j <= B; ++j)
            for (int k = 1; k <= C; ++k)
                diff[get_idx(i, j, k)] += diff[get_idx(i, j, k - 1)];
    
    // j方向
    for (int i = 1; i <= A; ++i)
        for (int k = 1; k <= C; ++k)
            for (int j = 1; j <= B; ++j)
                diff[get_idx(i, j, k)] += diff[get_idx(i, j - 1, k)];
    
    // i方向
    for (int j = 1; j <= B; ++j)
        for (int k = 1; k <= C; ++k)
            for (int i = 1; i <= A; ++i)
                diff[get_idx(i, j, k)] += diff[get_idx(i - 1, j, k)];
    
    // 3. 检查是否爆炸
    for (int i = 1; i <= A; ++i)
        for (int j = 1; j <= B; ++j)
            for (int k = 1; k <= C; ++k) {
                int orig_idx = get_orig_idx(i, j, k);
                if (diff[get_idx(i, j, k)] > s[orig_idx])
                    return true;
            }
    return false;
}

int main() {
    scanf("%d%d%d%d", &A, &B, &C, &m);
    int total = A * B * C;
    
    // 读入初始生命值
    for (int i = 0; i < total; ++i)
        scanf("%lld", &s[i]);
    
    // 读入攻击参数
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < 7; ++j)
            scanf("%d", &attacks[i][j]);
    
    // 二分查找爆炸轮次
    int L = 1, R = m;
    while (L < R) {
        int mid = (L + R) >> 1;
        if (check(mid)) R = mid;
        else L = mid + 1;
    }
    printf("%d\n", L);
    return 0;
}

代码解析

1. ​​坐标映射​​：
   • get_idx()：三维坐标→一维索引（用于差分数组）
   • get_orig_idx()：原始生命值存储位置计算
2. ​​差分操作​​：
   • 每轮攻击转化为8个端点的修改操作（4个加伤害，4个减伤害）
3. ​​前缀和计算​​：
   • 分三个维度递推计算实际伤害值：
     • 先k方向（固定i,j）
     • 再j方向（固定i,k）
     • 最后i方向（固定j,k）
4. ​​二分框架​​：
   • 右边界R维护首次爆炸轮次
   • 左边界L维护未爆炸的轮次

实例验证

​​输入样例​​：

2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

​​执行过程​​：

1. ​​第一轮攻击后​​：
   • 伤害分布：4个位置伤害=1
   • 最小生命值：1-1=0 → 未爆炸
2. ​​第二轮攻击后​​：
   • 伤害分布：(1,1,1)=2, (1,2,1)=2
   • 最小生命值：1-2=-1 → 爆炸
3. ​​二分输出​​：2（符合预期）

测试点设计

优化建议

1. ​​内存优化​​：

   // 动态分配差分数组
   LL* diff = new LL[(A+2)*(B+2)*(C+2)]();

   减少固定数组大小，根据输入动态分配

2. ​​时间优化​​：

   // 循环展开（i方向）
   #pragma unroll(4)
   for (int i = 1; i <= A; ++i)

   编译器指令展开循环，减少分支预测开销

3. ​​二分优化​​：

   // 指数增长搜索
   int step = 1;
   while (!check(step) step *= 2;
   int L = step/2, R = min(step, m);

   先指数增长确定范围，再二分

4. ​​差分压缩​​：

   // 合并相同修改
   if (ht == prev_ht && region_overlap(...)) 
       merge_attacks();

   合并连续相同伤害值的攻击，减少操作次数