1198. Substring

Description

Dr lee cuts a string S into N pieces,s[1],…,s[N].

Now, Dr lee gives you these N sub-strings: s[1],…s[N]. There might be several possibilities that the string S could be. For example, if Dr. lee gives you three sub-strings {“a”,“ab”,”ac”}, the string S could be “aabac”,”aacab”,”abaac”,…

Your task is to output the lexicographically smallest S.

Input

The first line of the input is a positive integer T. T is the number of the test cases followed.

The first line of each test case is a positive integer N (1 <=N<= 8 ) which represents the number of sub-strings. After that, N lines followed. The i-th line is the i-th sub-string s[i]. Assume that the length of each sub-string is positive and less than 100.

Output

The output of each test is the lexicographically smallest S. No redundant spaces are needed.

Sample Input

1
3
a
ab
ac

Sample Output

aabac

Problem Source

ZSUACM Team Member

一开始看着题目都摸不着头脑，短短的一段文字，都不知道它想要我干嘛，于是随便写了一个把所有子串连在一起的代码，提交，果然是错的。但我看呀看呀，还是不明白它那个例子为什么会得出这个结果。只好GOOGLE一下了，看了才知道，这是一道字典排序题来的。这下明白它想要我干嘛了。

它的意思是说，所有的子串，按照字典的顺序，来组合。

比如例子中的，a,ab,ac, 首先第一个字母是按字母顺序来排序，然后第二个字母，以此类推。

但不止这么简单，因为有一种情况是：c,cb，如果只是按照上面那种按字母顺序排好序后就串在一起的话，会是这种结果：ccb，但这不是题目所要的结果，而是cbc，所以在这里的话，我是这样处理的：

在比较两个子串的时候，先分两种情况组合，得到两个结果，然后比较这两个结果就行了。如：

bool Comp(const string &a,const string &b)
{
    string sub1,sub2;
    sub1=a+b;
    sub2=b+a;
    if(sub1.compare(sub2)==-1)
        return true;
    else
        return false;
}

这样就可以得到题目要的结果。

这道题，我使用vector容器，和快速排序进行解答。

我的答案是：

View Code

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;


bool Comp(const string &a,const string &b)
{
    string sub1,sub2;
    sub1=a+b;
    sub2=b+a;
    if(sub1.compare(sub2)==-1)
        return true;
    else
        return false;
}
int main()
{
//    ifstream cin("input.txt");
    string sub,result;
    vector<string> s;
    vector<string>::iterator it;
    int n,t;
    cin>>t;
    for(int j=0;j<t;++j)
    {
        cin>>n;
        result="";
        for(int i=0;i<n;++i)
        {
            cin>>sub;
            s.push_back(sub);
        }        
        sort(s.begin(),s.end(),Comp);
        for(it=s.begin();it!=s.end();++it)
        {
            result+=*it;
        }
        cout<<result<<endl;    
        s.clear();
    }

    return 0;
}

时间大小

312KB