n≤200,因此可以在O(n3)范围内求解
快速求一个矩形区域内的和:使用二维前缀和预处理
最终计算答案的时候,第一层循环枚举矩形长度len,第二,三层循环分别枚举矩形的左上角的端点(x,y)
对应右下角的端点则为(x+len−1,y+len−1)
小美拿到了一个n×m的矩阵,其中每个元素是0或者1。
小美认为一个矩形区域是完美的,当且仅当该区域内0的数量恰好等于1的数量。现在,小美希望你回答有多少个i×i的完美矩形区域。你需要回答1≤i≤n的所有答案
第一行输入一个正整数n,代表矩阵大小
接下来的n行,每行输入一个长度为n的01串,用来表示矩阵 1≤n≤200
输出n行,第i行输出i×i的完美矩形区域的数量
输入
4
1010
0101
1100
0011
输出
0
7
0
1