Learn programming with Lao Ma by “leveling up and fighting monsters”!
- Involves examination: Computer Society Programming Ability Level Certification (GESP)
- Activity content: Provides real questions of different levels for students to choose and practice
- Preparation advice: Choose corresponding questions based on your preparation level
- Additional value: Can be used as preparation training for whitelist competitions
Day 21: Openjudge1.3.01 A+B Problem
[Submit]
http://noi.openjudge.cn/ch0103/01/
[Description]
In most online question banks, the A+B problem is often the first question to help beginners familiarize themselves with the platform.
The problem description is as follows:
Given two integers and , output the value of . It is guaranteed that , , and the result are all within the integer range.
Please solve this problem.
[Input]
A single line containing two integers, , separated by a single space. and are both within the integer range.
[Output]
A single integer, which is the value of . It is guaranteed that the result is within the integer range.
[Sample Input]
1 2
[Sample Output]
3
[Reference Program]
C Language Version
/*
* 01: A+B Problem
* http://noi.openjudge.cn/ch0103/01/
*/
# include<cstdio>
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d", a + b);
return 0;
}
C++ Language Version
/*
* 01: A+B Problem
* http://noi.openjudge.cn/ch0103/01/
*/
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << a + b;
return 0;
}
Day 21: GESP Level 2 2023.03_Chicken Problem
[Submit]
https://www.luogu.com.cn/problem/B3836
[Problem Description]
The “Chicken Problem” originates from the famous mathematical problem in the ancient Chinese text “Zhang Qiu Jian Suan Jing”. The essence is: “Each rooster costs 5 yuan, each hen costs 3 yuan, and every 3 chicks cost 1 yuan; now with 100 yuan, how many ways can 100 chickens be bought?”
Little Ming loves this story and decided to expand on it using programming: If each rooster costs yuan, each hen costs yuan, and each chick costs 1 yuan; now with yuan, how many ways can chickens be bought?
[Input Description]
Input a line containing five integers, corresponding to the values in the problem description: , , , . It is agreed that .
[Output Description]
Output a line containing an integer , representing the number of ways.
[Sample Input 1]
5 3 3 100 100
[Sample Output 1]
4
[Sample Explanation 1]
This is the “Chicken Problem” described above. The 4 solutions are: 0 roosters, 25 hens, and 75 chicks; 4 roosters, 18 hens, and 78 chicks; 8 roosters, 11 hens, and 81 chicks; 12 roosters, 4 hens, and 84 chicks.
[Sample Input 2]
1 1 1 100 100
[Sample Output 2]
5151
Reference Answer:
/*
* GESP202303 Level 2 Chicken Problem
* https://www.luogu.com.cn/problem/B3836
*/
#include <iostream>
using namespace std;
int main()
{
int x, y, z, n, m, cnt = 0;
cin >> x >> y >> z >> n >> m;
for (int gj = 0; gj * x <= n && gj <= m; gj++)
for (int mj = 0; mj * y + gj * x <= n && mj + gj <= m; mj++)
{
int xj = (n - gj * x - mj * y) * z;
if (gj + mj + xj == m)
cnt++;
}
cout << cnt << endl;
return 0;
}
Day 21: GESP Level 3 2024.06_Shifting
[Submit]
https://www.luogu.com.cn/problem/B4003
[Problem Description]
Little Yang has learned the encryption technique of shifting, where all uppercase letters are shifted back by a fixed number. The shifting process treats the alphabet as a circular loop; for example, when the shift amount is 3, uppercase letter A becomes D, and uppercase letter Z becomes C. Overall, the uppercase alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ is replaced by DEFGHIJKLMNOPQRSTUVWXYZABC.
Note: When the shift amount is a multiple of 26, each uppercase letter will return to its original position after shifting, meaning the uppercase alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ remains unchanged.
[Input Description]
The first line contains a positive integer .
[Output Description]
Output the result of the uppercase alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ after shifting by .
[Sample Input 1]
3
[Sample Output 1]
DEFGHIJKLMNOPQRSTUVWXYZABC
[Sample Explanation]
When the shift amount is 3, uppercase letter A becomes D, and uppercase letter Z becomes C. Overall, the uppercase alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ is replaced by DEFGHIJKLMNOPQRSTUVWXYZABC.
[Data Range]
For all data, it is guaranteed that .
Reference Answer:
/*
* GESP202406 Level 3 Shifting
* https://www.luogu.com.cn/problem/B4003
*/
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
cin >> n;
n = n % 26;
string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string s1 = s.substr(n, 26 - n);
string s2 = s.substr(0, n);
cout << s1 << s2;
}
Day 21: GESP Level 4 2025.03_Land Reclamation
[Submit]
https://www.luogu.com.cn/problem/B4263
[Problem Description]
Little Yang has a large piece of wasteland, which can be represented as a grid of rows and columns.
Little Yang wants to reclaim this wasteland, but some positions contain debris. A piece of wasteland without debris can only be reclaimed if all four adjacent squares (up, down, left, right) do not contain debris.
Little Yang can choose to clear at most one position of debris, turning that position into wasteland. Little Yang wants to know how many pieces of wasteland can be reclaimed at most by clearing at most one position of debris.
[Input Description]
The first line contains two positive integers , meaning as described in the problem.
Each of the following lines contains a string of length consisting only of characters <span>.</span> and <span>#</span>. If it is <span>.</span>, it means that position is wasteland; if it is <span>#</span>, it means that position contains debris.
[Output Description]
Output an integer representing the maximum number of pieces of wasteland that can be reclaimed by clearing at most one position of debris.
[Sample Input 1]
3 5
.....
.#..#
.....
[Sample Output 1]
11
[Sample Explanation]
After removing the debris from the second row, second position from the left:
.....
....#
.....
The first row has pieces of wasteland, the second row has pieces of wasteland, and the third row has pieces of wasteland, all of which can be reclaimed.
[Data Range]
For all data, it is guaranteed that .
Reference Answer:
/*
* [GESP202503 Level 4] Land Reclamation
* https://www.luogu.com.cn/problem/B4263
*/
# include<iostream>
using namespace std;
char arr[1005][1005];
int n, m;
int check(int i, int j)
{
if (i<1 || i>n || j<1 || j>m)
return 0;
if (arr[i][j] == '.')
{
if (arr[i - 1][j] != '#' && arr[i + 1][j] != '#' && arr[i][j - 1] != '#' && arr[i][j + 1] != '#')
{
return 1;
}
}
return 0;
}
int main()
{
cin >> n >> m;
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
cin >> arr[i][j];
}
}
int cnt = 0;//表示可开垦荒地的数量
int max_ = 0;//增加荒地的最大值
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
if (arr[i][j] == '.')
{
cnt += check(i, j);
}
else
{
arr[i][j] = '.';
int temp = check(i, j);
temp += check(i - 1, j);
temp += check(i + 1, j);
temp += check(i, j - 1);
temp += check(i, j + 1);
if (temp > max_)
{
max_ = temp;
}
arr[i][j] = '#';
}
}
}
cout << cnt + max_;
return 0;
}
Day 21: GESP Level 5 2023.12_Cooking Problem
[Submit]
https://www.luogu.com.cn/problem/B3930
[Problem Description]
There are types of ingredients, numbered from to , where the type of ingredient has a deliciousness of .
Different combinations of ingredients may produce wonderful chemical reactions. Specifically, if two ingredients have deliciousness of and , their compatibility is .
Here, the operation is a bitwise AND operation, which requires converting the two operands to binary, padding the higher bits, and then performing the AND operation bit by bit. For example, the binary representations of and are and , performing the AND operation yields , which converts to decimal as , thus .In C++ or Python, the <span>&</span> operator can be used to represent the AND operation.
Now, please find the two ingredients with the highest compatibility and output their compatibility.
[Input Description]
The first line contains an integer , representing the number of ingredients.
The next line contains integers separated by spaces, representing the deliciousness of each ingredient.
[Output Description]
Output a single integer representing the highest compatibility.
[Sample Input 1]
3
1 2 3
[Sample Output 1]
2
[Sample Explanation 1]
The compatibility between ingredients numbered is , which is the highest compatibility among all pairs of ingredients.
[Sample Input 2]
5
5 6 2 10 13
[Sample Output 2]
8
[Sample Explanation 2]
The compatibility between ingredients numbered is , which is the highest compatibility among all pairs of ingredients.
[Data Range]
For the test points, it is guaranteed that .
For all test points, it is guaranteed that , .
Reference Answer:
/*
* [GESP202312 Level 5] Cooking Problem
* https://www.luogu.com.cn/problem/B3930
*/
# include<iostream>
# include<vector>
using namespace std;
int main()
{
// 1. Store data
int N;
cin >> N;
vector<int> a(N);
for (int i = 0;i < N;i++)
{
cin >> a[i];
}
// 2. Process data: Use the properties of bitwise AND operation to determine the maximum possible result from the highest bit to the lowest bit
vector<int> candidates = a;
int mask = 0;
// The maximum value of a is 2^31-1, so i starts from 30
// Check each bit from the highest (30th bit) to the lowest (0th bit) to see if it can be added to the current mask.
for (int i = 30;i >= 0;i--)
{
// For each bit, generate a candidate mask and filter out numbers that meet the current candidate mask condition.
int mask_ = mask | (1 << i);
vector<int> temp;
int count = 0;
for (int num : candidates)
{
if ((num & mask_) == mask_)
{
temp.push_back(num);
count++;
}
}
// If at least 2 numbers meet the condition, update the mask and narrow down the candidate array, continue processing lower bits.
if (count >= 2)
{
mask = mask_;
candidates = temp;
}
}
cout << mask;
return 0;
}
Day 21: GESP Level 6 2023.12_Work Communication
[Submit]
https://www.luogu.com.cn/problem/P10109
[Problem Description]
A company has employees, numbered from to . Among them, employee is the boss, and every other employee has a direct supervisor. We assume that the direct supervisor of employee is .
The company has strict management rules, where each employee can only be managed by themselves, their direct supervisor, or an indirect supervisor. Specifically, employee can manage employee if and only if , or , or can manage . In particular, employee (the boss) can only manage themselves and cannot be managed by any other employee.
Now, some colleagues want to collaborate and hope to find a colleague to lead this collaboration. This colleague must be able to manage all colleagues involved in the collaboration. If there are multiple employees who meet this condition, they want to find the employee with the highest number. Can you help them?
[Input Description]
The first line contains an integer , representing the number of employees.
The second line contains integers separated by spaces, representing the direct supervisors of each employee.
The third line contains an integer , representing the number of collaborations to be arranged.
Each of the following lines describes a collaboration: the first number is an integer (), representing the number of employees involved in this collaboration; followed by integers representing the employee numbers involved in this collaboration (guaranteed to be valid and unique).
It is guaranteed that the company structure is valid, meaning no employee can be their own direct or indirect supervisor.
[Output Description]
Output lines, each containing an integer representing the selected leader for each collaboration.
[Sample Input 1]
5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4
[Sample Output 1]
2
2
0
[Sample Explanation 1]
For the first collaboration, employees have a common supervisor, so they can collaborate.
For the second collaboration, employee 2 can manage all participants.
For the third collaboration, only the boss (employee 0) can manage all employees.
[Sample Input 2]
7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4
[Sample Output 2]
2
1
1
1
0
[Data Range]
For the test points, it is guaranteed that .
For all test points, it is guaranteed that , .
Reference Answer:
/*
* [GESP202312 Level 6] Work Communication
* https://www.luogu.com.cn/problem/P10109
*/
#include <iostream>
# include <vector>
using namespace std;
vector<int> parent = {-1};// Store parent nodes
vector<int> c;
// Find the parent node starting from x, recording the occurrence count
void find(int x)
{
while (x != -1)
{
c[x] += 1;
x = parent[x];
}
}
int main()
{
//1. Store data
int n;
cin >> n;
for (int i = 1;i < n;i++)
{
int p;
cin >> p;
parent.push_back(p);
}
int q;
cin >> q;
for (int i = 0;i < q;i++)
{
int m;
cin >> m;
c.assign(n, 0);
for (int j = 0;j < m;j++)
{
int k;
cin >> k;
find(k);
}
// 2. Process data
int ma = 0;
for (int j = 0;j < n;j++)
{
if (c[j] == m && ma < j)
{
ma = j;
}
}
// 3. Output result
cout << ma << endl;
}
return 0;
}
Youth Programming Competition Communication
The “Youth Programming Competition Communication Group” has been established (suitable for young people aged 6 to 18). Add the assistant’s WeChat to invite everyone into the learning group. After joining the group, everyone can participate in regularly organized 21-day problem-solving check-ins, level examination assessments, guidance for Ministry of Education whitelist competitions, and team competitions for youth programming.
