小美的平衡矩阵_

NuyoahToHere

import java.util.*

//二维数组前缀和
public class main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        in.nextLine();
        String[] rect = new String[n];
        for (int i = 0; i < n; i++) {
            rect[i]=in.nextLine();
        }
                //为了便于理解转化为二维数组
        int[][] rectInt = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rectInt[i][j]=rect[i].charAt(j)-'0';
            }
        }
        // 使用 二维 数组的前缀和  之所以 +1 是为了统一 操作, 避免判断边界
        //如果 不用 n+1 而使用 n  则需要手动初始化 第一行和第一列
        //https://www.bilibili.com/video/BV1c64y1p7Z1/?spm_id_from=333.337.search-card.all.click&vd_source=deb80297a2c89a7c09425884c13200ac  参考视频
        int[][] preSum = new int[n + 1][n + 1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=n ; j++) {
                preSum[i][j]=preSum[i][j-1]+preSum[i-1][j]-preSum[i-1][j-1]+rectInt[i-1][j-1];
                //直接访问字符串更快一点
                //preSum[i][j]=preSum[i][j-1]+preSum[i-1][j]-preSum[i-1][j-1]+(rect[i-1].charAt(j-1)-'0');
            }
        }
        for (int k = 1; k <= n; k++) {  //控制矩形大小
            if (k%2!=0){  // 奇数个元素 0 和 1 的数量不可能相等
                System.out.println(0);
                continue;
            }
            int res=0;
            int target=(k*k)/2;
            for (int i = k; i <=n ; i++) {
                for (int j = k; j <=n; j++) {
                    //计算每一个小正方形的和
                    int sum=preSum[i][j]-preSum[i-k][j]-preSum[i][j-k]+preSum[i-k][j-k];
                    if (sum==target){
                        res++;
                    }
                }
            }
            System.out.println(res);
        }
    }
}

发表于 2024-03-16 23:40:45 回复(1)

在喝茶的芭乐很想回家

#include <iostream>
#include <vector>
using namespace std;

int main() {

//得到矩阵大小
int n;
cin >> n;

//得到原始矩阵
vector<vector<int>> data(n + 1,vector<int>(n + 1));
string str;
for(int i = 1 ; i<= n;i++)
{
cin >> str;
for(int j = 0 ; j< str.size();j++)
{
if(str[j] == '1')
data[i][j+1] = 1;
else
data[i][j+1] = 0;
}
}

//得到前缀和矩阵
vector<vector<int>> pre_data(n + 1,vector<int>(n + 1));
for(int i = 1 ; i <= n;i++)
{
for(int j = 1 ; j <= n;j++)
{
pre_data[i][j] = pre_data[i][j - 1] + pre_data[i - 1][j] - pre_data[i - 1][j - 1] + data[i][j];
}
}

//输出完美矩形
for(int wan = 1 ; wan <= n; wan++)
{
int count = 0;
for(int i = 1 ; i <= n - wan + 1;i++)
{
for(int j = 1 ; j <= n - wan + 1;j++)
{
int sum = pre_da*** - 1][j + wan - 1] - pre_da*** - 1][j - 1] - pre_data[i - 1][j + wan - 1] + pre_data[i - 1][j - 1];
if(sum*2 == wan*wan) count++;
}
}
cout << count << endl;
}

}

发表于 2024-04-22 11:07:53 回复(0)

C/C++

真正的loser

#include <iostream>
#include <vector>
using namespace std;

void perfectMatrix(int n, vector<string>& matrix, vector<int>& result) {
    vector<vector<int>> preSum(n + 1, vector<int>(n + 1, 0));
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = 0; j < n; j++) {
            if(matrix[i][j] == '1') sum++;
            preSum[i + 1][j + 1] = sum + preSum[i][j + 1];
        }
    }
    for(int k = 1; k <= n; k++) {
        if(k % 2 == 1) result[k] = 0;
        else {
            int count = 0;
            for(int i = 1; i + k - 1 <= n; i++) {
                for(int j = 1; j + k - 1 <= n; j++) {
                    int oneSum = preSum[i + k - 1][j + k - 1] - preSum[i + k - 1][j - 1] - preSum[i - 1][j + k - 1] + preSum[i - 1][j - 1];
                    if(oneSum == (k * k) / 2) count++;
                }
            }
            result[k] = count;
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<string> matrix(n);
    for(int i = 0; i < n; i++) {
        cin >> matrix[i];
    }
    vector<int> result(n + 1, 0);
    perfectMatrix(n, matrix, result);
    for(int i = 1; i < result.size(); i++) {
        cout << result[i] <<endl;
    }
}

前缀和，时间复杂度O(n^3)，计算二维前缀和时要注意，不能直接全加一起直接更新，刚开始算错了

编辑于 2024-03-23 03:56:28 回复(0)

牛萧犇

n = int(input())
li = []
for _ in range(n):
    li.append(input())
sm = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        sm[i][j] = sm[i - 1][j] + sm[i][j - 1] + int(li[i - 1][j - 1]) - sm[i - 1][j - 1]

for k in range(1, n + 1):
    t = k * k
    if t % 2:
        print(0)
        continue
    cnt = 0
    for i in range(k, n + 1):
        for j in range(k, n + 1):
            if sm[i][j] - sm[i - k][j] - sm[i][j - k] + sm[i - k][j - k] == t // 2:
                cnt += 1
    print(cnt)

编辑于 2024-03-13 21:13:14 回复(2)

再快点啊啊啊

//利用前缀和，没优化但过了
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] nums = new int[n][n], sum = new int[n][n];
        char[] chars;
        for (int i = 0; i < n; i++) {
            chars = in.next().toCharArray();
            for (int j = 0; j < n; j++) {
                nums[i][j] = chars[j] - '0';
                if ( i != 0 &&
                        j != 0)sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] +
                                               nums[i][j];
                else if (i != 0)sum[i][j] = sum[i - 1][j] + nums[i][j];
                else if (j != 0)sum[i][j] = sum[i][j - 1] + nums[i][j];
                else sum[i][j] = nums[i][j];
            }
        }
        int res = 0, tar;
        for (int i = 0; i < n; i++) {

            if (i % 2 == 0) {
                res = 0;
                System.out.println(res);
            } else {
                for (int j = i; j < n; j++) {
                    for (int w = i; w < n; w++) {
                        if (j == i && w == i)tar = sum[j][w];
                        else if (j == i)tar = sum[j][w] - sum[j][w - i - 1];
                        else if (w == i)tar = sum[j][w] - sum[j - i - 1][w];
                        else tar = sum[j][w] - sum[j][w - i - 1] - sum[j - i - 1][w] + sum[j - i - 1][w
                                       - i - 1];
                        if (tar == (i + 1) * (i + 1) / 2)res++;
                    }
                }
                System.out.println(res);
            }
        }



    }
}

发表于 2024-03-12 10:37:08 回复(2)

Python

侯普琳

def count_perfect_matrices(matrix, n):
    prefix_diff = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            current_val = 1 if matrix[i - 1][j - 1] == '1' else -1
            prefix_diff[i][j] = (prefix_diff[i - 1][j] + prefix_diff[i][j - 1] - 
                                 prefix_diff[i - 1][j - 1] + current_val)

    results = []
    for size in range(1, n + 1):
        perfect_count = 0
        for i in range(size, n + 1):
            for j in range(size, n + 1):
                total_diff = (prefix_diff[i][j] - prefix_diff[i - size][j] -
                              prefix_diff[i][j - size] + prefix_diff[i - size][j - size])
                if total_diff == 0:
                    perfect_count += 1
        results.append(perfect_count)
    
    return results

n = int(input().strip())
matrix = [input().strip() for _ in range(n)]

result = count_perfect_matrices(matrix, n)
for count in result:
    print(count)

将0处理为-1，直接前缀和计算

编辑于 2024-04-30 17:33:17 回复(0)

C/C++

stronger_1

#include <iostream>

#include <string>

#include <stdlib.h>

#include <algorithm>

using namespace std;

const int N= 210;

int a[N][N];

int s[N][N];

int main() {

int n;

cin>>n;

string str;

//数组初始化

for(int i=1;i<=n;i++)

{

cin>>str;

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

a[i][j+1]=(char)str[j]-'0';

}

//二位前缀和数组初始化

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

//计算

for(int i=1;i<=n;i++)//i*i矩阵

{

int res=0;

for(int j=i;j<=n;j++)

{

for(int k=i;k<=n;k++)

{

int sum=s[j][k]-s[j-i][k]-s[j][k-i]+s[j-i][k-i];

if(sum*2==i*i) res++;

}

cout<<res<<endl;

}

return 0;

}

编辑于 2024-04-14 13:02:20 回复(1)

C/C++

游过一只鸭

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<vector<int>>num(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            char c;
            cin>>c;
            num[i][j]=c-'0';
            if(i==0&&j==0) continue;
            else if(i==0) num[i][j]+=num[i][j-1];
            else if(j==0) num[i][j]+=num[i-1][j];
            else num[i][j]=num[i][j]+num[i][j-1]+num[i-1][j]-num[i-1][j-1];
        }
    }
    for(int k=1;k<=n;k++){
        if(k%2){
            cout<<0<<endl;
            continue;
        }
        int cnt=0;
        for(int i=k-1;i<n;++i){
            for(int j=k-1;j<n;++j){
                int a=num[i][j];
                if(i-k>=0)a-=num[i-k][j];
                if(j-k>=0)a-=num[i][j-k];
                if(i-k>=0&&j-k>=0)a+=num[i-k][j-k];
                if(a==k*k/2)cnt++;
            }
        }
        cout<<cnt<<endl;
    }
}

发表于 2024-04-03 22:22:03 回复(0)

大厂后端必拿下

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n;
cin >> n;
vector<vector<char> >arr(n, vector<char>(n));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
cin >> arr[i][j];
vector<vector<int> >z_o(n, vector<int>(n, 0)); // 0 1 个数， 1加一，0减一
int len = 1;
while(len <= n){
int cnt = 0;
for(int r = 0; r <= n - len; ++r){
for(int c = 0; c <= n - len; ++c){ // [r][c] : 起点
for(int i = r; i < r + len; ++i)
z_o[r][c] += (arr[i][c+len-1] == '1' ? 1 : -1);
for(int j = c; j < c + len - 1; ++j) // -1原因：右下角位置上面已经加过了
z_o[r][c] += (arr[r+len-1][j] == '1' ? 1 : -1);
if(z_o[r][c] == 0) ++cnt;
}
}
cout << cnt << endl;
++len;
}
return 0;
}

发表于 2024-04-02 17:09:16 回复(0)

让我过一次吧求求了

import java.util.Scanner;

public class Main  {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        int[][] g = new int[n][n];
        for(int i = 0;i<n;i++){
            String s = scan.nextLine();
            for(int j = 0;j<n;j++){
                g[i][j] = s.charAt(j)-'0';
            }
        }
        int[][][] count = new int[2][n+1][n+1];
        count[0][1][1] = g[0][0]^1;
        count[1][1][1] = g[0][0]&1;
        for (int i = 2; i <= n; i++) {
            count[0][1][i] = count[0][1][i-1] + (g[1][i-1]^1);
            count[0][i][1] = count[0][i-1][1] + (g[i-1][1]^1);
            count[1][1][i] = count[1][1][i-1] + (g[1][i-1]&1);
            count[1][i][1] = count[1][i-1][1] + (g[i-1][1]&1);
        }
        for (int i = 1; i <=n;i++) {
            for (int j = 1; j <=n; j++) {
                count[0][i][j] = count[0][i-1][j]+count[0][i][j-1]-count[0][i-1][j-1]+(g[i-1][j-1]^1);
                count[1][i][j] = count[1][i-1][j]+count[1][i][j-1]-count[1][i-1][j-1]+(g[i-1][j-1]&1);
            }
        }
        System.out.println(0);
        for (int k = 2; k <=n; k++) {
            int ans  = 0;
            for (int i = k-1; i < n; i++) {
                for (int j = k-1; j < n; j++) {
                    int c0 = count[0][i+1][j+1]-count[0][i+1-k][j+1]-count[0][i+1][j+1-k]+count[0][i+1-k][j+1-k];
                    int c1 = count[1][i+1][j+1]-count[1][i+1-k][j+1]-count[1][i+1][j+1-k]+count[1][i+1-k][j+1-k];
                    if(c0==c1)ans ++;
                }
            }
            System.out.println(ans);
        }
    }
}
//4
//        1010
//        0101
//        1100
//        0011

发表于 2024-03-22 17:03:05 回复(0)

C/C++

韭菜gaga

计算框内的元素和是否为框内元素个数的一半，是则ans+1

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main(){

    int N,n,i=1,k;
    cin>>N;
    string s;
    n = N;
    vector<vector<int>> arr(N+1,vector<int>(N+1));
    vector<vector<int>> dp(N+1,vector<int>(N+1));
    while(N--){
        k = 1;
        while(k<=n){
            cin>>s;
            for(char ch:s){
                arr[i][k++] = ch-'0';
            }
            ++i;
        }
    }
    // 计算dp数组
    for(i = 1;i<=n;++i){
        for(k = 1;k<=n;++k){
            dp[i][k] = dp[i-1][k]+dp[i][k-1]-dp[i-1][k-1]+arr[i][k];            
        }
    }

    for(int m = 1;m<=n;++m){// 框的边长
        int ans = 0;
        if(m%2==0){
            for(i = 1;i<=n;++i){
                for(k = 1;k<=n;++k){
                    if(i>=m&&k>=m){
                        unsigned long long num = dp[i][k]-dp[i-m][k]-dp[i][k-m]+dp[i-m][k-m];
                        if(num==m*m/2)
                            ++ans;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}

编辑于 2024-03-14 10:54:45 回复(1)

求个offer2024

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           in.nextLine();
           int[][] a = new int[n][n];
           int[][] p = new int[n + 1][n + 1];
           for(int i = 0;i < n;i++){
            String s = in.nextLine();
            for(int j = 0;j < n;j++){
                a[i][j] = s.charAt(j) - '0';
            }
           }
           for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i - 1][j - 1];
            }
           }
           for(int i = 1;i <= n;i++){
            int cnt = 0, target = i * i;
            for(int j = i;j <= n;j++){
                for(int k = i;k <= n;k++){
                    int num = p[j][k] - p[j - i][k] - p[j][k - i] + p[j - i][k - i];
                    if(num * 2 == target) cnt++;
                }
            }
            System.out.println(cnt);
           }
        }
    }
}

编辑于 2024-03-13 13:05:14 回复(0)

小美的平衡矩阵

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题