农夫约翰的奶酪块
文章目录
- 农夫约翰的奶酪块
- 一、题目
- 二、分析
- 三、题解
- 总结
一、题目
农夫约翰有一块立方体形状的奶酪，它位于三维坐标空间中，从 (0,0,0)
延伸至 (N,N,N)。
农夫约翰将对他的奶酪块执行一系列 Q
次更新操作。
对于每次更新操作，农夫约翰将从整数坐标 (x,y,z)
到 (x+1,y+1,z+1)
处切割出一个 1×1×1
的奶酪块，其中 0≤x,y,z<N。
输入保证在农夫约翰切割的位置上存在一个 1×1×1
的奶酪块。
由于农夫约翰正在玩牛的世界，当下方的奶酪被切割后，重力不会导致上方的奶酪掉落。
在每次更新后，输出农夫约翰可以将一个 1×1×N
的砖块插入奶酪块中的方案数，使得砖块的任何部分都不与剩余的奶酪重叠。
砖块的每个顶点在全部三个坐标轴上均必须具有整数坐标，范围为 [0,N]。农夫约翰可以随意旋转砖块。
输入格式
输入的第一行包含 N
和 Q。
以下 Q
行包含 x，y 和 z，为要切割的位置的坐标。
输出格式
在每次更新操作后，输出一个整数，为所求的方案数。
数据范围
2≤N≤1000,
1≤Q≤2×105,
0≤x,y,z<N
输入样例：
2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0
输出样例：
0
0
1
2
5
样例解释
在前三次更新操作后，[0,1]×[0,2]×[0,1]
范围的 1×2×1
砖块与剩余的奶酪不重叠，因此它贡献了答案。
二、分析
暴力枚举
本题是用二维模拟，所以我们创建三个二维数组来模拟三维空间的每一个面，第一个面是(x, y) 第二个面是(y, z) 第三
个面是(x, z)，因为本题要插入一个含有一条边是N的柱体不与原来的图形重叠，那我们可以推断出一定是横竖方向长度连续为N(可以>N)的小正方体被挖 去，也就是某个平面上连续的长度为N的面被挖去，转换到二维空间上的点上，只要此点被用过N次(一个面上)，就代表被挖去N个连续的正方体
三、题解
#include <iostream>const int N = 1010;int main()
{int a[N][N],b[N][N],c[N][N];int n,Q;scanf("%d%d",&n,&Q);int res = 0;while(Q--){int x,y,z;scanf("%d%d%d",&x,&y,&z);a[x][y]++;b[y][z]++;c[x][z]++;if(a[x][y] == n) res++;if(b[y][z] == n) res++;if(c[x][z] == n) res++;printf("%d\n",res);}return 0;}
总结
到这里这篇文章的内容就结束了，谢谢大家的观看，如果有好的建议可以留言喔，谢谢大家啦！