子矩形计数（多少个面积为k的全1子矩阵）【思维，两个一维数组相乘得到矩阵，计算一维数组中长度为x的全1子段】

3617. 子矩形计数（多少个面积为k的全1子矩阵）

输入样例1：

3 3 2
1 0 1
1 1 1

输出样例1：

4

输入样例2：

3 5 4
1 1 1
1 1 1 1 1

输出样例2：

14

#include 
using namespace std;
#define int long long int
const int N=40005;
int n,m,T,k;
bool a[N],b[N];
int fun(bool v[],int x,int len){
    int res=0;//v数组重有几个长度为x的全1子段
    int cnt=0;//一段连续的1的个数 可以得到cnt-x+1个长度为x的全1子段
    for(int i=1;ilen;i++){
        if(v[i])cnt++;
        else{
            if(cnt>=x)res+=cnt-x+1;
            cnt=0;
        }
    }
    if(cnt>=x)res+=cnt-x+1;//可能最后一串1碰不到0
    return res;
}
signed main(){
    cin>>n>>m>>k;//选出的数最多划分为 k组
    for(int i=1;in;i++)cin>>a[i];
    for(int i=1;im;i++)cin>>b[i];
    int res=0;
    for(int w=1;wn&&wk;w++){//w遍历到k是会超时的
        if(k%w==0){
            int h=k/w;
            int x=fun(a,w,n);
            int y=fun(b,h,m);
            res+=x*y;//xy数量级都是N数量级的，4e4 * 4e4 过了1e9爆int
        }
    }
    coutres;
   
    return 0;
}

真的把矩阵计算出来，在矩阵里面找子矩阵必然超时

#include 
using namespace std;
// #define int long long int
const int N=40005;
int n,m,T,k;
int a[N],b[N],c[N][N];
signed main(){
    cin>>n>>m>>k;//选出的数最多划分为 k组
    for(int i=1;in;i++)cin>>a[i];
    for(int i=1;im;i++)cin>>b[i];
    for(int i=1;in;i++){
        for(int j=1;jm;j++){
            c[i][j]=a[i]*b[j];
        }
    }
    for(int i=1;in;i++){
        for(int j=1;jm;j++){
            c[i][j]=a[i]*b[j];
        }
    }
    大小为k
    for(int i=1;in;i++){
        for(int j=1;jm;j++){//左上端点
            for(int w=1;wk&&c[i][j]&&k%w==0;w++){
                int h=k/w;
                if(i+w-1n&&j+h-1m){
                    
                }
            }
        }
    }
   
    return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: PyTorch深度学习开发医学影像端到端判别项目

download：PyTorch深度学习开发医学影像端到端判别项目 ChatGPT：开启人机交互新时代的AI语言模型 在现代科技快速发展的今天，人工智能已经成为了一个备受关注的话题，而ChatGPT作为一种基于自然语言处理技术的AI语言模型，在人机交互方面扮演…