欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU - 6514 - Monitor(二维差分)

程序员文章站 2022-07-12 17:38:56
...

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6514

题意:n*m的矩阵,给出p个监控器的监控矩阵范围,q次询问,给出一矩阵,如果能全部监控到输出YES,否则输出NO。

思路:二维差分,但是数据比较大开不了二维数组,可以用vector <vector <int> >,或者对于每一个二维HDU - 6514 - Monitor(二维差分)hash成一维HDU - 6514 - Monitor(二维差分),然后求一下前缀和,然后遍历一下把非0值重新赋值为1,再求一次前缀和,最后HDU - 6514 - Monitor(二维差分)查询答案即可。

hash版本:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20000010;
int pre[maxn];
int n, m, k, q;
int col(int x,int y)
{
    return x * (m + 1) + y;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        n++; m++;
        for(int i = 0; i <= n * m; i++) pre[i] = 0;
        scanf("%d",&k);
        int x1, y1, x2, y2;
        for(int i = 1; i <= k; i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            pre[col(x1, y1)]++; pre[col(x1, y2+1)]--;
            pre[col(x2+1,y1)]--; pre[col(x2+1, y2+1)]++;
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                pre[col(i,j)] += pre[col(i,j-1)] + pre[col(i-1,j)] - pre[col(i-1,j-1)];

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                pre[col(i,j)] = bool(pre[col(i,j)]);

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                pre[col(i,j)] += pre[col(i,j-1)] + pre[col(i-1,j)] - pre[col(i-1,j-1)];

        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int ans = pre[col(x2,y2)] - pre[col(x2,y1-1)] - pre[col(x1-1,y2)] + pre[col(x1-1,y1-1)];
            if(ans == (x2 - x1 + 1) * (y2 - y1 + 1)) puts("YES");
            else puts("NO");
        }
    }
}
/*
6 6
3
2 2 4 4
3 3 5 6
5 1 6 2
2
3 2 5 4
1 5 6 5
*/

vector版本:

#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        scanf("%d",&k);
        int x1, y1, x2, y2;
        vector<vector<int> > a(n + 2, vector<int> (m + 2));
        while(k--)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            a[x1][y1]++, a[x1][y2+1]--;
            a[x2+1][y1]--, a[x2+1][y2+1]++;
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                a[i][j] = bool(a[i][j]);


        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];

        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int ans = a[x2][y2] - a[x1-1][y2] - a[x2][y1 - 1] + a[x1-1][y1-1];
            if(ans == (x2 - x1 + 1) * (y2 - y1 + 1)) puts("YES");
            else puts("NO");
        }
    }

}
/*
6 6
3
2 2 4 4
3 3 5 6
5 1 6 2
2
3 2 5 4
1 5 6 5
*/