202412-字符排序(luogu-B4069)

GESP C++四级2024年12月真题。本题主要考查排序和字符串处理的应用。排序使用内置函数sort难度不大，整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B4069 [GESP202412 四级] 字符排序

题目要求

题目描述

小杨有 $n$ 个仅包含小写字母的字符串 $s_1,s_2,\ldots,s_n$，小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 $t$。小杨希望最后构成的字符串 $t$ 满足：

• 假设 $t_i$ 为字符串 $t$ 的第 $i$ 个字符，对于所有的 $j\lt i$ 均有 $t_j\le t_i$。两个字符的大小关系与其在字母表中的顺序一致，例如 $\texttt{e}\lt \texttt{g}\lt \texttt{p} \lt \texttt{s}$。

小杨想知道是否存在满足条件的字符串排列顺序。

输入格式

第一行包含一个正整数 $T$，代表测试数据组数。

对于每组测试数据，第一行包含一个正整数 $n$，含义如题面所示。

之后 $n$ 行，每行包含一个字符串 $s_i$。

输出格式

对于每组测试数据，如果存在满足条件的排列顺序，输出（一行一个）$\texttt{1}$，否则输出（一行一个） $\texttt{0}$。

输入输出样例 #1

输入 #1

3
3
aa
ac
de
2
aac
bc
1
gesp

输出 #1

1
0
0

说明/提示

样例解释

对于第一组测试数据，一种可行的排列顺序为 $\texttt{aa}+\texttt{ac}+\texttt{de}$，构成的字符串 $t$ 为 $\texttt{aaacde}$，满足条件。

对于全部数据，保证有 $1\le T,n\le 100$，每个字符串的长度不超过 $10$。

题目分析

本题的解题思路如下：

1. 题目要求

给定 $n$ 个小写字母字符串，要求将这些字符串按某种顺序排列并拼接，使得最终的字符串满足:对于任意位置 $i$，该位置之前的所有字符都不大于位置 $i$ 的字符。

2. 解题关键点

• 每个字符串本身必须是非递减的（字典序递增）
• 相邻字符串的衔接处必须满足：前一个字符串的最后一个字符不大于后一个字符串的第一个字符
• 需要判断是否存在满足条件的排列方式
• 可以利用排序来简化问题

3. 具体实现步骤

• 读入每组测试数据的字符串数量 $n$ 和所有字符串
• 检查每个字符串本身是否有序（非递减）
  • 如果存在字符串本身不是非递减的，则无解
• 对所有字符串按字典序排序
• 检查排序后的字符串数组是否满足条件：
  • 遍历相邻字符串，检查前一个字符串的最后一个字符是否不大于后一个字符串的第一个字符
• 根据检查结果输出 1（存在解）或 0（无解）

4. 时间复杂度分析

• 检查每个字符串是否有序：$O(L)$，其中 $L$ 是字符串的最大长度
• 字符串排序：$O(n\log n)$
• 检查排序后的结果：$O(n)$
• 总体时间复杂度：$O(n\log n)$
• 由于 $n \leq 100$，字符串长度不超过 10，此复杂度完全可以接受

5. 注意事项

• 需要同时满足两个条件：
  1. 每个字符串本身必须有序
  2. 排序后的字符串数组必须满足相邻字符串的衔接条件
• 使用 C++ 的 sort 函数可以方便地实现字符串排序
• 使用 is_sorted 函数可以快速判断字符串是否有序
• 字符串拼接时不需要实际执行拼接操作，只需要检查条件即可

这道题目主要考察对字符串排序和判断的应用，理解题意后使用适当的排序算法可以较为简单地解决问题。

关于sort的用法，前面文章【GESP】C++四级真题 luogu-B3851 [GESP202306 四级] 图像压缩已经介绍过。

示例代码

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

// 定义字符串数组，用于存储输入的字符串
std::string str_ary[105];

/**
 * 检查排序后的字符串数组是否满足条件
 * 条件：前一个字符串的最后一个字符不大于后一个字符串的第一个字符
 * @param n 字符串数量
 * @return 是否满足条件
 */
bool check(int n) {
    for (int i = 1; i < n; i++) {
        // 比较相邻字符串的最后一个字符和第一个字符
        if (str_ary[i - 1].back() > str_ary[i].front()) {
            return false;
        }
    }
    return true;
}

int main() {
    // 读入测试用例数量
    int T;
    std::cin >> T;
    
    // 处理每组测试用例
    while (T--) {
        // 读入字符串数量
        int n;
        std::cin >> n;
        
        // flag用于标记每个字符串本身是否有序
        bool flag = true;
        
        // 读入所有字符串并检查每个字符串本身是否有序
        for (int i = 0; i < n; i++) {
            std::cin >> str_ary[i];
            // 使用is_sorted检查字符串本身是否按字典序排序
            if (!is_sorted(str_ary[i].begin(), str_ary[i].end())) {
                flag = false;
            }
        }
        
        // 对字符串数组进行排序
        std::sort(str_ary, str_ary + n);
        
        // 输出结果：
        // 1. 每个字符串本身必须有序(flag为true)
        // 2. 排序后的字符串数组必须满足check条件
        if (flag && check(n)) {
            std::cout << "1" << "\n";
        } else {
            std::cout << "0" << "\n";
        }
    }

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号