P11450 [USACO24DEC] Farmer John’s Cheese Block B

题目描述

Farmer John 有一块立方体形状的奶酪，它位于三维坐标空间中，从 $(0,0,0)$ 延伸至 $(N,N,N)$（$2\le N\le 1000$）。Farmer John 将对他的奶酪块执行一系列 $Q$（$1\le Q\le 2\cdot 10^5$）次更新操作。

对于每次更新操作，FJ 将从整数坐标 $(x,y,z)$ 到 $(x+1,y+1,z+1)$ 处切割出一个 $1\times 1\times 1$ 的奶酪块，其中 $0\le x,y,z<N$。输入保证在 FJ 切割的位置上存在一个 $1\times 1\times 1$ 的奶酪块。由于 FJ 正在玩牛的世界，当下方的奶酪被切割后，重力不会导致上方的奶酪掉落。

在每次更新后，输出 FJ 可以将一个 $1\times 1\times N$ 的砖块插入奶酪块中的方案数，使得砖块的任何部分都不与剩余的奶酪重叠。砖块的每个顶点在全部三个坐标轴上均必须具有整数坐标，范围为 $[0,N]$。FJ 可以随意旋转砖块。

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0

输出 #1

0
0
1
2
5

说明/提示

样例解释

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

测试点性质

• 测试点 1：样例。
• 测试点 2-4：$N\le 10$ 且 $Q\le 1000$。
• 测试点 5-7：$N\le 100$ 且 $Q\le 1000$。
• 测试点 8-16：没有额外限制。

C++实现

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int Q = 2e5 + 5;
int n, q, x, y, z;
map<PII, int> mapab;
map<PII, int> mapac;
map<PII, int> mapbc;

int main() {
scanf(“%d %d”, &n, &q);
int ans = 0;
for (int i = 1; i <= q; i ++) {
scanf(“%d %d %d”, &x, &y, &z);
mapab[{x, y}] ++;
mapac[{x, z}] ++;
mapbc[{y, z}] ++;
if (mapab[{x, y}] == n) ans ++;
if (mapac[{x, z}] == n) ans ++;
if (mapbc[{y, z}] == n) ans ++;
printf(“%d\n”, ans);
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容