简答题 偏难
#18053

字符排序 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有 n 个仅包含小写字母的字符串s 1 ,s 2 ,...,s n ,小杨想将这些字符…

字符排序

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有 n 个仅包含小写字母的字符串s1,s2,...,sn,小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 t 。小杨希望最后构成的字符串 t 满足:

假设ti为字符串 t 的第 i 个字符,对于所有的j<i 均有tj≤ti。两个字符的大小关系与其在字母表中的顺序一致,例如e<g<p<s。

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

输入格式

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

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

之后 n 行,每行包含一个字符串si。

输出格式

对于每组测试数据,如果存在满足条件的排列顺序,输出 1,否则输出 0。


输入样例

3
3
aa
ac
de
2
aac
bc
1
gesp

输出样例

1
0
0

样例解释

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

对于全部数据,保证有1≤t,n≤100,每个字符串的长度不超过 10。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">def bubble_sort(a): n, flag = len(a), True while flag: flag = False for i in range(n - 1): if a[i] &gt; a[i + 1]: flag = True a[i], a[i + 1] = a[i + 1], a[i] t = int(input()) for _ in range(t): n = int(input()) s = [] for _ in range(n): s.append(input()) bubble_sort(s) t = ''.join(s) fl = 1 for i in range(1, len(t)): if t[i] &lt; t[i - 1]: fl = 0 break print(fl)</pre>
这道题暂未补解析。