Codeforces Round #632 (Div. 2) / 1333C】- C. Eugene and an array

题面

Eugene likes working with arrays. And today he needs your help in solving one challenging task.

An array cc is a subarray of an array bb if cc can be obtained from bb by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Let’s call a nonempty array good if for every nonempty subarray of this array, sum of the elements of this subarray is nonzero. For example, array [-1, 2, -3][−1,2,−3] is good, as all arrays [-1][−1], [-1, 2][−1,2], [-1, 2, -3][−1,2,−3], [2][2], [2, -3][2,−3], [-3][−3] have nonzero sums of elements. However, array [-1, 2, -1, -3][−1,2,−1,−3] isn’t good, as his subarray [-1, 2, -1][−1,2,−1] has sum of elements equal to 00.

Help Eugene to calculate the number of nonempty good subarrays of a given array aa.

题意

给一个两个一维数组组成的矩阵，问其中用1组成的面积为k的矩阵有多少个

分析

枚举矩形的边长x，再统计每行每列的连续x个1的个数即可

统计个数的处理方式可以是输入时预处理f[i] = f[i – 1] + 1；
也可以是遍历到超过k就计数，不是1就归零

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
inline int read() {
	register int x = 0, f = 1;
	register char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0',c = getchar();
	return x * f;
}
const int MAXN = 4e4 + 1;
int n, m, k, cnt;
ll ans;
int a[MAXN], b[MAXN], fac[MAXN];
int main() {
	n = read(), m = read(), k = read();
	for (int i(1); i <= n; i++) a[i] = read();
	for (int i(1); i <= m; i++) b[i] = read();
	for (int i(1); i <= sqrt(k); i++){
		if (!(k % i)){
			fac[++cnt] = i;
			if (i * i == k) break;
			fac[++cnt] = k / i;
		}
	}
	for (int i(1); i <= cnt; i++){
		int row = fac[i], col = k / fac[i];
		int sum = 0, cnt_row = 0, cnt_col = 0;
		for (int j(1); j <= n; j++){
			if (a[j]) sum++;
			else sum = 0;
			if (sum >= row) cnt_row++;
		}
		sum = 0;
		for (int j(1); j <= m; j++){
			if (b[j]) sum++;
			else sum = 0;
			if (sum >= col) cnt_col++; 
		}
		ans += cnt_row * cnt_col;
	}
	printf("%lld\n", ans);
	return 0;
}

原文地址：http://www.cnblogs.com/cancers/p/16833262.html