P8666

_O_v_O_ · 2023-09-02 14:16:27 · 题解

初步思想：

拿三维数组存，每次暴力加，在看所有战舰是否有爆炸的。

但这时间复杂度是 O(A\times B\times C\times m)，空间复杂度是 ({10^6})^3（三维，每维是 10^6），明显会爆。

优化：

注意到题面“输入格式”里有一句话：

第二行包含 A\times B\times C 个整数，其中第 ((i-1)\times B+(j-1))\times C+(k-1)+1 个数为 d(i,j,k)。

我们就可以用这句话把数组压缩成一维的，原来 d(x,y,z) 现在就是 d_{((x-1)\times B+(j-1))\times C+(k-1)+1}。

但这样子时间复杂度没变，还是会爆。

再优化：

我们可以参考 P1083 一题，用二分答案和在检查函数内用差分的方式。

借教室是一维差分，而这个是三维差分，只用把三维差分的数组按照上述防式转化成一维就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e7+5;
int a,b,c,m,d[N],cf[N];
int la[N],lb[N],lc[N],ra[N],rb[N],rc[N],h[N];

int QwQ(int x,int y,int z){
    return ((x-1)*b+(y-1))*c+z;
}

bool check(int x){
    memset(cf,0,sizeof(cf));
    for(int i=1;i<=x;i++){
        cf[QwQ(la[i],lb[i],lc[i])]+=h[i];
        cf[QwQ(ra[i]+1,lb[i],lc[i])]-=h[i];
        cf[QwQ(la[i],rb[i]+1,lc[i])]-=h[i];
        cf[QwQ(la[i],lb[i],rc[i]+1)]-=h[i];
        cf[QwQ(la[i],rb[i]+1,rc[i]+1)]+=h[i];
        cf[QwQ(ra[i]+1,lb[i],rc[i]+1)]+=h[i];
        cf[QwQ(ra[i]+1,rb[i]+1,lc[i])]+=h[i];
        cf[QwQ(ra[i]+1,rb[i]+1,rc[i]+1)]-=h[i];
    }
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            for(int k=1;k<=c;k++){
                cf[QwQ(i,j,k)]+=cf[QwQ(i-1,j,k)]+cf[QwQ(i,j-1,k)]+cf[QwQ(i,j,k-1)]-cf[QwQ(i-1,j-1,k)]-cf[QwQ(i-1,j,k-1)]-cf[QwQ(i,j-1,k-1)]+cf[QwQ(i-1,j-1,k-1)];
                if(cf[QwQ(i,j,k)]>d[QwQ(i,j,k)]) return true;
            }
        }
    }
    return false;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    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[QwQ(i,j,k)];
            }
        }
    }
    for(int i=1;i<=m;i++){
        cin>>la[i]>>ra[i]>>lb[i]>>rb[i]>>lc[i]>>rc[i]>>h[i];
    }
    int l=0,r=m+1;
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}

upd：修改了代码。