首先本题求面积为k的矩形 k=长宽 用变量 表示k=xy
也就是说找到a数组中 长度为x的连续1数量,再找到b数组中 长度为y的连续1数量相乘就是答案

算法1

(暴力枚举)不用差分 一个一个找

数据范围比较大 这样写数据小的都ok

C++ 代码

void f(bool *a,int *s,int n){//s[i]表示长度为i的连续1数量 
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1){
            cnt++;
            for(int j=1;j<=cnt;j++){
                s[j]++;
            }
        }else{
            cnt=0;
        }
    }
}

算法2

差分

C++ 代码

void df(bool *a,int *s,int n){//s[i]表示长度为i的连续1数量 
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1){
            cnt++;
            s[1]++,s[cnt+1]--;
        }else{
            cnt=0;
        }
    }
    for(int i=2;i<=n;i++){
        s[i]=s[i]+s[i-1];
    }
}

完整代码如下

#include <iostream>
#include <cstring>
using namespace std;
void df(bool *a,int *s,int n){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1){
            cnt++;
            s[1]++,s[cnt+1]--;
        }else{
            cnt=0;
        }
    }
    for(int i=2;i<=n;i++){
        s[i]=s[i]+s[i-1];
    }
}
int main() {
    int n,m,k,s1[40010]={0},s2[40010]={0};
    bool a[40010]={0},b[40010]={0};
    long long ans=0;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    } 
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    df(a,s1,n);
    df(b,s2,m);
    for(int i=1;i<=n;i++){
        if(k%i==0) {//才有可能组成面积为K的矩形
            int j=k/i;
            if(j>m){
                continue;
            }
            ans=ans+s1[i]*s2[j]; 
        } 
    }
    cout<<ans;
    return 0;
}