csp信奥赛C++高频考点专项训练之字符串 --【字符串排序】：字符排序

csp信奥赛C++高频考点专项训练之字符串 --【字符串排序】：字符排序

题目描述

小杨有n nn个仅包含小写字母的字符串s 1 , s 2 , … , s n s_1,s_2,\ldots,s_ns1​,s2​,…,sn​，小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串t tt。小杨希望最后构成的字符串t tt满足：

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

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

输入格式

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

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

之后n nn行，每行包含一个字符串s i s_isi​。

输出格式

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

输入输出样例 #1

输入 #1

3 3 aa ac de 2 aac bc 1 gesp

输出 #1

1 0 0

说明/提示

样例解释

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

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

思路分析

1. 核心想法：如果存在一种排列使得拼接后的字符串t非递减，那么将原字符串数组按字典序升序排序后，直接拼接得到的字符串一定也满足非递减性质。因此只需要检查字典序排序后的拼接结果。
2. 判断方法：将排序后的字符串数组拼接成t，再将t的所有字符升序排序得到t2。如果t == t2，说明原字符串本身已经非递减，输出1；否则输出0。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intt,n;// t:测试组数, n:每组字符串个数boolcheck(string s[]){// 判断是否存在合法排列// 对字符串数组按字典序升序排序（下标1~n）sort(s+1,s+n+1);// 将排序后的字符串依次拼接string t="";for(inti=1;i<=n;i++){t+=s[i];}// 复制原拼接串，准备排序string t2=t;// 对拼接串的字符升序排序sort(t.begin(),t.end());// 若排序后的字符串与原串相等，说明原串已经非递减if(t==t2)returntrue;elsereturnfalse;}intmain(){cin>>t;// 读入测试组数while(t--){cin>>n;// 读入当前组字符串个数string s[110];// 存储字符串，下标从1开始for(inti=1;i<=n;i++){cin>>s[i];}if(check(s))cout<<1<<endl;elsecout<<0<<endl;}return0;}

功能分析

该程序的功能是：对于每组测试数据，判断是否存在一种将给定字符串排列并拼接的方式，使得最终得到的大字符串t的字符序列是非递减的（即每个字符都不小于前一个字符）。

实现步骤：

1. 读入测试组数t。
2. 对每组数据：
   • 读入n和n个字符串。
   • 调用check函数：
     • 将字符串数组按字典序升序排序。
     • 将排序后的字符串依次拼接成一个大字符串t。
     • 将t的所有字符进行升序排序得到t2。
     • 若t == t2则返回true，否则false。
   • 根据返回值输出1或0。

算法时间复杂度：每组数据排序字符串 O(n log n × L)，L 为字符串平均长度（≤10），字符排序 O(|t| log |t|)，其中 |t| ≤ n×10 ≤ 1000。

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}