GESP C++ Level 4 real questions for June 2024. This problem mainly tests two-dimensional arrays, multiple loop operations, and even the prefix sum concept. The brute force difficulty is not high, but optimizing with prefix sums requires some thought, with an overall difficulty rating of ⭐⭐★☆☆. This problem is rated as<span>Popular-</span>.
-
GESP Level 1 Practice Question List
-
GESP Level 1 Real Question List
-
GESP Level 2 Practice Question List
-
GESP Level 2 Real Question List
-
GESP Level 3 Practice Question List
-
GESP Level 3 Real Question List
-
GESP Level 4 Practice Question List
-
GESP Level 4 Real Question List
-
GESP Level 1-5 Syllabus Analysis
luogu-B4005 [GESP202406 Level 4] Black and White Squares
Problem Requirements
Problem Description
Little Yang has a row column grid, where each cell is either white or black. A sub-rectangle in the grid is considered balanced if and only if the number of black cells is equal to the number of white cells. Little Yang wants to know the maximum number of cells in the largest balanced sub-rectangle.
Input Format
The first line contains two positive integers, as described in the problem statement.
Following that, lines, each containing a string of length , represent the color of the cells in the grid for each row; if it is , the corresponding cell is white, otherwise it is black.
Output Format
Output a single integer representing the number of cells in the largest balanced sub-rectangle; if none exists, output .
Input/Output Example #1
Input #1
4 5
00000
01111
00011
00011
Output #1
16
Explanation/Hint
[Sample Explanation]:
For the sample, assuming represents the row and the column, the four vertices of the largest balanced sub-rectangle are .
[Data Range]:
For all data, it is guaranteed that there is .
Problem Analysis
Problem Analysis
- The problem requires finding the largest balanced sub-rectangle in a black and white square matrix
- A balanced sub-rectangle is defined as a rectangular area where the number of black cells equals the number of white cells
- We need to calculate how many cells this largest balanced sub-rectangle contains
Solution Approach
Method 1: Brute Force Enumeration
- Enumerate all possible sub-rectangles (determined by the coordinates of the top-left and bottom-right corners) using four nested loops
- Two nested loops to enumerate all possible top-left corner coordinates of the sub-rectangles
- Two nested loops to enumerate all possible bottom-right corner coordinates of the sub-rectangles
- For each sub-rectangle, count the number of black and white cells; the counting method is:
- Traverse each cell within the sub-rectangle, assuming white cells are -1 and black cells are 1
- The sum of all cells must be zero for the sub-rectangle to be balanced
- If the sub-rectangle is balanced, update the maximum area; the area formula is
- Time Complexity:, we need to traverse each cell as the top-left and bottom-right corners, and for each sub-rectangle, we need time to count the black and white cells, which is approximately level
- Space Complexity:, we only need to store the original matrix
Method 2: Prefix Sum Optimization
Prefix sum concept:
- Mark white cells as -1 and black cells as 1
- Construct a two-dimensional prefix sum array , representing the sum of all cell values from to
- For any sub-rectangle (x1,y1) to (x2,y2), the sum of all cells can be quickly calculated using the prefix sum:
- If the sum is zero, it indicates that the sub-rectangle is balanced
Optimized algorithm steps:
- Preprocess to construct the two-dimensional prefix sum array
- Enumerate the coordinates of the top-left and bottom-right corners of the sub-rectangles and
- Use the prefix sum formula to calculate the difference in the number of black and white cells in the sub-rectangle
- If the difference is zero, calculate the area and update the maximum value
Time Complexity Analysis:
- Constructing the prefix sum array requires
- Enumerating all possible sub-rectangles requires
- Calculating the sum for each sub-rectangle only requires
- The total time complexity is, which is approximately level
Space Complexity Analysis:
- Requires an additional two-dimensional array to store the prefix sum
- Space complexity is
The prefix sum method effectively reduces the time complexity from to level.
Example Code
Method 1: Brute Force Loop
#include <cmath>
#include <iostream>
#include <string>
// Store the black and white square matrix, -1 represents white, 1 represents black
int ary[15][15];
// Store the prefix sum array
int sum[15][15];
// Check if the specified rectangular area is balanced
// Parameters: f_row,f_col top-left coordinates, l_row,l_col bottom-right coordinates
bool check(int f_row, int f_col, int l_row, int l_col) {
int sum = 0;
// Traverse the rectangular area
for (int i = f_row; i <= l_row; i++) {
for (int j = f_col; j <= l_col; j++) {
sum += ary[i][j];
}
}
// If the sum is zero, it means the number of black and white squares is equal
return sum == 0 ? true : false;
}
int main() {
// Read the size of the matrix
int n, m;
std::cin >> n >> m;
// Read the matrix data and calculate the prefix sum
for (int i = 1; i <= n; i++) {
std::string r_str;
std::cin >> r_str;
for (int j = 1; j <= m; j++) {
// Convert 0 to -1 (white), keep 1 unchanged (black)
ary[i][j] = r_str[j - 1] == '0' ? -1 : 1;
// Calculate the two-dimensional prefix sum
sum[i][j] =
sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ary[i][j];
}
}
// Enumerate all possible rectangular areas
int max_area = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = i; k <= n; k++) {
for (int l = j; l <= m; l++) {
// Check if the current rectangle is balanced
if (check(i, j, k, l)) {
// Calculate the area of the rectangle and update the maximum value
int area = (k - i + 1) * (l - j + 1);
max_area = std::max(max_area, area);
}
}
}
}
}
// Output the result
std::cout << max_area;
return 0;
}
Method 2: Prefix Sum Optimization
#include <cmath>
#include <iostream>
#include <string>
// Store the black and white square matrix, -1 represents white, 1 represents black
int ary[15][15];
// Store the two-dimensional prefix sum array
int sum[15][15];
int main() {
// Read the size of the matrix n rows m columns
int n, m;
std::cin >> n >> m;
// Read the matrix data and calculate the prefix sum
for (int i = 1; i <= n; i++) {
std::string r_str;
std::cin >> r_str;
for (int j = 1; j <= m; j++) {
// Convert 0 to -1 (white), keep 1 unchanged (black)
ary[i][j] = r_str[j - 1] == '0' ? -1 : 1;
// Calculate the two-dimensional prefix sum
sum[i][j] =
sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ary[i][j];
}
}
// Record the maximum balanced rectangle area
int max_area = 0;
// Enumerate all possible rectangular areas
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = i; k <= n; k++) {
for (int l = j; l <= m; l++) {
// Use prefix sum to calculate the difference in black and white squares in the current rectangular area
int area_sum = sum[k][l] - sum[i - 1][l] - sum[k][j - 1] +
sum[i - 1][j - 1];
// If the difference is zero, it means the number of black and white squares is equal
if (area_sum == 0) {
// Calculate the area of the current balanced rectangle
int area = (k - i + 1) * (l - j + 1);
// Update the maximum area
max_area = std::max(max_area, area);
}
}
}
}
}
// Output the result
std::cout << max_area;
return 0;
}
For detailed GESP syllabus, real question explanations, knowledge expansion, and practice lists, see:
[Pinned][GESP] C++ Certification Learning Resource Summary
“luogu-” series problems can be evaluated online in the Luogu Problem Bank.
“bcqm-” series problems can be evaluated online in the Programming Enlightenment Problem Bank.