网站开发的技术风险,如何建网站做传奇网友,辽宁建设工程信息网备案,公司年会视频制作模板小美的平衡矩阵 写在前面: 本博客只是一种解题思路的提供。
小美的平衡矩阵
题目描述#xff1a;
小美拿到了一个n*n 的矩阵#xff0c;其中每个元素是 0 或者 1。 小美认为一个矩形区域是完美的#xff0c;当且仅当该区域内 0 的数量恰好等于 1 的数量。 现在#xf…小美的平衡矩阵 写在前面: 本博客只是一种解题思路的提供。
小美的平衡矩阵
题目描述
小美拿到了一个n*n 的矩阵其中每个元素是 0 或者 1。 小美认为一个矩形区域是完美的当且仅当该区域内 0 的数量恰好等于 1 的数量。 现在小美希望你回答有多少个i*i的完美矩形区域。你需要回答1in的所有答案。
输入描述
第一行输入一个正整数n代表矩阵大小。 接下来的n行每行输入一个长度为n的01 串用来表示矩阵。
输出描述
输出n行第i行输出的I*I 完美矩形区域的数量。
示例 1
输入
4
1010
0101
1100
0011输出
0
7
0
1思路 符合条件的矩阵的边一定是偶数只有偶数才能保证 0和1的数量相等 确定一个矩阵只需要确定这个矩阵的四个顶点中的一个和边长m,这里选择右下角的顶点 a r r [ i ] [ k ] arr[i][k] arr[i][k] 记录了原始输入的 n ∗ n n*n n∗n的矩阵 d p [ m ] [ i ] [ k ] dp[m][i][k] dp[m][i][k] 的含义是 当边长为 m 时 , 右下角为 a r r [ i ] [ k ] 时的矩阵内数字和 当边长为m时,右下角为arr[i][k]时的矩阵内数字和 当边长为m时,右下角为arr[i][k]时的矩阵内数字和 当矩阵内和为矩阵元素个数一半时他是平衡矩阵。也就是说 当 m 2 2 d p [ m ] [ i ] [ k ] 时 \frac{m^2}{2} dp[m][i][k]时 2m2dp[m][i][k]时 这个矩阵是平衡矩阵
这里放一个 d p [ i ] [ k ] dp[i][k] dp[i][k]的版本此时 d p [ i ] [ k ] dp[i][k] dp[i][k]的含义为以 a r r [ 1 ] [ 1 ] arr[1][1] arr[1][1]为左上元素 a r r [ i ] [ k ] arr[i][k] arr[i][k]为右下角元素的这个框内的所有元素和此时的平衡矩阵的个数并不在dp中保存而是作为一个临时变量存储这一点切记。
#includeiostream
#includevector
#includestring
using namespace std;int main(){int N,n,i1,k;// N用于控制输入,n用于控制输出,i和k用于访问数组的元素cinN;string s;// 用于记录输入的01串n N;vectorvectorint arr(N1,vectorint(N1));vectorvectorint dp(N1,vectorint(N1));while(N--){k 1;while(kn){cins;for(char ch:s){// 遍历01串中的每个字符,将其数字放入arr中arr[i][k] ch-0;}i;}}// 计算dp数组for(i 1;in;i){for(k 1;kn;k){dp[i][k] dp[i-1][k]dp[i][k-1]-dp[i-1][k-1]arr[i][k]; }}for(int m 1;mn;m){// 矩阵边长为1开始遍历,直到边长为nint ans 0;if(m%20){// 只有边长为偶数的矩阵内才有可能使得 0和1的数目相等,保证可能存在平衡矩阵for(i 1;in;i){for(k 1;kn;k){if(imkm){unsigned long long num dp[i][k]-dp[i-m][k]-dp[i][k-m]dp[i-m][k-m];if(numm*m/2)ans;}}}}coutansendl;}return 0;
}有什么问题欢迎来讨论。 最开始思路 d p [ r ] [ q ] [ i ] [ k ] dp[r][q][i][k] dp[r][q][i][k] 保存 以 a r r [ r ] [ q ] arr[r][q] arr[r][q]为左上角 a r r [ i ] [ k ] arr[i][k] arr[i][k] 为右下角的框内的元素和发现dp的初始化和计算都比较麻烦而且也计算了很多不符合条件的框非正方形框
稍微改进 d p [ m ] [ i ] [ k ] dp[m][i][k] dp[m][i][k] 保存 边长为 m m m时框的右下角为元素 a r r [ i ] [ k ] arr[i][k] arr[i][k]时的这个框内的所有元素和刨除了非正方形的框
最后: d p [ i ] [ k ] dp[i][k] dp[i][k] ,也就是代码版本 注意本程序仅由简单测试主要是提供思路。
