题解 P5229 【[AHOI2013]立方体】

2017gdgzoi999 · 2019-02-27 13:56:43 · 题解

这下明白了原因了。究竟怎么判断一个面是不是外表面呢？如果你做过这一题，肯定会想到搜索。从\{0,0,0\}开始搜索，每一个x,y,z都保证在区间[0, n+1]之间，被染色的方格设为障碍，每到一个地方打标记。

那么枚举每一个被染色的方格时，旁边六联通有多少个没被染色但是被标记了的方格，计数器就加多少。于是就有了这个方法：

错误做法2:对于每个立方体，直接暴力染色。然后按照以上规则进行DFS。最后枚举所有的相邻的两个块组合，如果其中正好一个染了色，另外一个一个没有染色并且被标记，计数器+1。

错误原因：自己想一下可知DFS递归层数最多可以达到maxn^3层，会导致RE、MLE。\color{orange}36pts

（太长了于是分两行写）

为节省代码长度，离散化可以封装。

正确做法3：在正确做法2的基础上，增加离散化并修改计算外表面积方法。

核心代码：

第一个代码：离散化(已封装)

int doit(int a[], int b[], int d[]) { // 将a数组和b数组离散，delta存到d
    int *r = new (int[(MAXN<<1)+3]); // 排序用数组
    int *m = new (int[(MAXN<<1)+3]); // 映射数组
    for (int i=1; i<=n; ++i) {
        r[i] = a[i]; r[n+i] = b[i]; // 初始化排序数组
    }
    sort(r+1, r+(n<<1)+1); r[0] = -1;
    int id = 0;
    for (int i=1; i<=n<<1; ++i) { // 排序后离散化
        if (r[i-1]!=r[i]) d[++id] = r[i]-r[i-1];
        m[r[i]] = id;
    }
    for (int i=1; i<=n; ++i) {
        a[i] = m[a[i]]; b[i] = m[b[i]];
    }
    return id+1;
}

第二个代码：计算外表面积

    int res = 0; // 计算外表面积
    for (int i=1; i<=xx; ++i) {
        for (int j=1; j<=yy; ++j) {
            for (int k=1; k<=zz; ++k) {
                if (a[i][j][k]==1) {
                    for (int t=0; t<6; ++t) {
                        if (2==a[i+gx[t]][j+gy[t]][k+gz[t]]) { // 找到一对组合
                            int tmp = 1; // tmp表示这一对增加的外表面积
                            if (!gx[t]) tmp *= dx[i];
                            if (!gy[t]) tmp *= dy[j];
                            if (!gz[t]) tmp *= dz[k];
                            res += tmp; // 更新结果
                        }
                    }
                }
            }
        }
    }

提交结果：267ms，第11个数据点仅用了3ms。

完整的代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

#define c(x, xx) ((~x) && (x<=xx))
using namespace std;
const int MAXN = 210;

struct data {
    int x, y, z;
};
int a[MAXN][MAXN][MAXN], xx, yy, zz, n;
int x[MAXN], y[MAXN], z[MAXN], x2[MAXN], y2[MAXN], z2[MAXN];
int dx[MAXN], dy[MAXN], dz[MAXN];
int gx[6] = {1, -1, 0, 0, 0, 0};
int gy[6] = {0, 0, 1, -1, 0, 0};
int gz[6] = {0, 0, 0, 0, 1, -1};

int doit(int a[], int b[], int d[]) {
    int *r = new (int[(MAXN<<1)+3]);
    int *m = new (int[(MAXN<<1)+3]);
    for (int i=1; i<=n; ++i) {
        r[i] = a[i]; r[n+i] = b[i];
    }
    sort(r+1, r+(n<<1)+1); r[0] = -1;
    int id = 0;
    for (int i=1; i<=n<<1; ++i) {
        if (r[i-1]!=r[i]) d[++id] = r[i]-r[i-1];
        m[r[i]] = id;
    }
    for (int i=1; i<=n; ++i) {
        a[i] = m[a[i]]; b[i] = m[b[i]];
    }
    return id+1;
}
void bfs() {
    queue<data> q;
    q.push((data) {0, 0, 0}); a[0][0][0] = 2;
    while (!q.empty()) {
        data u = q.front(); q.pop();
        int x, y, z;
        for (int i=0; i<6; ++i) {
            x = u.x+gx[i]; y = u.y+gy[i]; z = u.z+gz[i];
            if (c(x, xx) && c(y, yy) && c(z, zz)) {
                if (!a[x][y][z]) {
                    a[x][y][z] = 2; q.push((data) {x, y, z});
                }
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) {
        scanf("%d%d%d%d%d%d", &x[i], &y[i], &z[i], &x2[i], &y2[i], &z2[i]);
    }
    xx = doit(x, x2, dx);
    yy = doit(y, y2, dy);
    zz = doit(z, z2, dz);
    for (int i=1; i<=n; ++i) {
        int x = ::x[i],
        y = ::y[i],
        z = ::z[i],
        x2 = ::x2[i],
        y2 = ::y2[i],
        z2 = ::z2[i];
        bool flag = false;
        for (int j=1; j<i; ++j) {
            if (((::x[j]<=x) && (::x2[j]>=x2)) && ((::y[j]<=y) && (::y2[j]>=y2)) && ((::z[j]<=z) && (::z2[j]>=z2))) {
                flag = true; break;
            }
        }
        if (flag) continue;
        for (int j=x+1; j<=x2; ++j) {
            for (int k=y+1; k<=y2; ++k) {
                for (int l=z+1; l<=z2; ++l) a[j][k][l] = true;
            }
        }
    }
    bfs();
    int res = 0;
    for (int i=1; i<=xx; ++i) {
        for (int j=1; j<=yy; ++j) {
            for (int k=1; k<=zz; ++k) {
                if (a[i][j][k]==1) {
                    for (int t=0; t<6; ++t) {
                        if (2==a[i+gx[t]][j+gy[t]][k+gz[t]]) {
                            int tmp = 1;
                            if (!gx[t]) tmp *= dx[i];
                            if (!gy[t]) tmp *= dy[j];
                            if (!gz[t]) tmp *= dz[k];
                            res += tmp;
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", res);
}

当然这些优化在数据相对随机的情况下是比较有用的，当然，一些奇奇怪怪的数据（例如每两个方块都互不包含、重合，且数据包含0-200之间的所有数字）要卡卡常。

建议的其它优化方案：

1. 开O2优化吸氧（STL很有用）；

2. 手写队列（比STL快很多，推荐）。

总结：

• 细心看好题目。

• 在注意时间限制的同时也要注意空间限制，必要时使用占用空间少的BFS。

• 估计自己的算法在不同数据特点下的效率。