Codeforces Round #626 （Div. 2） B. Count Subrectangles

题目连接：https://codeforces.com/contest/1323/problem/B

题意：给一个大小为n的a数组，一个大小为m的b数组，c数组是二维数组c[i][j]=a[i]*b[j]，问面积为k的矩形有几个。

题解：先把k的所有因子存入一个数组里，然后遍历因子，表示在a数组有 i 个连续的1，那么如果在b数组里有 k/i 个连续的1，形成的矩形面积就是k（线代的矩阵乘法自己脑补一下吧），计算出a数组中符合条件的个数乘以b数组中符合条件的个数，然后把每个因子下的都加起来就是答案。

 1 #include<bits/stdc++.h>

 2 #define ll long long

 3 using namespace std;

 4

 5 int a[100100],b[100100];

 6 int c[100100];

 7

 8 int main()

 9 {

10     int n,m,k;

11     cin>>n>>m>>k;

12     for(int i=0;i<n;i++) cin>>a[i];

13     for(int i=0;i<m;i++) cin>>b[i];

14     int p=0;

15     for(int i=1;i*i<=k;i++){

16         if(k%i==0){

17             c[p++]=i;

18             if(i==k/i) continue;

19             c[p++]=k/i;

20         }

21     }

22     ll ans=0;

23     for(int i=0;i<p;i++){

24         int cnt=0;

25         ll x=0,y=0;

26         for(int j=0;j<n;j++){

27             if(a[j]==1) cnt++;

28             else cnt=0;

29             if(cnt==c[i]) cnt--,x++;

30         }

31         cnt=0;

32         for(int j=0;j<m;j++){

33             if(b[j]==1) cnt++;

34             else cnt=0;

35             if(cnt==k/c[i]) cnt--,y++;

36         }

37         ans=ans+x*y;

38     }

39     cout<<ans<<endl;

40     return 0;

41 }

巴特西

Codeforces Round #626 （Div. 2） B. Count Subrectangles

最新文章

热门文章