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> >,或者对于每一个二维hash成一维,然后求一下前缀和,然后遍历一下把非0值重新赋值为1,再求一次前缀和,最后查询答案即可。
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
*/