[Blue Bridge Cup] C++ Group B Statistical Submatrix

Hits: 0

Give a like if it helps 👍

brute force method

ideas

  • Directly use the two-digit prefix sum to calculate the sum in the area
  • Traverse all areas that meet the conditions, such as length and width ( 1*1, 1*2…)

#include<bits/stdc++.h> 
using namespace std;
const int N=2000;
int n,m,k;
int a[N][N];
/*
3 4 10
2 2 3 4
5 6 7 8
9 10 11 12
*/
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }   
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }   
        //cout<<endl;
    }
    //cout<<endl;
//  for(int i=1;i<=n;i++)
//  {
//      for(int j=1;j<=m;j++)
//      {
//          cout<<a[i][j]<<" ";
//      }   
//      cout<<endl;
//  }

    int res=0;

    for ( int x= 1 ;x<=n;x++) //Enumerate xy, even if the upper left corner and the lower right corner are combined
    {
        for(int y=1;y<=m;y++)
        {
            for ( int i= 1 ;i<=n;i++) //When the area is fixed, find all the solutions
            {
                for(int j=1;j<=m;j++)
                {
                    int sum1=a[i+x-1][j+y-1]-a[x+i-1][j-1]-a[i-1][j+y-1]+a[i-1][j-1];
                    if(sum1<=k)
                    {
                        //cout<<x<<" "<<y<<endl;
                        res++; 
                    }

                }   

            }
        }   

    }
    printf("%d",res);

    return 0;
}

Double pointer optimization (y total method)

ideas

  • Because the time complexity of the brute force method is O(n^4), it will time out, so there must be one less loop
  • You can use the method of double pointers to traverse each element in the upper and lower boundaries determined.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 510;

int n, m, K;
int s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &K);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &s[i][j]);
            s[i][j] += s[i - 1 ][j]; //Note that this is the data, the y-axis is not summed
        }


    LL res = 0 ;
     for ( int i = 1 ; i <= n; i ++ ) //upper bound i 
        for ( int j = i; j <= n; j ++ ) //lower bound j 
            for ( int l = 1 , r = 1 , sum = 0 ; r <= m; r ++ ) //left boundary l and right boundary r
            {
                sum += s[j][r] - s[i - 1 ][r]; //Add one to the right border, sum must add the element 
                //After the border is added, the left border must also look to the right Add, otherwise sum will be greater than k 
                while (sum > K)
                {
                    sum -= s[j][l] - s[i - 1][l];
                    l ++ ;
                }
                res += r - l + 1 ; //The number of elements in the interval is the number of qualified intervals 
                //For example, the upper and lower intervals are fixed (i=1, j=3), and the left and right intervals are also fixed ( l=2,j=5), then the interval that satisfies the condition is 4 
                //The upper right corner is {{EJS0}}, the lower left corner is {{EJS1}}, {{EJS2}} ,{{EJS3}},{{EJS4}}, there are pictures below
            }

    printf("%lld\n", res);
    return 0;
}

You may also like...

Leave a Reply

Your email address will not be published.