【蓝桥杯集训·每日一题2025】 AcWing 6122. 农夫约翰的奶酪块 python

Week 1
2月17日

农夫约翰的奶酪块

农夫约翰有一块立方体形状的奶酪，它位于三维坐标空间中，从 $(0, 0, 0)$ 延伸至 $(N, N, N)$ 。

农夫约翰将对他的奶酪块执行一系列 $Q$ 次更新操作。

对于每次更新操作，农夫约翰将从整数坐标 $(x, y, z)$ 到 $(x + 1, y + 1, z + 1)$ 处切割出一个 $1 \times 1 \times 1$ 的奶酪块，其中 $0 \leq x, y, z < N$ 。

输入保证在农夫约翰切割的位置上存在一个 $1 \times 1 \times 1$ 的奶酪块。

由于农夫约翰正在玩牛的世界，当下方的奶酪被切割后，重力不会导致上方的奶酪掉落。

在每次更新后，输出农夫约翰可以将一个 $1 \times 1 \times N$ 的砖块插入奶酪块中的方案数，使得砖块的任何部分都不与剩余的奶酪重叠。

砖块的每个顶点在全部三个坐标轴上均必须具有整数坐标，范围为 $[0, N]$ 。

农夫约翰可以随意旋转砖块。

输入格式

输入的第一行包含 $N$ 和 $Q$ 。

以下 $Q$ 行包含 $x$ ， $y$ 和 $z$ ，为要切割的位置的坐标。

输出格式

在每次更新操作后，输出一个整数，为所求的方案数。

数据范围

$\le N \le 1000$ ,
$\le Q \le 2 \times 10^5$ ,
$\le x,y,z < N$

输入样例：

输出样例：

样例解释

在前三次更新操作后， $[0, 1] \times [0, 2] \times [0, 1]$ 范围的 $1 \times 2 \times 1$ 砖块与剩余的奶酪不重叠，因此它贡献了答案。

思路：

我们需要解决的问题是模拟在三维空间中对奶酪块进行一系列切割操作，并在每次切割后计算可以插入一个 (1 * 1 * N) 砖块的不同方案数

题目解析

输入格式：
- 第一行包含两个整数 N 和 Q，分别表示奶酪块的大小和更新操作的次数。
- 接下来的 Q 行每行包含三个整数 x, y, z，表示需要切割的坐标。
处理逻辑：
- 使用三个二维数组 a, b, c 分别记录在不同维度方向上的切割情况。
  - a[x][y]：记录在第 x 行、第 y 列方向上被切割的次数。
  - b[x][z]：记录在第 x 层、第 z 列方向上被切割的次数。
  - c[y][z]：记录在第 y 层、第 z 行方向上被切割的次数。
- 在每次切割后，检查是否可以在某个方向上插入一个完整的 1x1xN 砖块（即某个方向上已经被切割了 N 次）。
输出格式：
- 在每次更新操作后，输出当前可以插入砖块的方案数。

示例解释

对于给定的输入样例：

第一次切割 (0, 0, 0)：没有完整的一维方向被切割，所以方案数为 0。
第二次切割 (1, 1, 1)：依然没有完整的一维方向被切割，所以方案数仍为 0。
第三次切割 (0, 1, 0)：现在在 a[0][1] 方向上已经切割了一次，但还未达到 N=2，所以方案数仍为 0。
第四次切割 (1, 0, 0)：在 b[1][0] 方向上切割了一次，仍未达到 N=2，所以方案数增加到 1。
第五次切割 (1, 1, 0)：在 c[1][0] 方向上切割了一次，达到了 N=2，因此方案数增加到 5。

code:

n, q = map(int, input().split()) # 初始化三个二维数组a, b, c来记录每个维度上的切割情况
# a[x][y]表示在x行y列方向上被切割的次数
# b[x][z]表示在x层z列方向上被切割的次数
# c[y][z]表示在y层z行方向上被切割的次数
a = [[0] * n for _ in range(n)]
b = [[0] * n for _ in range(n)]
c = [[0] * n for _ in range(n)]ans = 0  for _ in range(q):x, y, z = map(int, input().split())  # 获取要切割的位置坐标(x, y, z)# 更新对应位置的切割次数a[x][y] += 1b[x][z] += 1c[y][z] += 1# 检查是否可以在某个方向上插入一个完整的1x1xN砖块if a[x][y] == n:  # 如果在x行y列方向上已经完全切割了N次ans += 1if b[x][z] == n:  # 如果在x层z列方向上已经完全切割了N次ans += 1if c[y][z] == n:  # 如果在y层z行方向上已经完全切割了N次ans += 1print(ans)