Monitor HDU 6514 二维差分入门学习

题意

小腾有\(n*m\)的田地，但是有小偷来偷东西，在一片矩形区域上，有一部分区域是监控可以覆盖到的，这部分区域由一个或多个包含于该矩形区域的小矩形构成；现在给你另一个包含在该矩形区域的小矩形A，问你这个小矩形能否被监控完全覆盖。

解题思路

这个题可以模拟做，就是开一个二维数组，把能监控的区域标记为1，否者就是0，然后在给的小矩形内看看这里面1的个数已不是等于小矩形的面积，是的话就是YES，否者就是NO。但是这个方法会超时。我就无能为力了，这时旁白同学说这个题得用二维差分来做（还没学过），神奇，我就找了个博客，有位大佬正好写了这道题，而且很详细，易懂，点我进来。

这里我就补充一下自己看过这个博客后的一点见解。

这里建立二维数组，坐标不用像大佬所说的那样转换，就正常那样就行，二维数组可以正常表示，不用把左下改为左上，右上改为右下，这里可能是那位作者想错了。
这里需要使用vector来建立二维数组，要不然会爆，而这里如何用vector来建立二维数组我还真不会，下面代码里见（这个也很重要）。
感觉差分就是树状数组的简洁版。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn=1e7+7;

int n, m, p, q;

int main()

{

	int x1, y1, x2, y2;

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

	{

	vector< vector<int> > recode(n+2, vector<int>(m+2)), glass(n+2, vector<int>(m+2));

	//这里n+2代表第一维的参量，第二个是代表第二维

        //这样声明vector后就可以直接使用recode[i][j],只要在范围内就行

        //如果使用vector<int> recode[maxm],我们不能直接使用比如recode[2][3]，

        //因为可能在recode[2][3]之前，并没有数字存储。

        scanf("%d", &p);

		for(int i=1; i<=p; i++)

		{

			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

			recode[x1][y1]++;

			recode[x2+1][y2+1]++;

			recode[x1][y2+1]--;

			recode[x2+1][y1]--;

		}

		for(int i=1; i<=n; i++)

		{

			for(int j=1; j<=m; j++)

			{

				recode[i][j]+=recode[i-1][j]+recode[i][j-1]-recode[i-1][j-1];

			}

		}

		for(int i=1; i<=n; i++)

		{

			for(int j=1; j<=m; j++)

			{

				glass[i][j]+=glass[i-1][j]+glass[i][j-1]-glass[i-1][j-1] + ( recode[i][j]>0? 1:0);

			}

		}

		scanf("%d", &q);

		while(q--)

		{

			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

			int eara=glass[x2][y2]-glass[x2][y1-1]-glass[x1-1][y2]+glass[x1-1][y1-1];

			if(eara==(x2-x1+1)*(y2-y1+1))

			{

				printf("YES\n");

			}

			else printf("NO\n");

		}

	}

	return 0;

 }

巴特西

Monitor HDU6514 二维差分入门学习

Monitor HDU 6514 二维差分入门学习

题意

解题思路

代码实现

END

最新文章

热门文章