poj 1195 Mobile phones 解题报告

题目链接：http://poj.org/problem?id=1195

题目意思：有一部 mobie phone 基站，它的面积被分成一个个小正方形（1 * 1 的大小），所有的小正方形的面积构成了一个 S * S 大小的矩阵（下标都是从 0 ~ S-1 变化的）。

　　有四种指令：

　　第一行的指令默认输入是 0，空格之后是矩阵的大小： S

最后一行的指令是 3，代表整个输入结束

注意：这两行的指令只会出现一次！

夹在它们中间的指令有可能是指令1，假设为X Y A，代表向第 X 行第 Y 列的那个小正方形加上A （可正可负），不需要输出结果。又或者是指令2，假设为 L B R T，代表要计算出行 L ~ R，列 B ~ T 所围住的矩形的和，这个指令要求输出这个和。

看了很久，终于看明白题目了，表示英文太差，经常看不懂POJ 的英文题 = =。

二维树状数组，有了前一天二维树状数组探索版的积累，套了下模板。不过询问那里，也就是指令 2 的输出有点问题，今天终于改好了，happy ^_^ ....

首先要知道二维树状数组这个模板的 Sum 究竟算出来的是什么：假如调用的是Sum(i， j)啦，那么它求出的是从最左上角的坐标到坐标 (i, j) 所围的面积的和！！！那么如果要求特定的某个子矩阵的面积（例如 (2， 3) ~ (3，4)），就需要减去相应不需要的部分啦。

数字4 是我们要求的部分，如果单纯调用Sum(3, 4) 的话，得出的是编号 1 的和，那么我们需要减去2和3的和，才能得出4的和，而要得出2的和，也需要减去[A11 + A12]这个矩阵的和啦，也就是Sum(3, 2) - Sum(1, 2)，对应代码中的 Sum(R+1, B)-Sum(L, B)。而编号 3 的和对应代码： Sum(L, T+1)。

（之前错误地写成Sum(3, 4）- Sum(2, 3) 了， = =，粗心呀~~~，读者请忽略）

还有一个值得注意的地方是，树状数组下标是从1开始的，而题目坐标是从0开始的，所以不妨相应地向右下角移动一位，就是说，假设输入的是0 0，那么就看成是1 1 （这个是受hdu 1541 的 Stars 启发啦）

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int A[maxn][maxn];

 int C[maxn][maxn];

 int size;

 int lowbit(int x)

 {

     return x & (-x);

 }

 int Sum(int i, int j)

 {

     int result = ;

     for (int x = i; x > ; x -= lowbit(x))

     {

         for (int y = j; y > ; y -= lowbit(y))

             result += C[x][y];

     }

     return result;

 }

 void Modify(int i, int j, int delta)

 {

     A[i][j] += delta;

     for (int x = i; x < size+; x += lowbit(x))

     {

         for (int y = j; y < size+; y += lowbit(y))

             C[x][y] += delta;

     }

 }

 int main()

 {

     int x, y, ask, num, L, B, R, T;

     memset(A, , sizeof(A));

     memset(C, , sizeof(C));

     while (scanf("%d", &ask) != EOF && ask != )

     {

         if (ask == )

             scanf("%d", &size);

         else if (ask == )

         {

             scanf("%d%d%d", &x, &y, &num);

             Modify(x+, y+, num);

         }

         else if (ask == )

         {

             scanf("%d%d%d%d", &L, &B, &R, &T);

             printf("%d\n", Sum(R+, T+)-(Sum(R+, B)-Sum(L, B))- Sum(L, T+));   // 对应图中的1-2-3

         }

     }

     return ;

 }

巴特西

poj 1195 Mobile phones 解题报告

最新文章

热门文章