美团春招编程第一场第三题

美团春招编程第一场第三题

题目

解答

• 思路-暴力解法
  pair中存储从原点到包含当前元素的0,1数量，得到二维数组mat;
  从头到尾遍历尺寸为i*i的矩形，计算完美矩形数量

#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<vector<pair<int, int>>> mat;vector<vector<int>> data;for (int i = 0; i < n; i++) {vector<pair<int, int>> dp(n);vector<int> tmp(n);if (i == 0) {for (int j = 0; j < n; j++) {int in;cin >> in;tmp[j] = in;if (j == 0) {dp[j] = {in == 1 ? 1 : 0, in == 0 ? 1 : 0};} else {dp[j] = {dp[j - 1].first + (in == 1 ? 1 : 0), dp[j - 1].second + (in == 0 ? 1 : 0)};}}} else {for (int j = 0; j < n; j++) {int in;cin >> in;tmp[j] = in;if (j == 0) dp[j] = {in == 1 ? 1 : 0, in == 0 ? 1 : 0};else dp[j] = {dp[j - 1].first + (in == 1 ? 1 : 0), dp[j - 1].second + (in == 0 ? 1 : 0)};}for (int j = 0; j < n; j++) {dp[j].first += mat[i - 1][j].first;dp[j].second += mat[i - 1][j].second;}}data.emplace_back(tmp);mat.emplace_back(dp);}for (int i = 1; i <= n; i++) {if (i == 1) {cout << 0 << endl;continue;} else {int ret = 0;for (int k = 0; k <= n - i; k++) {for (int p = 0; p <= n - i; p++) {if(k == 0 && p == 0) {if(mat[k+i-1][p+i-1].first == mat[k+i-1][p+i-1].second) ++ret;}else if(p == 0){if(mat[k+i-1][p+i-1].first - mat[k-1][p+i-1].first  == mat[k+i-1][p+i-1].second - mat[k-1][p+i-1].second ){ret++;	}}else if( k == 0){if(mat[k+i-1][p+i-1].first - mat[k+i-1][p-1].first  == mat[k+i-1][p+i-1].second - mat[k+i-1][p-1].second ){ret++;	}}else {if(mat[k+i-1][p+i-1].first - mat[k+i-1][p-1].first - mat[k-1][p+i-1].first + mat[k-1][p-1].first == mat[k+i-1][p+i-1].second - mat[k+i-1][p-1].second - mat[k-1][p+i-1].second + mat[k-1][p-1].second){ret++;	}}}}cout << ret << endl;}}return 0;
}
// 64 位输出请用 printf("%lld")