Farmer John's Cheese Block

题意

有一个 $N\times N\times N$ 的奶酪立方体。每次会切掉一个坐标为 (x,y,z) 的 $1\times 1\times 1$ 小方块。

每次切割后，问有多少种方式可以放入一个 $1\times 1\times N$ 的长砖块，使它不与剩余奶酪重叠。

砖块可以沿 x、y、z 三个方向摆放。

思路

先看一个直接重算的朴素写法：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:31
 * update_at: 2026-07-11 15:34
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, q;
bool removed_block[MAXN][MAXN][MAXN]; // true 表示这个 1x1x1 小块已经被切掉。

bool empty_x_line(int y, int z) {
    for (int x = 0; x < n; x++) {
        if (!removed_block[x][y][z]) return false;
    }
    return true;
}

bool empty_y_line(int x, int z) {
    for (int y = 0; y < n; y++) {
        if (!removed_block[x][y][z]) return false;
    }
    return true;
}

bool empty_z_line(int x, int y) {
    for (int z = 0; z < n; z++) {
        if (!removed_block[x][y][z]) return false;
    }
    return true;
}

long long calc_answer() {
    long long ans = 0;

    for (int y = 0; y < n; y++) {
        for (int z = 0; z < n; z++) {
            if (empty_x_line(y, z)) ans++;
        }
    }

    for (int x = 0; x < n; x++) {
        for (int z = 0; z < n; z++) {
            if (empty_y_line(x, z)) ans++;
        }
    }

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
            if (empty_z_line(x, y)) ans++;
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;

    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;

        removed_block[x][y][z] = true;
        cout << calc_answer() << '\n';
    }

    return 0;
}

这个暴力每次切割后，检查三种方向的所有直线是否已经完全切空。它直观但太慢。

一个 $1\times 1\times N$ 的砖块一定对应一条长度为 $N$ 的整线：

固定 y,z，沿 x 方向。
固定 x,z，沿 y 方向。
固定 x,y，沿 z 方向。

切掉一个小方块 (x,y,z)，只会影响穿过它的三条线：

text

1
2
3固定 y,z 的 x 方向线
固定 x,z 的 y 方向线
固定 x,y 的 z 方向线

所以我们维护每条线还剩多少奶酪块。

初始每条线都剩 N 块。每次切掉 (x,y,z)：

left_yz[y][z]--
left_xz[x][z]--
left_xy[x][y]--

如果某个值第一次变成 0，就说明这条线已经被完全切空，可以新增一种放砖块方案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:31
 * update_at: 2026-07-11 15:34
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, q;
int left_xy[MAXN][MAXN]; // 固定 x,y，沿 z 方向还剩多少块。
int left_xz[MAXN][MAXN]; // 固定 x,z，沿 y 方向还剩多少块。
int left_yz[MAXN][MAXN]; // 固定 y,z，沿 x 方向还剩多少块。
long long ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            left_xy[i][j] = n;
            left_xz[i][j] = n;
            left_yz[i][j] = n;
        }
    }

    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;

        left_xy[x][y]--;
        if (left_xy[x][y] == 0) ans++;

        left_xz[x][z]--;
        if (left_xz[x][z] == 0) ans++;

        left_yz[y][z]--;
        if (left_yz[y][z] == 0) ans++;

        cout << ans << '\n';
    }

    return 0;
}

复杂度

初始化三个二维数组需要 $O(N^2)$ 。

每次更新只修改三条线，所以总时间复杂度为 $O(N^2+Q)$ 。

空间复杂度为 $O(N^2)$ 。

总结

本题的关键是把三维问题降成“固定两维的一条线”。

一次切割只影响三条线，增量维护剩余数量即可。

Farmer John's Cheese Block

目录

题意

思路

代码

复杂度

总结