P8666 题解

· · 题解

题意大家应该都看懂了，不放了。

思路：

这道题是在 m 次攻击，是一个时间轴，又符合单调性，一下子就想到了二分答案来做：

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

大家应该都学过差分吧，但在一个立体空间里，三维差分又怎么做呢？

三维差分和一维差分差不多，只是在三维空间里操作，脑海中想象一个立方体，模版代码如下：

sub[x1][y1][z1]+=d;      //前：左下顶点，即区间的起始点
sub[x2+1][y1][z1]-=d;    //前：右下顶点的右边一个点
sub[x1][y1][z2+1]-=d;    //前：左上顶点的上面一个点
sub[x2+1][y1][z2+1]+=d;  //前：右上顶点的斜右上方一个点
sub[x1][y2+1][z1]-=d;    //后：左下顶点的后面一个点
sub[x2+1][y2+1][z1]+=d;  //后：右下顶点的斜右后方一个点
sub[x1][y2+1][z2+1]+=d;  //后：左上顶点的斜后上方一个点
sub[x2+1][y2+1][z2+1]-=d;//后：右上顶点的斜右上后方一个点，即区间终点的后一个点

现在，check 函数写完了，但 (x_1,y_1,z_1) 的范围可能会 MLE，将它们带入题目中的公式：[(x-1)\times B+y-1]\times C+k，在存到差分数组里，最后计算前缀和，如果有大于战舰本生的生命，直接返回 1，否则返回 0。

最后附上 AC 代码：

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int A,B,C,m,s[N];
int X1[N],X2[N],Y1[N],Y2[N],Z1[N],Z2[N];
int d[N],l,r,sub[N];
int num(int x,int y,int z){
    if(x>A||y>B||z>C)return 0;
    return ((x-1)*B+y-1)*C+z;
}//将三维转化成一维
void xxs(int x,int y,int z,int d){sub[num(x,y,z)]+=d;}
bool pre(){
    //三个方向计算前缀和
    for(int i=1;i<=A;i++)
        for(int j=1;j<=B;j++)
            for(int k=1;k<=C;k++)xxs(i,j,k+1,sub[num(i,j,k)]);
    for(int i=1;i<=A;i++)
        for(int k=1;k<=C;k++)
            for(int j=1;j<=B;j++)xxs(i+1,j,k,sub[num(i,j,k)]);
    for(int j=1;j<=B;j++)
        for(int k=1;k<=C;k++)
            for(int i=1;i<=A;i++)xxs(i,j+1,k,sub[num(i,j,k)]);
    for(int i=1;i<=A*B*C;i++)
        if(sub[i]>s[i])return 1;
    return 0;
}
bool check(int x){
    memset(sub,0,sizeof(sub));//记住这里要清空，不然之前的还会留在数组中
    for(int i=1;i<=x;i++){
        xxs(X1[i],Y1[i],Z1[i],d[i]);
        xxs(X2[i]+1,Y1[i],Z1[i],-d[i]);
        xxs(X1[i],Y1[i],Z2[i]+1,-d[i]);
        xxs(X2[i]+1,Y1[i],Z2[i]+1,d[i]);
        xxs(X1[i],Y2[i]+1,Z1[i],-d[i]);
        xxs(X2[i]+1,Y2[i]+1,Z1[i],d[i]);
        xxs(X1[i],Y2[i]+1,Z2[i]+1,d[i]);
        xxs(X2[i]+1,Y2[i]+1,Z2[i]+1,-d[i]);
    }//对sub数组进行差分
    return pre();
}
int main(){
    cin>>A>>B>>C>>m;
    for(int i=1;i<=A*B*C;i++)cin>>s[i];
    for(int i=1;i<=m;i++)cin>>X1[i]>>X2[i]>>Y1[i]>>Y2[i]>>Z1[i]>>Z2[i]>>d[i];
    int l=1,r=m;
    while(l+1<r){//二分答案，取临界点
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}

这种代码很多的题，千万不要在 main 函数里写一大堆，你自己也会眼花的，记住：函数是编程。