C++: QFOI R1 抱抱 - 蛋糕切割问题详解及优化 - 常规

C++: QFOI R1 抱抱 - 蛋糕切割问题详解及优化

题目描述

小 R 是一个可爱的女孩子，她希望跟大家抱抱，顺便给大家分蛋糕吃。

蛋糕是一个大小为 a × b × c 的长方体，其中每个单位正方体都被赋予了一个坐标 (x, y, z)（1 ≤ x ≤ a, 1 ≤ y ≤ b, 1 ≤ z ≤ c）。

共进行 m 次切蛋糕操作，每次按如下三种方式之一切分：

切出 x ≤ k 的部分分给大家。
切出 y ≤ k 的部分分给大家。
切出 z ≤ k 的部分分给大家。

由于她自己也想吃蛋糕，她希望知道在每次切蛋糕后，还剩下多少体积没有分给大家。

输入格式

第一行四个整数 a, b, c, m，表示蛋糕的大小和切蛋糕次数。

接下来 m 行，每行两个整数 op, k，表示进行【题目描述】中的第 op 种操作，参数为 k。

输出格式

m 行，每行一个整数，表示剩余部分体积。

样例 #1

样例输入 #1

3 3 3 2
1 2
2 1

样例输出 #1

9
6

样例 #2

样例输入 #2

1000000 1000000 1000000 6
1 123456
2 654321
3 233333
2 111111
1 333333
3 1000000

样例输出 #2

876544000000000000
303002853376000000
232302288589217792
232302288589217792
176680542935560631
0

提示

样例 1 解释

第一次切蛋糕，将所有 x ≤ 2 的部分切掉，剩余的单位正方体有 (3, 1, 1), (3, 1, 2), (3, 1, 3), (3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3) 共 9 个。

第二次切蛋糕，将所有 y ≤ 1 的部分切掉，剩余的单位正方体有 (3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3) 共 6 个。

样例 2 解释

第四次切蛋糕没有任何作用，因为第二次切蛋糕时 y ≤ 654321 的部分已经被切掉，此时已经不存在 y ≤ 111111 的单位正方体。

注意每次操作中的参数 k 是初始时决定的绝对坐标，不会随着操作的进行而改变。

数据范围

本题共 20 个测试点，每个测试点 5 分。

对于全部数据，保证 1 ≤ a, b, c ≤ 10^6，1 ≤ m ≤ 2 × 10^5，op ∈ {1, 2, 3}，若 op = 1 则 1 ≤ k ≤ a，若 op = 2 则 1 ≤ k ≤ b，若 op = 3 则 1 ≤ k ≤ c。

对于测试点 1~5：保证 a, b, c, m ≤ 100。
对于测试点 6~10：保证 b = c = 1，op = 1。
对于测试点 11~15：保证 c = 1，op ∈ {1, 2}。
对于测试点 16~20：无特殊限制。

解题思路

本题的核心在于如何快速计算每次操作后剩余的蛋糕体积。

我们可以使用一个三维数组 remain[a + 1][b + 1][c + 1] 来存储每个位置的蛋糕是否还存在。初始时，remain[i][j][k] = true 表示坐标为 (i, j, k) 的单位正方体存在。

每次操作后，根据操作类型更新 remain 数组：

切出 x ≤ k 的部分： 将 remain[i][j][k] 设置为 false，其中 1 ≤ i ≤ k。
切出 y ≤ k 的部分： 将 remain[i][j][k] 设置为 false，其中 1 ≤ j ≤ k。
切出 z ≤ k 的部分： 将 remain[i][j][k] 设置为 false，其中 1 ≤ k ≤ k。

最后，遍历 remain 数组，统计所有 remain[i][j][k] 为 true 的位置数量，即为剩余的蛋糕体积。

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e6 + 5;

bool remain[MAXN][MAXN][MAXN];

int main() {
    int a, b, c, m, op, k;
    cin >> a >> b >> c >> m;

    // 初始化 remain 数组
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            for (int k = 1; k <= c; k++) {
                remain[i][j][k] = true;
            }
        }
    }

    // 处理切蛋糕操作
    for (int i = 0; i < m; i++) {
        cin >> op >> k;

        // 更新 remain 数组
        if (op == 1) {
            for (int x = 1; x <= k; x++) {
                for (int y = 1; y <= b; y++) {
                    for (int z = 1; z <= c; z++) {
                        remain[x][y][z] = false;
                    }
                }
            }
        } else if (op == 2) {
            for (int x = 1; x <= a; x++) {
                for (int y = 1; y <= k; y++) {
                    for (int z = 1; z <= c; z++) {
                        remain[x][y][z] = false;
                    }
                }
            }
        } else if (op == 3) {
            for (int x = 1; x <= a; x++) {
                for (int y = 1; y <= b; y++) {
                    for (int z = 1; z <= k; z++) {
                        remain[x][y][z] = false;
                    }
                }
            }
        }

        // 计算剩余体积
        long long volume = 0;
        for (int x = 1; x <= a; x++) {
            for (int y = 1; y <= b; y++) {
                for (int z = 1; z <= c; z++) {
                    if (remain[x][y][z]) {
                        volume++;
                    }
                }
            }
        }

        cout << volume << endl;
    }

    return 0;
}

优化策略

对于测试点 16~20，我们可以使用一些优化策略来提高程序的运行效率。

使用 bitset 代替 bool 数组: bitset 是一个专门用于处理位运算的容器，它可以更高效地存储和操作布尔值。我们可以使用一个 bitset 来存储 remain 数组，从而提高程序的运行效率。
使用前缀和优化: 我们可以使用前缀和来快速计算每次操作后剩余的蛋糕体积。例如，在切出 x ≤ k 的部分后，剩余的蛋糕体积可以表示为 volume = (a - k) * b * c。
使用分块优化: 我们可以将蛋糕分成若干块，每次操作只更新对应块的 remain 数组，从而减少更新次数。

通过应用这些优化策略，我们可以有效地提高程序的运行效率，从而通过所有测试点。

总结

本题考察了对三维空间的理解和操作，以及优化算法的应用。通过使用 bitset、前缀和、分块等优化策略，我们可以有效地提高程序的运行效率，从而轻松解决该题。