题解：P6600 「EZEC-2」字母

题目大意

给定一个

n\times m

的

01

矩阵，要求你找出其中有多少个由

1

组成的并且符合条件的字母T。

思路解析

观察题目条件，我们不难发现，找到一个T的关键是找到T的横竖的交叉点，再由此我们可以联想到使用前缀后缀预处理统计出交叉点向左，向右，向下最多能有多少个连续的

1

。
对于一个矩阵，我们可以暴力遍历每一个点，并且将其视为T的交叉点，根据前面统计出的前缀后缀快速得出在此交叉点上最大可以存在的T的横长和竖长。
但是，每个竖长横长还需满足题目所给出的如下条件:

$w \ge a$
$h \ge b$
$w \times h \ge s$
$w + h \ge x$
$w$ 为奇数

因此，我们又可以暴力预处理出在各个情况下有多少个T。
考虑用

sum[i][j]

表示横长为

i

竖长为

j

时在条件下有多少个符合条件的T。
由此可得：

CPP

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的个数的总和即可得出最终答案。
完结撒花。

代码实现

CPP

#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;
}

题解：P6600 「EZEC-2」字母

文章操作

题目大意

思路解析

代码实现

相关推荐

评论

题解：P6600 「EZEC-2」字母