HDOJ 3682 To Be an Dream Architect

HDOJ 3682

一个相当于暴力的好题：有点容斥原理的意思

题意：n*n*n的一个正方体，每次可以拿掉一个1*1*n的柱子，问拿掉m个这样的柱子后，总共取掉了多少个小方块

想法：首先是对输入的柱子所在平面进行记录

注意的是，这个题需要判重，即有可能输入的是已经拿走的柱子

我们先处理xz平面和yz平面上的小方块，并且对xy平面的柱子进行记录

在相同的z平面的高度上，每插入一个xz的柱子，如果有相同高度的yz柱子存在，那么说明有一个重复的

所以呢，我们需要记录在xz平面上，x=x0，z=z0这个柱子是否拿掉过

而且，需要记录在z=z0这个平面上，有多少条x的柱子存在

那么在z=z0这个平面上，有y=y0的柱子出现的时候，那么答案是需要用容斥来减掉的

当xz和yz平面处理好了之后，我们来处理xy方向的柱子

可以想象成一个一个竖直的柱子往正方体从上往下插入

那么，可以枚举每一个z的高度

如果在xz平面上和yz平面上，这个xyz小方块没有被拿走的话，需要拿走

再次提醒，注意判重

另外，一个针对这个题的小技巧在这里说下：读入数据是怎么读

因为固定的字母是XYZ和=和，

那么我们不需要去用麻烦的字符串处理

用getchar（）绕过这些没有意义的字符

然后用读取整数的方法得到两个数值

代码如下：

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

const int maxn=1050;
int t,n,m;
int yz[maxn][maxn],xz[maxn][maxn];
int ans,tot;

struct node{
	int x,y;
}a[maxn];

int cmp(node m,node n){
	if (m.x==n.x) return m.y<n.y;
	return m.x<n.x;
}

int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		tot=ans=0;
		memset(yz,0,sizeof(yz));
		memset(xz,0,sizeof(xz));
		memset(a,0,sizeof(a));
		scanf("%d%d",&n,&m);
		while(m--){
			int x=0,y=0,z=0;
			char ch;
			getchar();
			scanf("%c",&ch);
			getchar();
			if (ch=='X') scanf("%d",&x);
			else if (ch=='Y') scanf("%d",&y);
			else if (ch=='Z') scanf("%d",&z);
			getchar();
			scanf("%c",&ch);
			getchar();
			if (ch=='X') scanf("%d",&x);
			else if (ch=='Y') scanf("%d",&y);
			else if (ch=='Z') scanf("%d",&z);
			//printf("%d%d %d\n",x,y,z);
			if (x==0&&yz[y][z]==0){
				yz[y][z]=1;
				yz[0][z]++;
				ans+=n-xz[0][z];
			}
			else if (y==0&&xz[x][z]==0){
				xz[x][z]=1;
				xz[0][z]++;
				ans+=n-yz[0][z];
			}
			else if (z==0){
				tot++;
				a[tot].x=x;
				a[tot].y=y;
			}
		}
		sort(a+1,a+tot+1,cmp);
		for(int i=1;i<=tot;i++)
			if (i>1&&a[i].x==a[i-1].x&&a[i].y==a[i-1].y) continue;
			else{
				for(int z=1;z<=n;z++)
					if (!xz[a[i].x][z]&&!yz[a[i].y][z]) ans++;
			}
		printf("%d\n",ans);
	}
	return 0;
}