小美的平衡矩阵
写在前面:
本博客只是一种解题思路的提供。
小美的平衡矩阵
题目描述：
小美拿到了一个n*n 的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个i*i的完美矩形区域。你需要回答1 int N,n,i=1,k;// N用于控制输入,n用于控制输出,i和k用于访问数组的元素 cinN; string s;// 用于记录输入的01串 n = N; vector arr(N+1,vector(N+1)); vector dp(N+1,vector(N+1)); while(N--){ k = 1; while(k cin>s; for(char ch:s){// 遍历01串中的每个字符,将其数字放入arr中 arr[i][k++] = ch-'0'; } ++i; } } // 计算dp数组 for(i = 1;i for(k = 1;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// 矩阵边长为1开始遍历,直到边长为n int ans = 0; if(m%2==0){// 只有边长为偶数的矩阵内才有可能使得 0和1的数目相等,保证可能存在平衡矩阵 for(i = 1;i for(k = 1;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
