洛谷 P1387 最大正方形（前缀和，二分）()-其他

发表于： 11月 30, 2022 11月 30, 2022
分类：其他
标签：其他

洛谷 P1387 最大正方形（前缀和，二分）()

题目分析

当一个边长为x的正方形不包含0时，这个正方形内的二维前缀和为x*x，题目想求满足条件的最大的正方形的边长

假如最大的正方形的边长为ans，那么凡是边长大于ans的正方形一定不满足条件，同时一定能找到边长小于ans且满足条件的正方形，因此我们还想到二分

参考代码

暴力

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
	for (int i = mid; i <= n; i ++ )
	{
		for (int j = mid; j <= m; j ++ )
		{
			if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] == mid * mid) return 1;
		}
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			cin >> a[i][j];
			s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	int l = 1, r = min(n, m);
	for (int i = r; i >= 1; i -- )
	{
		if (check(i))
		{
			cout << i << endl;
			break;
		}
	}
	return 0;
}

二分答案

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
	for (int i = mid; i <= n; i ++ )
	{
		for (int j = mid; j <= m; j ++ )
		{
			if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] >= mid * mid) return 1;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;	
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			cin >> a[i][j];
			s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	int l = 1, r = min(n, m);
	while (l < r)
	{
		int mid = l + (r - l + 1) / 2;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << '\n';
	return 0;
}

————————

题目分析

当一个边长为x的正方形不包含0时，这个正方形内的二维前缀和为x*x，题目想求满足条件的最大的正方形的边长

假如最大的正方形的边长为ans，那么凡是边长大于ans的正方形一定不满足条件，同时一定能找到边长小于ans且满足条件的正方形，因此我们还想到二分

参考代码

暴力

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
	for (int i = mid; i <= n; i ++ )
	{
		for (int j = mid; j <= m; j ++ )
		{
			if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] == mid * mid) return 1;
		}
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			cin >> a[i][j];
			s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	int l = 1, r = min(n, m);
	for (int i = r; i >= 1; i -- )
	{
		if (check(i))
		{
			cout << i << endl;
			break;
		}
	}
	return 0;
}

二分答案

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
	for (int i = mid; i <= n; i ++ )
	{
		for (int j = mid; j <= m; j ++ )
		{
			if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] >= mid * mid) return 1;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;	
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			cin >> a[i][j];
			s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	int l = 1, r = min(n, m);
	while (l < r)
	{
		int mid = l + (r - l + 1) / 2;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << '\n';
	return 0;
}