Cube

72 阅读 0 评论 48 点赞

我是靠谱客的博主无情煎蛋，最近开发中收集的这篇文章主要介绍Cube，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Given an N*N*N cube A, whose elements are either 0 or 1. A i,j,k 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 i,j,k = 0 (1 <= i, j, k <= N).
We define two operations, 1: “Not” operation that we change the A i,j,k i,j,k=!A i,j,k i,j,k. that means we change A i,j,k 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 i,j,k.

Input

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.

Output

For each query output A x,y,z x,y,z in one line. (1<=n<=100 sum of m <=10000)

Sample Input

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

Sample Output

1
0

题解：三维的树状数组。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int Maxn=105;
int n,m;
int sum[Maxn][Maxn][Maxn];
int lowbit(int x){
    return x&(-x);
}
void updata(int x,int y,int z,int val){
    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))
               sum[i][j][k]+=val;
}
int getSum(int x,int y,int z){
    int ret=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            for(int k=z;k>0;k-=lowbit(k))
                ret+=sum[i][j][k];
    return ret;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(sum,0,sizeof(sum));
        int dir,x1,y1,z1,x2,y2,z2;
        while(m--){
            scanf("%d",&dir);
            if(dir){
                scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
                updata(x1,y1,z1,1);
                updata(x1,y2+1,z1,-1);
                updata(x2+1,y1,z1,-1);
                updata(x1,y1,z2+1,-1);
                updata(x2+1,y2+1,z1,1);
                updata(x2+1,y1,z2+1,1);
                updata(x1,y2+1,z2+1,1);
                updata(x2+1,y2+1,z2+1,-1);
            }
            else{
                scanf("%d%d%d",&x1,&y1,&z1);
                printf("%dn",getSum(x1,y1,z1)%2);
            }
        }
    }
}

这种方法好像更简单些。

#include<stdio.h>  
#include<string.h>  
struct node{  
    int x1,x2;  
    int y1,y2;  
    int z1,z2;  
}p[10010];  
  
int main(){  
    int n,m;  
    int x1,y1,z1;  
  
    while(scanf("%d%d",&n,&m)!=EOF){  
        int l=0;  
  
        while(m--){  
            int flag;  
            scanf("%d",&flag);  
            if(flag==1){  
                scanf("%d%d%d%d%d%d",&p[l].x1,&p[l].y1,&p[l].z1,&p[l].x2,&p[l].y2,&p[l].z2);  
                l++;  
            }  
            else if(flag==0){  
                scanf("%d%d%d",&x1,&y1,&z1);  
                int count=0;  
                for(int i=0;i<l;i++)  
                    if(p[i].x1<=x1&&x1<=p[i].x2&&p[i].y1<=y1&&y1<=p[i].y2&&p[i].z1<=z1&&z1<=p[i].z2)  
                                count+=1;  
                if(count%2==0)  
                    printf("0/n");  
                else  
                    printf("1/n");  
            }  
        }  
    }  
    return 0;  
}