首页 > ACM题库 > HDU-杭电 > HDU 4721-Food and Productivity-分治-[解题报告]HOJ
2015
09-17

HDU 4721-Food and Productivity-分治-[解题报告]HOJ

Food and Productivity

问题描述 :

In the Game Civilization X, the world is made up of square-shaped "tiles", forming a rectangle on the world map. For a tile located at row X and column Y , we give it a coordinate, say (X, Y ).
As you can see, different tiles have different "terrain-types", so they may have different amount of Resources. In this problem, we only consider two of them: Food and Productivity.
An important step in the Game is building cities. After you choose a tile to build a city, the Food amount in that tile will increase by A, and the Productivity amount will increase by B, no other tiles will be changed.
You decide to build your first city on the map, as an experienced player, you will choose the best tile on the map, here is how you make up your mind:
For each tile (X, Y ), you set up an "Influence Range" of that tile. Each tile (xi, yi) is said to be within the range if the following equation holds:
max(|X – xi| , |Y – yi|) <= R

After checking all the tiles within that range, you will get two values: the sum of all those tiles’ Food amount, and the sum of all those tiles’ Productivity. Among those two values, the final score for tile (X, Y ) will be the smaller one.
When choosing tiles, you just choose the tile with the highest score to build your city.
You are given a map with size N * M, and you wonder, for different values of A and B, what is the highest score for your first city?

输入:

The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, first line has four numbers N, M, R and Q (1 <= N, M <= 500, 0 <= 2 * R + 1 <= min(N,M), Q <= 200000), which is the size of the map.
Then come N lines each with M numbers, they are the original Food (0 < Food <= 3) amount for each tile.
Then come N lines each with M numbers, they are the original Productivity
(0 < Productivity <= 3) amount for each tile.
Then come Q lines each with two numbers A and B (0 <= A, B <= 106). Each is a query for you to answer. Those queries will not affect each other.

输出:

The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, first line has four numbers N, M, R and Q (1 <= N, M <= 500, 0 <= 2 * R + 1 <= min(N,M), Q <= 200000), which is the size of the map.
Then come N lines each with M numbers, they are the original Food (0 < Food <= 3) amount for each tile.
Then come N lines each with M numbers, they are the original Productivity
(0 < Productivity <= 3) amount for each tile.
Then come Q lines each with two numbers A and B (0 <= A, B <= 106). Each is a query for you to answer. Those queries will not affect each other.

样例输入:

1
3 3 0 2
1 2 1
1 1 1
1 1 1
1 1 1
1 2 1
1 1 1
1 2
2 1

样例输出:

Case #1:
3
3

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by—cxlove

题意 :给出n * m的格子,每个格子有两个属性food , prod。对于每一个查询A,B,可以选择某个格子将food属性+A,prod+B,然后以这个格子为中心的正方形两个属性和的最小值最大。

http://acm.hdu.edu.cn/showproblem.php?pid=4721

其实很简单的题, 很早就会了,WA了好多天,结果是一个乘号打成了加号。。。不能更逗

由于所有属性值为正,所以没必要取边界上不完整的正方形,不过处理下也没事。。。

正方形的连长为2 * r + 1,预处理一下子矩阵和。

将所有的正方形两个属性和提取出来,离散化一下food,用BIT维护prod属性的前缀最大值。

对于每一次查询,二分答案ans , 两个属性和都要大于等于ans。

二分下food,查询一下prod的最值。

逆序后维护前缀最大值。。


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#define lson step << 1
#define rson step << 1 | 1
#define lowbit(x) (x & (-x))
#define Key_value ch[ch[root][1]][0] 
using namespace std;
typedef long long LL;
const int N = 505;
int n , m , r , q;
int food[N][N] , prod[N][N];
int a[N * N] , b[N * N] , tot , x[N * N];
int s[N * N] , cnt;
void add (int x , int v) {
    for (int i = x ; i <= cnt ; i += lowbit (i)) {
        s[i] = max (s[i] , v);
    }
}
int ask (int x) {
    int ret = 0;
    for (int i = x ; i > 0 ; i -= lowbit (i)) {
        ret = max (ret , s[i]);
    }
    return ret;
}
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
        // freopen ("output.txt" , "w" , stdout);
    #endif
    int t , cas = 0;
    scanf ("%d" , &t);
    while (t --) {
        memset (food , 0 , sizeof(food));
        memset (prod , 0 , sizeof(prod));
        memset (s , 0 , sizeof(s));
        scanf ("%d %d %d %d" , &n , &m , &r , &q);
        for (int i = 1 ; i <= n ; i ++) {
            for (int j = 1 ; j <= m ; j ++) {
                scanf ("%d" , &food[i][j]);
                food[i][j] += food[i - 1][j] + food[i][j - 1] - food[i - 1][j - 1];
            }
        }
        for (int i = 1 ; i <= n ; i ++) {
            for (int j = 1 ; j <= m ; j ++) {
                scanf ("%d" , &prod[i][j]);
                prod[i][j] += prod[i - 1][j] + prod[i][j - 1] - prod[i - 1][j - 1];
            }
        }
        tot = 0;
        r = 2 * r + 1;
        for (int i = r ; i <= n ; i ++) {
            for (int j = r ; j <= m ; j ++) {
                a[tot] = food[i][j] - food[i][j - r] - food[i - r][j] + food[i - r][j - r];
                b[tot] = prod[i][j] - prod[i][j - r] - prod[i - r][j] + prod[i - r][j - r];
                x[tot] = a[tot];
                tot ++;
            }
        }
        sort (x , x + tot);
        cnt = unique (x , x + tot) - x;
        for (int i = 0 ; i < tot ; i ++) {
            int y = cnt - (lower_bound (x , x + cnt , a[i]) - x);
            add (y , b[i]);
        }
        printf ("Case #%d:\n" , ++ cas);
        while (q --) {
            int A , B;
            scanf ("%d %d" , &A , &B);
            int low = min (A , B) + r * r * 1 , high = min (A , B) + r * r * 3 , mid , ans;
            while (low <= high) {
                mid = (low + high) >> 1;
                int y = cnt - (lower_bound (x , x + cnt , mid - A) - x);
                if (y < 1) {
                    high = mid - 1;
                    continue;
                }
                int tmp = ask (y);
                if (tmp + B >= mid) {
                    ans = mid;
                    low = mid + 1;
                }
                else high = mid - 1;
            }
            printf ("%d\n" , ans);
        }
        if (t) puts ("");
    }
    return 0;
}       

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/11853303