E - Defect-free Squares
给你一个\(n \times m\)的方格矩阵,矩阵上有一些洞,然后让你求出所有的不含洞的正方形数量
\(1 \leq n,m \leq 3000\)
题解:二维前缀和 + 二分答案
- 我们先考虑一维上的问题,假设一维上有些位置上有漏洞,然后让你求出所有满足\([l,r]\)区间中没有洞的合法区间数量
- 我们考虑预处理前缀和\(pre\),如果\(pre[r] - pre[l - 1] =0\),说明\([l,r]\)中没有洞
- 那么我们发现,对于一个固定的区间右端点\(r\)来说,左端点\(l\)具有二分性,我们完全可以通过二分找到\(l\),那么区间个数为\(r - l + 1\)
- 所以我们只需要枚举\(r\)即可,然后对于每一个\(r\)的位置二分找出\(l\),记录对答案的贡献即可
- 那么现在问题转化到了二维上
- 我们可以预处理二维前缀和
- 显然类似一维,我们可以枚举每一个点作为正方形的右下角,二分正方形的边长即可
const int N = 3e3 + 10, M = 4e5 + 10;
int n, m, q;
int g[N][N];
int pre[N][N];
bool check(int x, int y, int mid)
{
int x1 = x - mid + 1;
int y1 = y - mid + 1;
int sum = pre[x][y] - pre[x][y1 - 1] - pre[x1 - 1][y] + pre[x1 - 1][y1 - 1];
return sum == 0;
}
void solve()
{
cin >> n >> m >> q;
for (int i = 1; i <= q; ++i)
{
int x, y;
cin >> x >> y;
g[x][y] = 1;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + g[i][j];
int ans = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (g[i][j])
continue;
int l = 1, r = min(i, j); // 二分正方形的边长的长度
while (l <= r)
{
int mid = l + r >> 1;
if (check(i, j, mid))
l = mid + 1;
else
r = mid - 1;
}
ans += r;
}
}
cout << ans << endl;
}
- Beginner AtCoder Contest 311beginner atcoder contest 311 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310