Learn programming with Lao Ma by “leveling up and battling”!
- Involves examination: Computer Society Programming Ability Level Certification (GESP)
- Event content: Provides real exam questions of different levels for students to practice
- Preparation advice: Choose corresponding questions based on your preparation level
- Additional value: Can be used as preparation training for whitelist competitions
Day 20: GESP Level 1 2025.03_Rounding
[Submit]
https://www.luogu.com.cn/problem/B4258
[Problem Description]
Rounding is a common approximation method. Now, given integers, you need to round each integer to the nearest ten. For example, after rounding becomes , after rounding becomes .
[Input Description]
Two lines in total, the first line contains an integer , indicating the number of integers to be input next.
Next lines, each line contains one integer , representing the integer to be rounded.
[Output Description]
One line for each integer, representing the result after rounding, with integers separated by spaces.
[Sample Input 1]
5
43
58
25
67
90
[Sample Output 1]
40
60
30
70
90
[Data Range]
For all test points, it is guaranteed that , .
Reference Answer:
/*
* [GESP202503 Level 1] Rounding
* https://www.luogu.com.cn/problem/B4258
*/
# include
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
x = int(1.0 * x / 10 + 0.5);
cout << x * 10 << endl;
}
return 0;
}
Day 20: GESP Level 2 2024.12_Digit Sum
[Submit]
https://www.luogu.com.cn/problem/B4065
[Problem Description]
Little Yang has positive integers, and he wants to know the maximum digit sum among these positive integers.
“Digit sum” refers to the sum of all digits in a number.
For example:
For the number , its digits are , , , , . Adding these digits gives:
Thus, the digit sum of is .
[Input Description]
The first line contains a positive integer , representing the number of positive integers.
Next lines, each line contains one positive integer.
[Output Description]
Output the maximum digit sum of these positive integers.
[Sample Input 1]
3
16
81
10
[Sample Output 1]
9
[Data Range]
For all data, it is guaranteed that , each positive integer does not exceed .
Reference Answer:
/*
* [GESP202412 Level 2] Digit Sum
* https://www.luogu.com.cn/problem/B4065
*/
# include
using namespace std;
int main()
{
int n, max_ = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
long long x;
cin >> x;
int sum = 0;
while (x > 0)
{
sum += x % 10;
x = x / 10;
}
if (sum > max_)
{
max_ = sum;
}
}
cout << max_;
return 0;
}
Day 20: GESP Level 3 2025.06_Parity Check
[Submit]
https://www.luogu.com.cn/problem/B4358
[Problem Description]
Data may be corrupted during transmission, so the receiver usually checks whether the transmitted data is correct. Parity check is one of the classic methods of verification.
Given non-negative integers representing the transmitted data, the parity code depends on the parity of the total number of 1s in the binary representation of these integers. If there are an odd number of 1s, the parity code is ; otherwise, the parity code is . Can you calculate the parity code for these integers?
[Input Description]
The first line contains a positive integer , indicating the amount of transmitted data.
The second line contains non-negative integers , representing the transmitted data.
[Output Description]
Output one line with two integers separated by a space:
The first integer represents the total number of 1s in binary;
The second integer represents the parity code (0 or 1).
[Sample Input 1]
4
71 69 83 80
[Sample Output 1]
13 1
[Sample Input 2]
6
1 2 4 8 16 32
[Sample Output 2]
6 0
[Data Range]
For all test points, it is guaranteed that , .
Reference Answer:
/*
* [GESP202506 Level 3] Parity Check
* https://www.luogu.com.cn/problem/B4358
*/
#include
using namespace std;
int main()
{
int n, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
while (x > 0)
{
if (x % 2 == 1)
{
cnt++;
}
x = x / 2;
}
}
cout << cnt << " " << cnt % 2;
return 0;
}
Day 20: GESP Level 4 2024.06_Black and White Squares
[Submit]
https://www.luogu.com.cn/problem/B4005
[Problem Description]
Little Yang has a grid of rows and columns, where each cell is either white or black.
A subrectangle in the grid is considered balanced if the number of black cells equals the number of white cells.
Little Yang wants to know the size of the largest balanced subrectangle.
[Input Description]
The first line contains two positive integers , as described in the problem statement.
Next lines, each line contains a string of length , representing the color of the cells in the grid. If it is , it corresponds to a white cell; otherwise, it is black.
[Output Description]
Output an integer representing the number of cells in the largest balanced subrectangle. If none exists, output .
[Sample Input 1]
4 5
00000
01111
00011
00011
[Sample Output 1]
16
[Sample Explanation]
For Sample 1, assuming () represents the cell in the row and the column, the four vertices of the largest balanced subrectangle are , , , .
[Data Range]
For all data, it is guaranteed that .
Reference Answer:
/*
* [GESP202406 Level 4] Black and White Squares
* https://www.luogu.com.cn/problem/B4005
*/
#include
using namespace std;
char arr[11][11] = { 0 };
int check(int x1, int y1, int x2, int y2)
{
int a = 0, b = 0, cnt = 0;
for (int i = x1; i <= x2; i++)
{
for (int j = y1; j <= y2; j++)
{
if (arr[i][j] == '0')
{
a += 1;
}
else
{
b += 1;
}
cnt += 1;
}
}
return a == b ? cnt : -1;
}
int main()
{
int n, m, max_ = 0;
cin >> n >> m;
// Read data
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> arr[i][j];
}
}
// Process data
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// Top left corner at (i,j)
for (int p = i; p <= n; p++)
{
for (int q = j; q <= m; q++)
{
// Bottom right corner (p,q)
int k = check(i, j, p, q);
if (k > max_)
{
max_ = k;
}
}
}
}
}
cout << max_;
return 0;
}
Day 20: GESP Level 5 2024.06_Checkered Squares
[Submit]
https://www.luogu.com.cn/problem/P10719
[Problem Description]
Little Yang has a grid of rows and columns, where each cell is either white or black.
Little Yang wants to know the size of the smallest subrectangle that contains at least black cells.
[Input Description]
The first line contains three positive integers , as described in the problem statement.
Next lines, each line contains a string of length , representing the color of the cells in the grid. If it is , it corresponds to a white cell; otherwise, it is black.
[Output Description]
Output an integer representing the number of cells in the smallest subrectangle that contains at least black cells. If none exists, output .
[Sample Input 1]
4 5 5
00000
01111
00011
00011
[Sample Output 1]
6
[Sample Explanation]
For the sample, assuming () represents the cell in the row and the column, the four vertices of the smallest subrectangle containing at least black cells are , , , , totaling cells.
[Data Range]
For all data, it is guaranteed that , .
Reference Answer:
The problem can be transformed into finding the minimum submatrix with an element sum greater than or equal to . We process the prefix sum of the matrix, then brute force enumerate the top left and bottom right corners of the submatrix. If the sum of the current matrix is greater than or equal to , update the minimum value. Remember to check for non-existence.
/*
* GESP202406 Level 5 Checkered Squares
* https://www.luogu.com.cn/problem/P10719
*/
#include
#include
using namespace std;
const int N = 102;
int a[N][N];
int s[N][N];
int main()
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char c;
cin >> c;
a[i][j] = c - '0';
// Prefix sum of the matrix
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
int mn = 0x0fffffff;
for (int i1 = 1; i1 <= n; i1++)
{
for (int j1 = 1; j1 <= m; j1++)
{
for (int i2 = i1; i2 <= n; i2++)
{
for (int j2 = j1; j2 <= m; j2++)
{
// Sum of the submatrix from s[i1][j1] to s[i2][j2]
if (s[i2][j2] - s[i1 - 1][j2] - s[i2][j1 - 1] + s[i1 - 1][j1 - 1] >= k)
{
mn = min(mn, (i2 - i1 + 1) * (j2 - j1 + 1));
}
}
}
}
}
if (mn != 0x0fffffff)
{
cout << mn;
}
else
{
cout << 0;
}
return 0;
}
Day 20: Openjudge2.6.1768_Maximum Submatrix
[Submit]
http://noi.openjudge.cn/ch0206/1768/
[Description]
The size of a matrix is defined as the sum of all its elements. Given a matrix, your task is to find the largest non-empty (at least 1 * 1) submatrix.
For example, the following 4 * 4 matrix
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
has the maximum submatrix
9 2
-4 1
-1 8
The size of this submatrix is 15.
[Input]
The input is an N * N matrix. The first line gives . In the following lines, the N integers of the matrix are given from left to right, row by row (space-separated).
[Output]
Output the size of the maximum submatrix.
[Sample Input]
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
[Sample Output]
15
[Reference Program]
#include
#include
#include
using namespace std;
const int SIZE = 100;
int matrix[SIZE + 1][SIZE + 1];
// Use Kadane's algorithm to calculate the maximum subarray sum of a one-dimensional array.
int maxSubArray(vector& nums)
{
int max_current = nums[0];
int max_global = nums[0];
for (int i = 1; i < nums.size(); ++i)
{
max_current = max(nums[i], max_current + nums[i]);
max_global = max(max_global, max_current);
}
return max_global;
}
// Process the two-dimensional matrix.
// By double looping through all possible row ranges (top to bottom),
// store the sum of each column between the top and bottom rows in a one-dimensional array dp.
int maxSubMatrix(int N)
{
int max_sum = INT_MIN;
for (int top = 0; top < N; top++)
{
vector dp(N, 0);
for (int bottom = top; bottom < N; bottom++)
{
for (int col = 0; col < N; ++col)
{
dp[col] += matrix[bottom][col];
}
int current_max = maxSubArray(dp);
if (current_max > max_sum)
{
max_sum = current_max;
}
}
}
return max_sum;
}
// Transform the two-dimensional problem into a one-dimensional problem, efficiently solving the maximum submatrix sum problem using dynamic programming and Kadane's algorithm.
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> matrix[i][j];
}
}
cout << maxSubMatrix(N) << endl;
return 0;
}Youth Programming Competition Exchange
The “Youth Programming Competition Exchange Group” has been established (suitable for youth aged 6 to 18). Add the assistant on WeChat to invite everyone into the learning group. After joining, everyone can participate in regularly organized 21-day problem-solving check-ins, level exam assessments, Ministry of Education whitelist competition coaching, and youth programming team competitions.
