AcWing 3617. 子矩形计数
原题链接
中等
作者:
术
,
2021-08-20 20:18:47
,
所有人可见
,
阅读 160
1.ON做法,差分找全1的连续区间数
#include <iostream>
using namespace std;
const int N=4e4+5;
int n,m,k;
int a[N],b[N];
int s1[N],s2[N];//长度为i的全1区间的数量
void work(int w[],int s[],int n){
for(int i=1,j=1;i<=n;i++){//也可以从0开始
if(w[i]){
//差分,长度为1~j的区间数+1
s[1]++;
s[++j]--;
}
else j=1;
}
for(int i=1;i<=n;i++) s[i]+=s[i-1],cout<<s[i]<<endl;
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
work(a,s1,n);
work(b,s2,m);
long long res=0;
for(int i=1;i<=n;i++){
if(k%i==0&&k/i<=m) res+=s1[i]*s2[k/i];
}
cout<<res;
//cout << "Hello world!" << endl;
return 0;
}
2.前缀和做法
#include <iostream>
using namespace std;
//先找k的约数ga,gb
//再在ab数组中找长度为ga,gb且全为1的子数组,求其个数numa,numb
//a中长度为ga的全1的连续线段数*b中长度为b的全1的连续线段数
//将所有k的约数对在ab中分别满足要求的区间数量相乘并相加,循环计算并相加
const int N=4e4+5;
const int K=N*N;
int n,m;
int k;
int a[N],b[N];
int sa[N],sb[N];//前缀和
int agcd[100000];//k的公约数
int numa[N],numb[N];//k每个公约数,在ab数组中全1线段数
long long res;
int main()
{
cin>>m>>n>>k;
for(int i=1; i<=n; i++)
{
cin>>a[i];
sa[i]+=sa[i-1]+a[i];
}
for(int i=1; i<=m; i++)
{
cin>>b[i];
sb[i]+=sb[i-1]+b[i];
}
//找k的所有约数
int cnt=0;
for(int i=1; i*i<=k; i++)
{
if(k%i==0&&i<=N&&k/i<=N)//注意k的取值范围
{
agcd[cnt++]=i;
if(k/i!=i)
agcd[cnt++]=k/i;
}
}
for(int j=0; j<cnt; j++)
{
int len=agcd[j];
for(int i=len; i<=n; i++)
{
if(sa[i]-sa[i-len]==len)
{
numa[len]++;
}
}
}
for(int j=0; j<cnt; j++)
{
int len=agcd[j];
for(int i=len; i<=m; i++)
{
if(sb[i]-sb[i-len]==len)
numb[len]++;
}
}
for(int j=0; j<cnt; j++)
{
res+=numa[agcd[j]]*numb[k/agcd[j]];
}
cout<<res;
//cout << "Hello world!" << endl;
return 0;
}