C++: # "QFOI R1" 抱抱 - 题解与代码 - 常规

C++: # 'QFOI R1' 抱抱 - 题解与代码

题目描述

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

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

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

切出 $x \le k$ 的部分分给大家。
切出 $y \le k$ 的部分分给大家。
切出 $z \le 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 \le 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 \le 1$ 的部分切掉，剩余的单位正方体有 $(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3)$ 共 $6$ 个。

样例 $2$ 解释

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

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

数据范围

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

对于全部数据，保证 $1 \le a, b, c \le 10^6$，$1 \le m \le 2 \times 10^5$，$op \in {1, 2, 3}$，若 $op = 1$ 则 $1 \le k \le a$，若 $op = 2$ 则 $1 \le k \le b$，若 $op = 3$ 则 $1 \le k \le c$。

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

题解

我们可以用三个变量分别记录三个方向上被切除的坐标的最大值。每次操作后，我们只需根据操作类型更新对应的变量，并计算剩余体积即可。

代码

#include <iostream>
using namespace std;

int main() {
    int a, b, c, m, op, k;
    cin >> a >> b >> c >> m;
    int x = 0, y = 0, z = 0;
    for (int i = 0; i < m; i++) {
        cin >> op >> k;
        if (op == 1) {
            x = max(x, k);
        } else if (op == 2) {
            y = max(y, k);
        } else {
            z = max(z, k);
        }
        cout << (a - x) * (b - y) * (c - z) << endl;
    }
    return 0;
}

Test Input Reasoning:

本题只有一次切蛋糕操作，可以用来测试最简单的情况。