[CodeForces-1323B] - Count Subrectangles

[CodeForces-1323B] - Count Subrectangles

题意：

• 给定两个只包含01的数列a[ ], b[ ]，我们可以得到一个矩阵c[i][j] = a[i] * b[j]. 我们需要找到矩阵c中，面积为k的子矩阵个数。

思路：

• 可以肯定的是a数组连续1和b数组连续1才有可能构成合法矩阵。问题是我们如何得到所有合法矩阵的个数，也就是如何遍历呢？
• 长度为n的数组a，那么连续1的个数一定是<=n的. 对于长度为len的连续1的子串，我们可以将其拆成$1\le i\le len$ 的子串，个数是$len-i+1$个。
• 对于长度为m的数组b，进行同样的处理。
• 那么我们遍历处理出来的a的可行长度$i$，对应的b的可行长度是$k/i$。条件自然就是k % i == 0 && k / i <= m

以上，我们可以在O(n + m)的范围内处理该题。注意答案要用ll，不然凉凉~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
const int maxN = 40004;
int n, m, k;
int a[maxN], b[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();
vector<int>laterA(n + 1), laterB(m + 1);
int now = 0;
for(int i = 1; i <= n; ++ i )
if(a[i]) ++ now;
else if(now)
{
for(int len = 1; len <= now; ++ len)
laterA[len] += (now - len + 1);
now = 0;
}
if(now)
{
for(int len = 1; len <= now; ++ len)
laterA[len] += (now - len + 1);
now = 0;
}
for(int i = 1; i <= m; ++ i )
if(b[i]) ++ now;
else if(now)
{
for(int len = 1; len <= now; ++ len)
laterB[len] += (now - len + 1);
now = 0;
}
if(now)
{
for(int len = 1; len <= now; ++ len)
laterB[len] += (now - len + 1);
}
ll ans = 0;
for(int i = 1; i <= n; ++ i )
{
if(k % i == 0 && k / i <= m)
ans += laterA[i] * laterB[k / i];
}
cout << ans << endl;
return 0;
}

最后

以上就是玩命奇迹为你收集整理的[CodeForces-1323B] - Count Subrectangles的全部内容，希望文章能够帮你解决[CodeForces-1323B] - Count Subrectangles所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。