sicily 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.

给一堆子串，求这堆子串的排列里字典序最小的那个。因为题目数据量很小所以可以直接全排列+排序，复杂度是O(n!)（这么暴力真是对不起……

为了方便用递归来求全排列（同样，反正数据量小我怕谁2333），stl的set自带有序所以就顺手用了。

#include<string>
#include<cstring>
#include<iostream>
#include<set>
using namespace std;

set<string> permutation;
int len;
string substring[8];
string fullstr;
bool visited[8];

void recur(int cur) {
    if (cur == len) {
        // compelete a full string consist of len substrings
        permutation.insert(fullstr);
    } else {
        for (int i = 0; i < len; ++i) {
            if (!visited[i]) {
                int lastEnd = fullstr.size();
                
                // add another substring
                fullstr += substring[i];
                visited[i] = true;
                
                recur(cur + 1);
                
                // remove the substring added in this level
                int curEnd = fullstr.size();
                fullstr.erase(lastEnd, curEnd);
                visited[i] = false;
            }
        }
    }
}

int main(void) {
#ifdef JDEBUG
    freopen("1198.in", "r", stdin);
    freopen("1198.out", "w", stdout);
#endif
    int t;
    
    cin >> t;
    while(t--) {
        cin >> len;
        
        // initialization
        fullstr.clear();
        permutation.clear();
        memset(visited, false, sizeof(visited));
        
        for (int i = 0; i < len; ++i) {
            cin >> substring[i];
        }
        
        recur(0);
     
        // use the lexicographically smallest full string
        cout << *(permutation.begin()) << '
';
    }
    return 0;
}

sicily 1198. Substring （递归全排列+排序）

相关推荐