Prince Ray’s Puzzle
时间限制(普通/Java):10000MS/30000MS 运行内存限制:65536KByte
总提交:683 测试通过:110
描述
Prince Ray wants to marry his girl friend, beautiful Princess Amy. Amy loves Ray, and is very willing to take him. However, Amy’s father, King StreamSpeed, insists that his son in law should be talented enough, so that he could let him be the King of this country after King StreamSpeed retired. So he gives Ray a Test.
Ray is given a large brick of size n*n*n, which contains n*n*n grids of size 1. Every grid can be represent as a triple(x, y, z) (1<=x, y, z<=n). There are numbers in every grid. All the numbers are initially set to zero.
King StreamSpeed will do three operations to the brick.
1. Add a number to a given grid’s number
2. Subtract a number from a given grid’s number
3. Query the sum of total number from(x1,y1,z1) to (x2,y2,z2)
(x1 <= x2, y1 <= y2, z1 <= z2)
As Ray ‘s best friend and most excellent coder, you are required to write a program to answer all the queries to help Ray marry with her valentine.
输入
The first line of the input contains an integer n(1<=n<=100), the size of the brick. Then follow several lines in the following format:
A x y z num : Add num to (x, y, z)
S x y z num: Subtract num from (x, y, z)
Q x1 y1 z1 x2 y2 z2 : Query the sum of numbers from (x1, y1 , z1) to (x2 , y2 , z2)
The number of all the queries will be no more than 1000000.Input file is ended by a zero and should not be processed.
输出
For every query in the input file, your program should output the corresponding result -- the sum of numbers in the range (x1, y1, z1) ~(x2, y2, z2). The result does not exceed 10^9.
样例输入
10
A 1 1 4 5
A 2 5 4 5
Q 1 1 1 10 10 10
S 3 4 5 34
Q 1 1 1 10 10 10
0
样例输出
10
-24
提示
Huge input file, scanf is recommended.
题目来源
Narashy
分析：运用数据结构方法较难的一道题，费了我小半天的时间弄出来了：其中关键的是树状数组，与pku1195类似，不过pku1195是2维的而此题是3维的。下面介绍下树状数。 这是一个外国人详细介绍的BIT的理论和应用在poor English的水平下恍然大悟的明白了树状数组的原理，，就是构造BIT时一个更新，一个求和的问题，觉得那个结构确实巧妙，起码了解了原理对于掌握有很大的好处的。 http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees膜拜下下。 以下摘自 http://wtommy.ycool.com/post.766159.html什么是树状数组写的比较详细。 三个重要的函数 Lowbit
 #define lowbit(t) (t&-t)
没太明白为什么， 也可以写成
#define lowbit(t) ( t & ( t ^ (t-1) ) )
因为可以理解t是几个数的和看二进制时后面全0的个数，很精彩。 然后是更新代码：
  void update(int x , int y , int z ,int val) {
 int y1,z1;
  while (x <= n){
y1 = y;
while (y1 <= n){
z1=z;
while (z1<=n)
{
c[x][y1][z1] += val;
z1+=lowbit(z1);
 }
y1 += lowbit(y1);
}
x += lowbit(x);
}
 }
求和：
int summ(int x,int y,int z)
{
int sum=0,y1,z1;
while (x>0)
{
y1=y;
while (y1>0)
{
z1=z;
while (z1>0)
{
sum+=c[x][y1][z1];
z1-=lowbit(z1);
}
y1 -= lowbit(y1);
}
x -= lowbit(x);
}
return sum;
}
其次是动态构建三维数组，呵呵，头次接触
int ***c;
c=(int ***)malloc(n*sizeof(int**));
for (x=0;x<n;x++)
{
c[x] = (int**)malloc(n*sizeof(int*));
for (y=0;y<n;y++)
{
c[x][y] = (int*)malloc(n*sizeof(int));
for (z=0;z<n;z++)
{
c[x][y][z]=0;
}
}
}
最好附上ac代码：
#include<stdio.h>
#include <stdlib.h>
#include <string>
//#define Max_N 101
//int c[Max_N][Max_N][Max_N],n;
#define lowbit(t) (t&-t)
int ***c,n;
int summ(int x,int y,int z)
{
int sum=0,y1,z1;
while (x>0)
{
y1=y;
while (y1>0)
{
z1=z;
while (z1>0)
{
sum+=c[x][y1][z1];
z1-=lowbit(z1);
}
y1 -= lowbit(y1);
}
x -= lowbit(x);
}
return sum;
}
void update(int x , int y , int z ,int val){
int y1,z1;
while (x <= n){
y1 = y;
while (y1 <= n){
z1=z;
while (z1<=n)
{
c[x][y1][z1] += val;
z1+=lowbit(z1);
}
y1 += lowbit(y1);
}
x += lowbit(x);
}
}
int main()
{
int x,y,z,val,x1,y1,z1;
char ch;
scanf("%d",&n);
// memset(c,0,sizeof(c));
n++;
c=(int ***)malloc(n*sizeof(int**));
for (x=0;x<n;x++)
{
c[x] = (int**)malloc(n*sizeof(int*));
for (y=0;y<n;y++)
{
c[x][y] = (int*)malloc(n*sizeof(int));
for (z=0;z<n;z++)
{
c[x][y][z]=0;
}
}
}
n--;
getchar();
while (scanf("%c",&ch),ch!='0')
{
getchar();
switch(ch)
{
case 'A':scanf("%d %d %d %d",&x,&y,&z,&val);update(x,y,z,val);break;
case 'S':scanf("%d %d %d %d",&x,&y,&z,&val);val=-val;update(x,y,z,val);break;
case 'Q':scanf("%d %d %d %d %d %d",&x1,&y1,&z1,&x,&y,&z);
x1--;
y1--;
z1--;
printf("%d\n",summ(x,y,z)-summ(x,y,z1)-summ(x,y1,z)-summ(x1,y,z)
+summ(x,y1,z1)+summ(x1,y,z1)+summ(x1,y1,z)-summ(x1,y1,z1)); break;
}
getchar();
}
}
发现动态的，要比静态的快一点.
|