小美的平衡矩阵-美团2024年春招第一场笔试

本文主要是介绍小美的平衡矩阵-美团2024年春招第一场笔试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：暴力枚举所有的i*i矩阵，复杂度为O（），至于矩阵中0和1的数量，使用二维前缀和数组求得。

解释下构造前缀和数组语句：sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];作用

求以（i,j）左上角，（k,l）右下角的的前缀和语句：

sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1]

读者自行理解。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[205][205],sum[205][205];
int main()
{ios::sync_with_stdio(0),cin.tie(0);int n,i,j,k,l,len,cnt=0;char c;cin>>n;for(i=1; i<=n; i++)for(j=1; j<=n; j++)cin>>c,a[i][j]=c-'0';for(i=1; i<=n; i++)/**< 二维数组求前缀和,统计1的个数 */for(j=1; j<=n; j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];for(len=1; len<=n; len++)/**< len矩阵的大小，len为奇数时不可能满足条件 */{cnt=0;for(i=1; i<=n-len+1; i++)/**< i,j矩阵左上角坐标，k，l右下角坐标 */for(j=1; j<=n-len+1; j++){k=i+len-1,l=j+len-1;if((sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1])*2==len*len)cnt++;}cout<<cnt<<endl;}return 0;
}

这篇关于小美的平衡矩阵-美团2024年春招第一场笔试的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---