ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0

MiYu原创, 转帖请注明 : 转载自 ______________白白の屋    

 

题目描述:

Cube

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 495    Accepted Submission(s): 226


Problem Description
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].
 

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] 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 1
 

题目分析 :

      更新区间, 查询一个点, 三维线段树 直接无视.........数据不是很强, 所以 直接暴力就可以过, 过完发现自己的时间 在700MS 左右, 看了下rank,

小A 榜首..... 时间竟然才62MS....果然还是要用三维树状数组来加速啊 . 不过一直没理解 用 树状数组 解决这题的思路, 今早上终于明白了.

画个图先 :

             

好了 , 看代码:

树状数组代码 :

 /*

Mail to   : miyubai@gamil.com
My Blog   : www.baiyun.me
Link      : http://www.cnblogs.com/MiYu  || http://www.cppblog.com/MiYu
Author By : MiYu
Test      : 1
Complier  : g++ mingw32-3.4.2
Program   : HDU_3584
Doc Name  : Cube
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
inline bool scan_d(int &num)  //整数输入
{
        char in;bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}
const int MAXN = 105;
int mat[MAXN][MAXN][MAXN];
int low[MAXN];
int i, j, k;
void setLow () {
     for ( i = 1; i <= MAXN; ++ i ) low[i] = i & (- i);
}
void modify ( int x, int y, int z ) {
     for ( i = x; i <= MAXN; i += low[i] ) {
         for ( j = y; j <= MAXN; j += low[j] ) {
             for ( k = z; k <= MAXN; k += low[k] )
                 mat[i][j][k] ^= 1;   
         }    
     }    
}
int query ( int x, int y, int z ) {
     int sum = 0;
     for ( i = x; i > 0; i ^= low[i] ) {
         for ( j = y; j > 0; j ^= low[j] ) {
             for ( k = z; k > 0; k ^= low[k] )
                 sum += mat[i][j][k];    
         }    
     }    
     return sum & 1;
}
int main ()
{
    setLow ();
    int N, M;
    while ( scan_d ( N ) && scan_d ( M ) ) {
          memset ( mat, 0, sizeof ( mat ) );
          while ( M -- ) {
                int x1,y1,z1,x2,y2,z2;
                int s;  scan_d ( s ); 
                switch ( s ) {
                       case 1:
                            scan_d ( x1 ); scan_d ( y1 ); scan_d ( z1 ); 
                            scan_d ( x2 ); scan_d ( y2 ); scan_d ( z2 );
                            modify ( x1,y1,z1 );    modify ( x1,y1,z2+1 );
                            modify ( x2+1,y1,z1 );    modify ( x2+1,y1,z2+1 );
                            modify ( x1,y2+1,z1 );    modify ( x2+1,y2+1,z1 );
                            modify ( x2+1,y2+1,z2+1 );    modify ( x1,y2+1,z2+1 ); 
                            break;
                       case 0:
                            scan_d ( x1 ); scan_d ( y1 ); scan_d ( z1 );
                            printf ( "%d\n", query ( x1,y1,z1 ) );      
                }
          }           
    }
    return 0;
}

暴力代码 :

/*
Mail to   : miyubai@gamil.com
My Blog   : www.baiyun.me
Link      : http://www.cnblogs.com/MiYu  || http://www.cppblog.com/MiYu
Author By : MiYu
Test      : 1
Complier  : g++ mingw32-3.4.2
Program   :
Doc Name  :
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
struct node {  
    int x1, x2, y1, y2, z1, z2; 
}cube[10010];   
  
int main()  
{  
    int N, M;  
    int x, y, z;
    while ( scanf ( "%d%d",&N,&M ) != EOF )  {  
        int cnt = 0;  
        while ( M -- )  
        {  
            int ask;  
            scanf ( "%d", &ask );  
            switch ( ask ) {
                case 1:   
                    scanf ( "%d%d%d%d%d%d", &cube[cnt].x1,&cube[cnt].y1,
                                            &cube[cnt].z1,&cube[cnt].x2,
                                            &cube[cnt].y2,&cube[cnt].z2 );  
                    ++ cnt;  
                    break;
                case 0:
                    scanf ( "%d%d%d", &x, &y, &z);  
                    int count = 0;  
                    for ( int i = 0; i != cnt; ++ i )  
                        if ( cube[i].x1 <= x && x <= cube[i].x2 && 
                             cube[i].y1 <= y && y <= cube[i].y2 && 
                             cube[i].z1 <= z && z <= cube[i].z2 )  
                                    count ^= 1;;  
                    puts ( count ? "1" : "0" ); 
            }  
        }  
    }  
    return 0;  
}  

 

Feedback

# re: HDU 3584 HDOJ 3584 Cube ACM 3584 IN HDU  回复  更多评论   

2010-11-14 21:40 by 博客之家
好复杂的代码啊

# re: HDU 3584 HDOJ 3584 Cube ACM 3584 IN HDU  回复  更多评论   

2010-12-03 01:59 by flagman
说两点,
1)这三维树状数组,占空间比较大,特别是问题规模快速增长时;
2)对于
void setLow () {
for ( i = 1; i <= MAXN; ++ i ) low[i] = i & (- i);
}
这样的短函数,topcoder上很多人都喜欢用宏定义,不知道为啥,难道受C的影响太深了,抑或为了节约函数调用开销?呵呵,比如上面这函数,可能写成如下,
#define SETLOW(low,MAXN) for( i = 1; i <= (MAXN); ++i) *((low) + i) = i & (-i);

# re: HDU 3584 HDOJ 3584 Cube ACM 3584 IN HDU  回复  更多评论   

2011-04-07 19:51 by
你好,我是一个代码初学者,也是在HD里做题目的,看了你的解析,相当的蛋疼。。。完全是看不懂,汗,不过看得出你狠厉害啊!呵呵。。。。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理