P8666 [蓝桥杯 2018 省 A] 三体攻击 题解

· · 题解

简要题意

有 A \times B \times C 艘战舰排列成 A \times B \times C 的立体矩阵，此时有 m 次攻击，每次攻击有7组数据： la_t，ra_t，lb_t， rb_t， lc_t， rc_t， h_t。代表的是所有坐标 x，y，z 满足 x \in [la_t, rb_t] ，y \in [lb_t, rb_t] ，z \in [lc_t, rc_T] 的战舰都会受到 h_t 点生命值的攻击。现在已知每个战舰的生命值，求出第一个爆炸的战舰是在第几轮攻击爆炸的。（爆炸指生命值 < 0 的战舰）

思路

先定义结构体储存每轮攻击信息：

struct node{
    int la, ra, lb, rb, lc, rc, h;
}t[N];

刚看到这道题的时候立马就想到了建一个三维的差分数组，每次进攻就对差分数组操作一次然后再判断是否有战舰爆炸，可是很容易发现这个思路会超时。

再仔细想一想可以发现，这 m 次进攻（想象成一条单调的时间轴，从时间轴上找到第 m 次进攻的时间）就可以用二分来搜索，代码：

int l=1, r=m;
while(l < r)
{
    int mid=(l+r)/2;
    if(check(mid))  r=mid;
    else    l=mid+1;
}
cout << l;

问题又来了， check(mid) 怎么写？思考一下对于二分每个 mid 在第 mid 轮攻击时，如果此轮攻击过后，有战舰爆炸，说明在第 mid 轮攻击之前（含 mid ）已经有战舰爆炸了，此时向左搜索，有 r=mid ；但如果没有战舰爆炸，说明第 mid 轮攻击之后才有战舰爆炸，此时向右搜索，有 l=mid+1 。于是 check(mid) 的框架就有了：

bool check(int mid)
{
    mem(b, 0);
    for (int i=1; i<=mid; i++)
    {
        //三维差分
    }
    for(int i=1;i<=A;i++)
    {
        for(int j=1;j<=B;j++)
        {
            for(int k=1;k<=C;k++)
            {
                //构造出所有受到伤害的战舰的数组
                if(/*每个战舰收到的伤害大于该战舰生命值*/)   return 1;
            }
        }
    }
    return 0;
}

现在，check(mid) 写完了，最后一步就是写差分了，建议使用一维数组储存，三维数组会 RE ，而且写起来还很麻烦。使用一维数组的时候，就可以用题目中做给的公式储存了：第 (i, j, k) 个数储存到 d[((i-1) \times B + (j-1)) \times C + (k-1)+1] 当中，为了方便，我们把这个公式定义成一个函数：

int get_xyz(int x, int y, int z)
{
    return ((x-1)*B+(y-1))*C+(z-1)+1;
}

建立差分的代码也有了：

for (int i=1; i<=mid; i++)
{
    b[get_xyz(t[i].la, t[i].lb, t[i].lc)]+=t[i].h;

        b[get_xyz(t[i].ra+1, t[i].lb, t[i].lc)]-=t[i].h;
        b[get_xyz(t[i].la, t[i].rb+1, t[i].lc)]-=t[i].h;
        b[get_xyz(t[i].la, t[i].lb, t[i].rc+1)]-=t[i].h;

        b[get_xyz(t[i].ra+1, t[i].rb+1, t[i].lc)]+=t[i].h;
        b[get_xyz(t[i].ra+1, t[i].lb, t[i].rc+1)]+=t[i].h;
        b[get_xyz(t[i].la, t[i].rb+1, t[i].rc+1)]+=t[i].h;

        b[get_xyz(t[i].ra+1, t[i].rb+1, t[i].rc+1)]-=t[i].h;

        //其实类似于三维数组的差分，本质就是容斥原理
        //所以只要把get_xyz(i, j, k)想成三维数组的a[i][j][k]就好了
}

判断的代码也可以补全了：

for(int i=1;i<=A;i++)
{
    for(int j=1;j<=B;j++)
    {
        for(int k=1;k<=C;k++)
        {
            b[get_xyz(i, j, k)]+=
            b[get_xyz(i-1, j, k)]+
            b[get_xyz(i, j-1, k)]+
            b[get_xyz(i, j, k-1)]-
            b[get_xyz(i-1, j-1, k)]-
            b[get_xyz(i-1, j, k-1)]-
            b[get_xyz(i, j-1, k-1)]+
            b[get_xyz(i-1, j-1, k-1)];
            if(b[get_xyz(i, j, k)] > d[get_xyz(i, j, k)])   return 1;
        }
    }
}
return 0;

完整代码

#include <bits/stdc++.h>
#define ll long long
#define mem(a, m) memset(a, m, sizeof(a));
using namespace std;

const int N=1e7+5;
int A, B, C, m;
int d[N];//血量
int b[N];//差分 
struct node{
    int la, ra, lb, rb, lc, rc, h;
}t[N];
int get_xyz(int x, int y, int z)
{
    return ((x-1)*B+(y-1))*C+(z-1)+1;
}
bool check(int mid)
{
    mem(b, 0);
    for (int i=1; i<=mid; i++)
    {
        b[get_xyz(t[i].la, t[i].lb, t[i].lc)]+=t[i].h;

        b[get_xyz(t[i].ra+1, t[i].lb, t[i].lc)]-=t[i].h;
        b[get_xyz(t[i].la, t[i].rb+1, t[i].lc)]-=t[i].h;
        b[get_xyz(t[i].la, t[i].lb, t[i].rc+1)]-=t[i].h;

        b[get_xyz(t[i].ra+1, t[i].rb+1, t[i].lc)]+=t[i].h;
        b[get_xyz(t[i].ra+1, t[i].lb, t[i].rc+1)]+=t[i].h;
        b[get_xyz(t[i].la, t[i].rb+1, t[i].rc+1)]+=t[i].h;

        b[get_xyz(t[i].ra+1, t[i].rb+1, t[i].rc+1)]-=t[i].h;
    }
    for(int i=1;i<=A;i++)
    {
        for(int j=1;j<=B;j++)
        {
            for(int k=1;k<=C;k++)
            {
                b[get_xyz(i, j, k)]+=
                b[get_xyz(i-1, j, k)]+
                b[get_xyz(i, j-1, k)]+
                b[get_xyz(i, j, k-1)]-
                b[get_xyz(i-1, j-1, k)]-
                b[get_xyz(i-1, j, k-1)]-
                b[get_xyz(i, j-1, k-1)]+
                b[get_xyz(i-1, j-1, k-1)];
                if(b[get_xyz(i, j, k)] > d[get_xyz(i, j, k)])   return 1;
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> A >> B >> C >> m;
    for(int i=1;i<=A;i++)
    {
        for(int j=1;j<=B;j++)
        {
            for(int k=1;k<=C;k++)
            {
                cin >> d[get_xyz(i, j, k)];
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        cin >> t[i].la >> t[i].ra >> t[i].lb >> t[i].rb >> t[i].lc >> t[i].rc >> t[i].h;
    }
    int l=1, r=m;
    while(l < r)
    {
        int mid=(l+r)/2;
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
    cout << l;
    return 0;
}