GESP C++ Level 4 Real Questions (Sorting, String Processing) [202412] Character Sorting (luogu-B4069)

GESP C++ Level 4 real questions for December 2024. This question mainly tests the application of sorting and string processing. The sorting uses the built-in functionsort with a difficulty level of ⭐⭐★☆☆. This question is rated asGeneral- on Luogu.

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-B4069 [GESP202412 Level 4] Character Sorting

Problem Requirements

Problem Description

Little Yang has strings consisting only of lowercase letters, and he wants to arrange these strings in a certain order and concatenate them to form a new string. Little Yang hopes that the final string satisfies:

Assuming is the th character of the string, for all it holds that . The relationship between two characters is consistent with their order in the alphabet, for example, .

Little Yang wants to know if there exists a string arrangement order that meets the conditions.

Input Format

The first line contains a positive integer , representing the number of test cases.

For each test case, the first line contains a positive integer , as described in the problem statement.

Then lines follow, each containing a string.

Output Format

For each test case, if there exists a valid arrangement order, output (one per line), otherwise output (one per line) .

Input/Output Example #1

Input #1

3
3
aa
ac
de
2
aac
bc
1
gesp

Output #1

1
0
0

Explanation/Notes

Example Explanation

For the first test case, one feasible arrangement order is , resulting in the string , which meets the conditions.

For all data, it is guaranteed that , and the length of each string does not exceed .

Problem Analysis

The solution approach for this problem is as follows:

1. Problem Requirements

Given strings of lowercase letters, the task is to arrange these strings in a certain order and concatenate them such that the final string satisfies: for any position , all characters before that position are not greater than the character at that position.

2. Key Points for Solving the Problem

Each string itself must be non-decreasing (in lexicographical order)
The junction between adjacent strings must satisfy: the last character of the previous string is not greater than the first character of the next string
It needs to be determined whether there exists a valid arrangement
Sorting can be used to simplify the problem

3. Specific Implementation Steps

Read the number of strings and all strings for each test case
Check if each string is ordered (non-decreasing)

If any string is not non-decreasing, then there is no solution

Sort all strings in lexicographical order
Check if the sorted array of strings meets the conditions:

Iterate through adjacent strings and check if the last character of the previous string is not greater than the first character of the next string

Based on the check results, output 1 (solution exists) or 0 (no solution)

4. Time Complexity Analysis

Check if each string is ordered:, where is the maximum length of the strings
Sorting the strings:
Check the sorted results:
Overall time complexity:
Since , and the length of the strings does not exceed 10, this complexity is completely acceptable

5. Notes

Both conditions must be satisfied:

Each string must be ordered
The sorted array of strings must satisfy the junction condition of adjacent strings

Using C++’s sort function can conveniently implement string sorting

Using is_sorted function can quickly check if a string is ordered

When concatenating strings, actual concatenation is not needed; only checking the conditions is sufficient

This problem mainly tests the application of string sorting and checking. After understanding the problem, using an appropriate sorting algorithm can simplify the solution.

Regarding the usage of sort, it has been introduced in a previous article【GESP】C++ Level 4 Real Questions luogu-B3851 [GESP202306 Level 4] Image Compression.

Example Code

#include <algorithm>
#include <iostream>
#include <map>

// Define string array to store input strings
std::string str_ary[105];

/**
 * Check if the sorted string array meets the conditions
 * Condition: The last character of the previous string is not greater than the first character of the next string
 * @param n Number of strings
 * @return Whether the condition is met
 */
bool check(int n) {
    for (int i = 1; i < n; i++) {
        // Compare the last character of the previous string and the first character of the next string
        if (str_ary[i - 1].back() > str_ary[i].front()) {
            return false;
        }
    }
    return true;
}

int main() {
    // Read the number of test cases
    int T;
    std::cin >> T;
    
    // Process each test case
    while (T--) {
        // Read the number of strings
        int n;
        std::cin >> n;
        
        // flag to mark if each string is ordered
        bool flag = true;
        
        // Read all strings and check if each string is ordered
        for (int i = 0; i < n; i++) {
            std::cin >> str_ary[i];
            // Use is_sorted to check if the string is sorted in lexicographical order
            if (!is_sorted(str_ary[i].begin(), str_ary[i].end())) {
                flag = false;
            }
        }
        
        // Sort the string array
        std::sort(str_ary, str_ary + n);
        
        // Output results:
        // 1. Each string must be ordered (flag is true)
        // 2. The sorted string array must meet the check condition
        if (flag && check(n)) {
            std::cout << "1" << "\n";
        } else {
            std::cout << "0" << "\n";
        }
    }

    return 0;
}

For detailed information on GESP levels, real questions, syllabus analysis, and practice lists, see:

【Pinned】【GESP】C++ Certification Learning Resource Compilation

“luogu-” series questions can be evaluated online atLuogu Question Bank.

“bcqm-” series questions can be evaluated online atProgramming Enlightenment Question Bank.