USACO 24Dec Bronze B 题解

题意

给定一个三维的正方体奶酪，坐标从 $(0,0,0)$ 延伸到 $(N, N, N)$。有 $Q$ 次询问，每次询问给定三个数 $(x, y, z)$，表示切去由坐标点 $(x,y,z)$ 到坐标点 $(x+1,y+1,z+1)$ 的一个 $1\times 1\times 1$ 立方体奶酪。然后询问，在这个残缺的奶酪中，可以有多少种方式，可以插入一个 $1\times 1\times N$ 的木棒。保证对于 $1\leq i\leq Q$，$(x_i, y_i, z_i)$ 互不相同。

分析

可以对题意进行转化。空间中共有 $N\times N\times N$ 个正方体，为了方便，把他们表示为 $\{0,0,0\}$ 到 $\{N-1,N-1,N-1\}$。一个木棒相当与占据了 $n$ 个小正方体，且这 $n$ 个正方体在某一方向是连续的。在坐标上，这种规律呈现为 $x,y,z$ 三种坐标中有两种相同，另外一种构成一个 $1\sim n$ 的排列。比如当 $N=3$ 时，$\{1, 1, 0\},\{1, 1, 1\},\{1, 1, 2\}$ 这三个位置。

暴力

很显然当 $N\leq 100$ 时，可以开数组标记是否已经被挖掉。判断那些位置可以插入木棒时，$O(N^2)$ 枚举 $(x,y)$，$(x,z)$ 和 $(y,z)$，然后 $O(N)$ 判断是否可以插入。复杂度 $O(N^3Q)$。

对暴力进行优化

因为是在不停的扣奶酪，所以不难发现答案是单调不减的。

发现对于每一组相同的 $(x,y)$ 或 $(x,z)$ 或 $(y,z)$ 坐标，当且仅当这一条被覆盖了 $N$ 次后，才会对答案产生 $+1$ 的贡献。开三个 map 记录一下，每次更新的时候判断一下是否满足条件即可。

#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;
}
// 是的，AC 代码比暴力要短

那这个题就做完了，撒花。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int ax[N][N], ay[N][N], az[N][N], sx, sy, sz;
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n, q;cin>>n>>q;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) ax[i][j]=ay[i][j]=az[i][j]=n;
	while(q--)
	{
		int x, y, z;cin>>x>>y>>z;x++;y++;z++;
		ax[y][z]--;ay[x][z]--;az[x][y]--;
		if(ax[y][z]==0)sx++;
		if(ay[x][z]==0)sy++;
		if(az[x][y]==0)sz++;
		cout<<sx+sy+sz<<"\n";
		
	}
    return 0;
}