一、题目解读

题目核心要求

给定 T 组测试用例，每组包含 n 个字符串：

1. 首先，每个字符串自身必须是非递减的（即字符串内部字符 s[0] ≤ s[1] ≤ ... ≤ s[len-1]），若任意一个字符串不满足，直接判定为「不可行」；
2. 其次，判断是否存在一种字符串排列顺序，使得将这些字符串按该顺序拼接后，得到的总字符串也是非递减的；
3. 最终输出：可行则输出 1，不可行则输出 0。

关键洞察

单个字符串自身非递减时，其内部字符是有序的，因此拼接后能否整体非递减，核心只取决于相邻字符串的「尾字符」和「首字符」（前一个字符串的尾字符 ≤ 后一个字符串的首字符）。

二、解题思路

整个解决方案分为 4 个核心步骤：

1. 前置校验：遍历每个字符串，检查其自身是否非递减。若有任意一个不满足，直接返回 0；
2. 提取关键信息：对每个合法的字符串，提取其「首字符」和「尾字符」（无需保留完整字符串，这两个字符是判断拼接的核心）；
3. 排序优化：将提取的「首/尾字符对」按「首字符升序，首字符相同则按尾字符升序」排序。该排序策略能最大化满足「前一个尾 ≤ 后一个首」的条件；
4. 最终验证：检查排序后的「字符对序列」，确认相邻元素满足「前一个尾字符 ≤ 后一个首字符」，同时二次兜底验证首字符非递减（排序后理论上已满足，做冗余校验提升鲁棒性）。

三、代码逐行解析

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

• 引入必备头文件：输入输出（iostream）、动态数组（vector）、字符串（string）、排序算法（algorithm）；
• using namespace std; 简化代码，避免重复写 std::。

// 定义一个结构体存储字符串的首尾字符
struct StringPart {
    char first;  // 字符串首字符
    char last;   // 字符串尾字符
    // 构造函数：快速初始化首尾字符
    StringPart(char f, char l) : first(f), last(l) {}
};

• 自定义结构体 StringPart，仅存储字符串的「首字符」和「尾字符」，减少内存占用，聚焦核心信息。

// 排序比较函数：先按首字符升序，首字符相同则按尾字符升序
bool compare(const StringPart &a, const StringPart &b) {
    if (a.first != b.first) {
        return a.first < b.first;  // 优先按首字符从小到大
    }
    return a.last < b.last;       // 首字符相同，按尾字符从小到大
}

• 排序的核心规则：
  • 首字符小的排前面，保证拼接时「起始字符」整体递增；
  • 首字符相同时，尾字符小的排前面，减少后续「前尾 > 后首」的概率。

int main() {
    int T;
    cin >> T;  // 读取测试用例组数

• 读取测试用例总数 T，对应多组测试的场景。

    while (T--) {  // 遍历每组测试用例
        int n;
        cin >> n;  // 读取当前组的字符串数量
        vector<string> strs(n);  // 存储当前组的所有字符串
        for (int i = 0; i < n; i++) {
            cin >> strs[i];  // 读取每个字符串
        }

• 逐组处理：读取每组的字符串数量 n，再读取 n 个字符串并存储到 strs 数组。

        bool valid = true;    // 标记：是否所有字符串自身非递减
        vector<StringPart> parts;  // 存储每个合法字符串的首尾字符对

        // 检查每个字符串是否自身非递减，并提取首尾字符
        for (const string &s : strs) {
            // 检查单个字符串内部是否非递减
            for (int i = 1; i < s.length(); i++) {
                if (s[i] < s[i-1]) {  // 发现递减字符
                    valid = false;
                    break;  // 跳出内层循环，无需继续检查该字符串
                }
            }
            if (!valid) break;  // 已有字符串不合法，跳出外层循环
            // 字符串合法，提取首尾字符存入 parts
            parts.emplace_back(s[0], s.back());
        }

• 核心前置校验：
  • 遍历每个字符串，检查其内部是否非递减（s[i] < s[i-1] 说明递减）；
  • 若发现任意字符串不合法，立即标记 valid = false 并终止检查；
  • 合法字符串则通过 emplace_back 构造 StringPart，存入 parts 数组。

        if (!valid) {  // 存在自身递减的字符串，直接输出 0
            cout << "0" << endl;
            continue;  // 处理下一组测试用例
        }

• 前置校验不通过，直接输出 0 并跳过后续逻辑。

        // 对首尾字符对按自定义规则排序
        sort(parts.begin(), parts.end(), compare);

• 调用 sort 算法，使用自定义的 compare 函数对 parts 排序，优化字符串的拼接顺序。

        // 检查排序后的序列是否满足拼接条件
        bool ok = true;
        for (int i = 1; i < n; i++) {
            // 前一个字符串的尾字符 > 后一个字符串的首字符 → 拼接后递减
            if (parts[i-1].last > parts[i].first) {
                ok = false;
                break;
            }
        }

• 验证核心条件：排序后相邻字符串的「前尾 ≤ 后首」，不满足则标记 ok = false。

        // 检查首字符是否非递减（排序后理论上已满足，冗余校验提升鲁棒性）
        if (ok) {
            for (int i = 1; i < n; i++) {
                if (parts[i].first < parts[i-1].first) {
                    ok = false;
                    break;
                }
            }
        }

• 兜底校验：虽然排序规则保证了首字符升序，但增加此步骤可避免排序逻辑出错导致的问题（实际项目中冗余校验能降低 bug 率）。

        // 输出最终结果：满足条件输出 1，否则输出 0
        cout << (ok ? "1" : "0") << endl;
    }
    
    return 0;
}

• 根据最终的 ok 标记输出结果，完成一组测试用例的处理。

四、核心要点总结

1. 前置校验是基础：单个字符串自身非递减是必要条件，若跳过此步，后续排序再合理也无法得到合法结果；
2. 核心优化是排序：按「首字符升序、首同则尾升序」排序，是保证拼接后非递减的关键策略，能最大化满足「前尾 ≤ 后首」；
3. 聚焦关键信息：仅存储字符串的首尾字符，而非完整字符串，既节省内存，又简化了后续的验证逻辑（无需拼接完整字符串）。

这个解法的时间复杂度主要由排序决定（O(n log n)），n 为每组的字符串数量，在算法题中属于高效解法，能应对常规的数据规模。