HDU 3584 Cube(3 Dツリー配列)
25430 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3584
Cube
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
View Code
3 Dと2 Dの差が少ないような気がします ちょっと変わればいいのに
でも私はwaです 例によって、次のコードは無視してください.
View Code
Cube
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
1 /*AC */
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5
6 using namespace std;
7
8 const int N=110;
9
10 int n,m,arr[N][N][N];
11
12 int lowbit(int x)
13 {
14 return x&(-x);
15 }
16
17 void update(int i,int j,int k,int val)
18 {
19 while(i<=n)
20 {
21 int tmpj=j;
22 while(tmpj<=n)
23 {
24 int tmpk=k;
25 while(tmpk<=n)
26 {
27 arr[i][tmpj][tmpk]+=val;
28 tmpk+=lowbit(tmpk);
29 }
30 tmpj+=lowbit(tmpj);
31 }
32 i+=lowbit(i);
33 }
34 }
35
36 int Sum(int i,int j,int k)
37 {
38 int ans=0;
39 while(i>0)
40 {
41 int tmpj=j;
42 while(tmpj>0)
43 {
44 int tmpk=k;
45 while(tmpk>0)
46 {
47 ans+=arr[i][tmpj][tmpk];
48 tmpk-=lowbit(tmpk);
49 }
50 tmpj-=lowbit(tmpj);
51 }
52 i-=lowbit(i);
53 }
54 return ans;
55 }
56
57 int main()
58 {
59
60 //freopen("input.txt","r",stdin);
61
62 while(~scanf("%d%d",&n,&m))
63 {
64 memset(arr,0,sizeof(arr));
65 int x1,y1,z1,x2,y2,z2;
66 int op;
67 while(m--)
68 {
69 scanf("%d",&op);
70 if(op==1)
71 {
72 scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
73 update(x2+1, y2+1, z2+1, 1);
74 update(x1, y2+1, z2+1, 1);
75 update(x2+1, y1, z2+1, 1);
76 update(x2+1, y2+1, z1, 1);
77 update(x1, y1, z2+1, 1);
78 update(x2+1, y1, z1, 1);
79 update(x1, y2+1, z1, 1);
80 update(x1, y1, z1, 1);
81 }
82 else
83 {
84 scanf("%d%d%d",&x1,&y1,&z1);
85 printf("%d
",Sum(x1,y1,z1)&1);
86 // sum(x,y)
87 }
88 }
89 }
90 return 0;
91 }View Code
3 Dと2 Dの差が少ないような気がします ちょっと変わればいいのに
でも私はwaです 例によって、次のコードは無視してください.
1 /*wa */
2 #include<iostream>
3
4 using namespace std;
5
6 int N;
7 int c[105][105][105];
8
9 int lowbit( int x )
10 {
11 return x & (-x);
12 }
13
14 void update( int x, int y, int z, int delta )
15 {
16 int i, j , k;
17 for(i=x; i<=N; i+=lowbit(i))
18 {
19 for(j=y; j<=N; j+=lowbit(j))
20 {
21 for(k=z ; k<=N; k+=lowbit(j))
22 c[i][j][k] += delta;
23 }
24 }
25 }
26
27 int sum( int x, int y , int z )
28 {
29 int res = 0, i, j , k;
30 for(i=x; i>0; i-=lowbit(i))
31 {
32 for(j=y; j>0; j-=lowbit(j))
33 {
34 for(k=z; k>0; k-=lowbit(j))
35 {
36 res += c[i][j][k];
37 }
38 }
39 }
40 return res;
41 }
42
43
44 void init ()
45 {
46 int i,j,k;
47 for(i=0;i<=N;i++)
48 for(j=0;j<=N;j++)
49 for(k=0;k<=N;k++)
50 c[i][j][k]=0;
51 }
52
53 int main()
54 {
55 int x1,y1,z1,x2,y2,z2;
56 int temp,p;
57
58 while(scanf("%d%d%",&N,&p)!=EOF)
59 {
60 init ();
61 while(p--)
62 {
63 scanf("%d",&temp);
64 if(temp==1)
65 {
66 // printf("input x1~z2
");
67
68 scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
69 update(x2+1, y2+1, z2+1, 1);
70 update(x1, y2+1, z2+1, 1);
71 update(x2+1, y1, z2+1, 1);
72 update(x2+1, y2+1, z1, 1);
73 update(x1, y1, z2+1, 1);
74 update(x2+1, y1, z1, 1);
75 update(x1, y2+1, z1, 1);
76 update(x1, y1, z1, 1);
77
78 }
79 else if(temp==0)
80 {
81 scanf("%d%d%d",&x1,&y1,&z1);
82 printf("%d
",sum(x1,y1,z1)&1);
83 }
84 }
85 }
86
87 return 0 ;
88 }View Code