gesp(C++四级)(16)洛谷:B4069:[GESP202412 四级] 字符排序
gesp(C++四级)(16)洛谷:B4069:[GESP202412 四级] 字符排序
题目描述
小杨有 n n n 个仅包含小写字母的字符串 s 1 , s 2 , … , s n s_1,s_2,\ldots,s_n s1,s2,…,sn,小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 t t t。小杨希望最后构成的字符串 t t t 满足:
- 假设 t i t_i ti 为字符串 t t t 的第 i i i 个字符,对于所有的 j < i j\lt i j<i 均有 t j ≤ t i t_j\le t_i tj≤ti。两个字符的大小关系与其在字母表中的顺序一致,例如 e < g < p < s \texttt{e}\lt \texttt{g}\lt \texttt{p} \lt \texttt{s} e<g<p<s。
小杨想知道是否存在满足条件的字符串排列顺序。
输入格式
第一行包含一个正整数 T T T,代表测试数据组数。
对于每组测试数据,第一行包含一个正整数 n n n,含义如题面所示。
之后 n n n 行,每行包含一个字符串 s i s_i si。
输出格式
对于每组测试数据,如果存在满足条件的排列顺序,输出(一行一个) 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 t t 为 aaacde \texttt{aaacde} aaacde,满足条件。
对于全部数据,保证有 1 ≤ T , n ≤ 100 1\le T,n\le 100 1≤T,n≤100,每个字符串的长度不超过 10 10 10。
AC代码(100分)
#include<bits/stdc++.h>
using namespace std;
/*思路:
1、满足题意的拼接字符串的可行思路为:
先将字符串数组按字典序升序排序,然后依次拼接
2、判断拼接后的字符串是否满足题意:
将拼接后的字符串升序排序,看排序后的结果和原字符串是否相等
*/
int t,n;
bool check(string s[]){
//对字符串数组排序
sort(s+1,s+n+1);
//拼接字符串
string t="";
for(int i=1;i<=n;i++){
t+=s[i];
}
//判断拼接后的字符串是符合要求
string t2=t;//t2存原来的字符串
sort(t.begin(),t.end());
if(t==t2) return true;//判断排序后的字符串和原来的字符串是否相等
else return false;
}
int main(){
cin>>t;
while(t--){
cin>>n;
string s[110];
for(int i=1;i<=n;i++){
cin>>s[i];
}
if(check(s)) cout<<1<<endl;
else cout<<0<<endl;
}
return 0;
}
文末彩蛋:
点击王老师青少年编程主页有更多精彩内容