首页 > ACM题库 > HDU-杭电 > HDU 3584-Cube[解题报告]HOJ
2014
11-27

HDU 3584-Cube[解题报告]HOJ

Cube

问题描述 :

Given an N*N*N cube A, whose elements are either 0 or 1. A[i, j, k] means the number in the i-th row , j-th column and k-th layer. Initially we have A[i, j, k] = 0 (1 <= i, j, k <= N).
We define two operations, 1: “Not” operation that we change the A[i, j, k]=!A[i, j, k]. that means we change A[i, j, k] from 0->1,or 1->0. (x1<=i<=x2,y1<=j<=y2,z1<=k<=z2).
0: “Query” operation we want to get the value of A[i, j, k].

输入:

Multi-cases.
First line contains N and M, M lines follow indicating the operation below.
Each operation contains an X, the type of operation. 1: “Not” operation and 0: “Query” operation.
If X is 1, following x1, y1, z1, x2, y2, z2.
If X is 0, following x, y, z.

输出:

Multi-cases.
First line contains N and M, M lines follow indicating the operation below.
Each operation contains an X, the type of operation. 1: “Not” operation and 0: “Query” operation.
If X is 1, following x1, y1, z1, x2, y2, z2.
If X is 0, following x, y, z.

样例输入:

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

样例输出:

1
0
1

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define maxn 101
#define lowbit(x) ((x)&(-x))
int c[maxn][maxn][maxn];
int n,m;

void update(int x,int y,int z) {
 for(int i=x;i<=n;i+=lowbit(i))
 for(int j=y;j<=n;j+=lowbit(j))
 for(int k=z;k<=n;k+=lowbit(k))
 c[i][j][k]^=1;
}

int sum(int x,int y,int z) {
 int res=0;
 for(int i=x;i;i-=lowbit(i))
 for(int j=y;j;j-=lowbit(j))
 for(int k=z;k;k-=lowbit(k))
 res^=c[i][j][k];
 return res;
}

int main() {
 while(~scanf("%d%d",&n,&m)) {
 int com;
 memset(c,0,sizeof(c));
 while(m--) {
 scanf("%d",&com);
 if(com) {
 int x,y,z,x1,y1,z1;
 scanf("%d%d%d%d%d%d",&x,&y,&z,&x1,&y1,&z1);
 update(x,y,z);
 update(x,y,z1+1);
 update(x,y1+1,z);
 update(x1+1,y,z);
 update(x1+1,y1+1,z);
 update(x1+1,y,z1+1);
 update(x,y1+1,z1+1);
 update(x1+1,y1+1,z1+1);
 }
 else {
 int x,y,z;
 scanf("%d%d%d",&x,&y,&z);
 printf("%d\n",sum(x,y,z));
 }
 }
 }
 return 0;
}

  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。