题解：P6600 「EZEC-2」字母

· · 题解

题目大意

给定一个 n\times m 的 01 矩阵， 要求你找出其中有多少个由 1 组成的并且符合条件的字母T。

思路解析

观察题目条件，我们不难发现，找到一个T的关键是找到T的横竖的交叉点，再由此我们可以联想到使用前缀后缀预处理统计出交叉点向左，向右，向下最多能有多少个连续的 1。
对于一个矩阵，我们可以暴力遍历每一个点，并且将其视为T的交叉点，根据前面统计出的前缀后缀快速得出在此交叉点上最大可以存在的T的横长和竖长。
但是，每个竖长横长还需满足题目所给出的如下条件:

因此，我们又可以暴力预处理出在各个情况下有多少个T。
考虑用 sum[i][j] 表示横长为 i 竖长为 j 时在条件下有多少个符合条件的T。
由此可得： 

for (int i = 3; i <= m; i ++ ) {
  for (int j = 2; j <= n; j ++ ) {
    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    if (i % 2 == 1 && i >= a && j >= b && (i * j) >= s && (i + j) >= x) {
      sum[i][j] ++;
    }
  }
}

最后，我们只需要统计每一个交叉点存在的T的个数的总和即可得出最终答案。
完结撒花。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3 + 10;
int vis[N][N], sum[N][N];
int ql[N][N], qr[N][N], qs[N][N];
signed main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, a, b, s, x;
    cin >> n >> m >> a >> b >> s >> x;
    string ts;
    for (int i = 1; i <= n; i ++ ) {
        cin >> ts;
        int len = ts.size(); ts = " " + ts;
        for (int j = 1; j <= len; j ++ ) {
            if (ts[j] == '1') vis[i][j] = 1;
        }
    }
    for (int i = 3; i <= m; i ++ ) {
        for (int j = 2; j <= n; j ++ ) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            if (i % 2 == 1 && i >= a && j >= b && (i * j) >= s && (i + j) >= x) {
                sum[i][j] ++;
            }
        }
    } // 统计当横长小于等于i,竖长小于等于j时有几个符合条件的T  
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            ql[i][j] = ql[i][j - 1] * vis[i][j] + vis[i][j]; 
        }
    } // 前缀统计一个点前面有多少个1 
    for (int i = 1; i <= n; i ++ ) {
        for (int j = m; j >= 1; j -- ) {
            qr[i][j] = qr[i][j + 1] * vis[i][j] + vis[i][j]; 
        }
    } // 后缀统计一个点后面有多少个1
    for (int i = 1; i <= m; i ++ ) {
        for (int j = n; j >= 1; j -- ) {
            qs[j][i] = qs[j + 1][i] * vis[j][i] + vis[j][i];
        }
    } // 后缀统计一个点后面有多少个1 
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) { // 暴力枚举每个交叉点 
            int minh = max (min (ql[i][j], qr[i][j]) * 2 - 1, (long long)(0)); // 横长 
            ans += sum[minh][qs[i][j]];
        }
    } 
    cout << ans;
}