【每日一题】「土」秘法地震

Description

帕秋莉掌握了一种土属性魔法

这种魔法可以在一片k×k大小的一个正方形区域内产生地震

但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法

整个地图大小为n×m，其中一些地方有建筑

请问有多少种可能的情况，使得帕秋莉会停止施法

Solution

题意就是要找每一个 $k * k$ 的小正方形里至少有一个1的数量
显然我们可以通过二维前缀和处理出(1, 1) 到 (n, m) 的数量
然后通过枚举处理出答案，具体思想是容斥
令 $dp[i][j]$ 为 (1, 1) 到 (n, m) 的1的数量
有递推式子 $dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + pos_{i,j} == '1'$
这个式子可以看成以下图形
图片说明
减去上下两个矩形的1的数量，然后蓝色的区域会被减两次，要加回来一次
最后我们枚举所有 $k * k$ 的正方形统计即可

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll mod = 1e9 + 7;
const int N = 2e5 + 5;

int n, m, k;
int dp[1005][1005];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> n >> m >> k;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      char p;
      cin >> p;
      dp[i][j] += (p == '1');
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    }
  }
  int ans = 0;
  for(int i = k; i <= n; i++) {
    for(int j = k; j <= m; j++) {
      if(dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k] > 0) {
        ans++;
      }
    }
  }
  cout << ans << "\n";
  return 0;
}