题解：P5567 [SDOI2008] 立方体覆盖

I_AM_CIMOTA · 2024-07-08 11:21:18 · 题解

简单扫描线，甚至可以直接暴力！

大体思路与 P8648 [蓝桥杯 2017 省 A] 油漆面积 一模一样，只不过是把扫描线放到三维空间上面来做。

如何把扫描线放到三维上？还是按坐标排序，之后我们会用一个“面”去依次扫描每个点。这个面是平行于立方体的面来扫的，所以它与立方体并的相交面积只会在某个立方体端点的位置才会发生改变。

发现值域非常小，所以我们可以直接用一个二维数组来表示“扫描面”的状态，如果从一个点扫到另外一个点的时候面积发生了改变，直接暴力修改即可。

代码非常短，跑得还飞快（最优解第一页）：

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

const int N=2005;
struct Diff{
    int x,y,a,b,h,tg;
}diff[N];
int n,tot,ans,nowS,s[N][N];

bool cmp(Diff x,Diff y){return x.h<y.h;}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x,y,z,r;
        scanf("%d%d%d%d",&x,&y,&z,&r);
        x+=1000,y+=1000,z+=1000; 
        diff[++tot]={x-r+1,y-r+1,x+r,y+r,z-r,1},diff[++tot]={x-r+1,y-r+1,x+r,y+r,z+r,-1};
    }
    sort(diff+1,diff+tot+1,cmp);
    for(int i=1;i<tot;i++){
        for(int j=diff[i].x;j<=diff[i].a;j++){
            for(int k=diff[i].y;k<=diff[i].b;k++){
                s[j][k]+=diff[i].tg;
                if(s[j][k]==1&&diff[i].tg==1)nowS++;
                if(s[j][k]==0&&diff[i].tg==-1)nowS--;
            }
        }
        ans+=nowS*(diff[i+1].h-diff[i].h);
    }
    printf("%d",ans);
    return 0;
}