题意:给定一个矩形,现在给出这个矩形中某些点存在柿子树,问在一个长和宽限定的子矩形内最多有多少个柿子树.

解法:由于此题中数据量不大.直接树状数组统计然后暴力.

代码如下:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int N, R, C, dx, dy;int tr[105][105];inline int lowbit(int x) {    return x & -x;    }void modify(int x, int y, int val) {    for (int i = x; i <= R; i+=lowbit(i)) {        for (int j = y; j <= C; j+=lowbit(j)) {            tr[i][j] += val;        }    }    }int sum(int x, int y) {    int ret = 0;    for (int i = x; i > 0; i-=lowbit(i)) {        for (int j = y; j > 0; j-=lowbit(j)) {            ret += tr[i][j];            }    }    return ret;}int get(int x, int y) {    int ret, x0 = x-dx, y0 = y-dy;    ret = sum(x, y) - sum(x0, y) - sum(x, y0) + sum(x0, y0);    return ret;}int main() {    int x, y, ret;    while (scanf("%d", &N), N) {        memset(tr, 0, sizeof (tr));        ret = 0;        scanf("%d %d", &C, &R); // 先读列再读行        for (int i = 0; i < N; ++i) {            scanf("%d %d", &y, &x);            modify(x, y, 1);        }        scanf("%d %d", &dy, &dx);        for (int i = dx; i <= R; ++i) {            for (int j = dy; j <= C; ++j) {                ret = max(ret, get(i, j));            }            }        printf("%d\n", ret);    }    return 0;}