首页 > 代码库 > sicily 1198. Substring （递归全排列+排序）
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()) << ‘\n‘; } return 0;}
sicily 1198. Substring （递归全排列+排序）