我是靠谱客的博主 靓丽豌豆,这篇文章主要介绍HDU3584 Cube(三维树状区间更新+位运算),现在分享给大家,希望可以做个参考。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Cube Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 1983 Accepted Submission(s): 1033 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 Author alpc32 Source 2010 ACM-ICPC Multi-University Training Contest(15)——Host by NUDT
复制代码
1
2
3
4
5
6
简单题,三维数组,我们就在二维的基础上再加一位就好了。 这里我们求的是: 1.把空间上以(x1,y1,z1),(x2,y2,z2)为端点的区域所有的1变成00变成1. 2.求出(1,1,1)->(x,y,z)的区域的值. 这里用到异或,初始化立方体所在区域的值都为0,所以我们的异或值就要设置成为1,以后也是1. 然后就随便搞搞就行了,主要是区间的更新,安利一片好文章。

传送门

复制代码
1
里面介绍的是2维的,三维的其实也同理,最后求得的值%2,由于这里是值为0,1,所以加不加都无所谓.
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cctype> #include<cmath> #include<ctime> #include<string> #include<stack> #include<deque> #include<queue> #include<list> #include<set> #include<map> #include<cstdio> #include<limits.h> #define MOD 1000000007 #define fir first #define sec second #define fin freopen("/home/ostreambaba/文档/input.txt", "r", stdin) #define fout freopen("/home/ostreambaba/文档/output.txt", "w", stdout) #define mes(x, m) memset(x, m, sizeof(x)) #define Pii pair<int, int> #define Pll pair<ll, ll> #define INF 1e9+7 #define Pi 4.0*atan(1.0) #define lowbit(x) (x&(-x)) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; typedef unsigned long long ull; const double eps = 1e-12; const int maxn = 3001; using namespace std; inline int read(){ int x(0),op(1); char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')op=-1,ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*op; } int N,Q; int mat[101][101][101]; void update(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)){ mat[i][j][k]^=val; } } } } int query(int x,int y,int z) { int res=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)){ res^=mat[i][j][k]; } } } return res; } int main() { // fin; int x1,y1,z1,x2,y2,z2,c; while(~scanf("%d%d",&N,&Q)){ mes(mat,0); while(Q--){ scanf("%d%d%d%d",&c,&x1,&y1,&z1); if(c==1){ scanf("%d%d%d",&x2,&y2,&z2); ++x2,++y2,++z2; update(x1,y1,z1,1); update(x1,y2,z2,1); update(x1,y1,z2,1); update(x1,y2,z1,1); update(x2,y2,z1,1); update(x2,y1,z2,1); update(x2,y2,z2,1); update(x2,y1,z1,1); } else{ printf("%dn",query(x1,y1,z1)%2); } } } return 0; }

最后

以上就是靓丽豌豆最近收集整理的关于HDU3584 Cube(三维树状区间更新+位运算)的全部内容,更多相关HDU3584内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(84)

评论列表共有 0 条评论

立即
投稿
返回
顶部