CodeForces - 1323B Count Subrectangles(思维)

题目链接：点击查看

题目大意：给出一个数组 a 和数组 b 只由 0 和 1 构成，构造出矩阵 maze[ x ][ y ] = a[ x ] * b[ y ]，显然maze矩阵同样只由 0 和 1 构成，现在要求面积为 k 的子矩阵中，有多少个全部为 1 

题目分析：再次感觉难度大于 C 题的一道 B 题。。考察的方面很综合，不知道如何分类，就暂且分为思维吧，首先排除n*m*n*m的暴力，接下来一步一步考虑，因为面积为 k 的子矩阵，换一种说法，假设子矩阵的大小为 x * y ，则必须满足 x * y == k 的子矩阵才可能满足条件，所以不难想到要对面积 k 进行因数分解，sqrt( k )的时间复杂度预处理出 k 的所有因数作为子矩阵的长和宽，对于每一对可行的长和宽 ( x , y ) 来说，都需要计算其贡献，接下来说的内容可能有点抽象，后面我会举例子说明的。现在的问题转换为了，给出指定大小的子矩阵 ( x , y ) ，如何计算出其出现次数，通过观察样例给出的矩阵可以发现，假设某个子矩阵的左上角端点为( x1 , y1 )，右下角端点为( x2 , y2 )，若该子矩阵想要全部为 1 的话，那么数组 a[ x1 ] ~ a[ x2 ] 以及 b[ y1 ] ~ b[ y2 ] 的这两段连续区间内必须全部为 1 才行，这样就可以将数组 a 以及数组 b 转换为连续的 1 储存了，比如数组 a 原本为 1011011101 ，那么转换后就变为了 1,2,3,1 了，我们记为 aa 数组和 bb 数组，这样转换后有什么用呢？剩下的其实就可以排列组合计算答案了，还是以大小为( x , y )的子矩阵为例，我们遍历一遍 aa 数组，可以对大小为 x * y 的子矩阵做出贡献，那么必须满足连续的行数大于等于 x 才行，通过平移可以知道，贡献就是 aa[ i ] - x + 1 了，遍历一遍数组aa后，可以计算出有多少种行可以做出贡献，同理遍历一遍 bb 数组后计算出有多少列可以做出贡献，相乘就是总贡献了

下面举一个例子，就拿样例为例，a 数组为 1 0 1，转换为 aa 数组也就变成了 1,1

b 数组为 1 1 1，转换为 bb 数组也就变成了 3

以大小为 ( 1 , 2 ) 的子矩阵为例，我们需要在 aa 数组中找到有多少个连续的行满足 aa[ i ] >= 1，显然有两个

接下来需要在 bb 数组中找到有多少个连续的列，满足 bb[ i ] >= 2 ，因为 bb 数组只有一个元素，且其值为 3 ，那么对列的贡献也就是 2 了，因为可以这样选：（选橙色的列）

1 1 1

也可以这样选：

1 1 1

综上，对于子矩阵 ( 1 , 2 ) 的贡献为 2 * 2 = 4

总时间复杂度为 sqrt( n * m )*( n + m )，我用了unordered_map稍加优化，而且sqrt(n*m)应该也不会拉满，所以评测机给出的反馈是十分不错的

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<unordered_map>
using namespace std;
      
typedef long long LL;
     
typedef unsigned long long ull;
      
const int inf=0x3f3f3f3f;
 
const int N=4e4+100;

int a[N],b[N];

vector<pair<int,int>>node;

void init(int k)
{
	for(int i=1;i*i<=k;i++)
	{
		if(k%i==0)
		{
			node.push_back(make_pair(i,k/i));
			if(i!=k/i)
				node.push_back(make_pair(k/i,i));
		}
	}
}

unordered_map<int,int>A,B;

void solve(int a[],int n,unordered_map<int,int>& mp)
{
	int pos=1,cnt=0;
	while(pos<=n)
	{
		while(a[pos])
		{
			pos++;
			cnt++;
		}
		if(cnt)
		{
			mp[cnt]++;
			cnt=0;
		}
		pos++;
	}
}

int main()
{
#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif
//	ios::sync_with_stdio(false);
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	init(k);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1;i<=m;i++)
		scanf("%d",b+i);
	solve(a,n,A);//预处理出aa数组和bb数组，存放在unordered_map中
	solve(b,m,B);
	LL ans=0;
	for(int k=0;k<node.size();k++)//遍历每对因子
	{
		int x=node[k].first,y=node[k].second;
		LL xx=0,yy=0;
		for(auto it:A)//行贡献
			if(it.first>=x)
				xx+=it.second*(it.first-x+1);
		for(auto it:B)//列贡献
			if(it.first>=y)
				yy+=it.second*(it.first-y+1);
		ans+=xx*yy;//累加贡献
	}
	printf("%lldn",ans);
	
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}

最后

以上就是微笑曲奇为你收集整理的CodeForces - 1323B Count Subrectangles(思维)的全部内容，希望文章能够帮你解决CodeForces - 1323B Count Subrectangles(思维)所遇到的程序开发问题。

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