简答题 偏难
#20727

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

字符排序

时间限制:1.0 s

内存限制:512.0 MB

题面描述

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

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

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

输入格式

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

对于每组测试数据,第一行包含一个正整数 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:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; string s[110]; void bubble_sort(string *a, int n) { bool flag = true; while (flag) { flag = false; for (int i = 1; i &lt; n; ++i) { if (a[i] &gt; a[i + 1]) { flag = true; string t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; } } } } int main(){ int t; cin&gt;&gt;t; while(t--){ int n; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;s[i]; } bubble_sort(s, n); string t=""; for(int i=1;i&lt;=n;i++){ t+=s[i]; } int m = t.size(); int fl=1; for(int i=1;i&lt;m;i++){ if(t[i]&lt;t[i-1]){ fl=0; break; } } cout&lt;&lt;fl&lt;&lt;"\n"; } }</pre>
这道题暂未补解析。