题目大意：
小蒜头又调皮了。这一次，姐姐的实验报告惨遭毒手。
姐姐的实验报告上原本记录着从 1 到 n 的序列，任意两个数字间用空格间隔。但是“坑姐”的蒜头居然把数字间的空格都给删掉了，整个数字序列变成一个长度为 1 到 100 的且首部没有空格的数字串。
现在姐姐已经怒了，蒜头找你写个程序快点把试验数据复原。
输入
输入文件有一行，为一个字符串——被蒜头搞乱的实验数据。
字符串的长度在 1 到 100 之间。
输出
输出共一行，为姐姐的原始测试数据—— 1 到 n 的输出。
任意两个数据之间有一个空格。
如果有多组符合要求的正确解，输出其中任意一组即可。
本题答案不唯一，符合要求的答案均正确
样例输入
4111109876532
样例输出
4 1 11 10 9 8 7 6 5 3 2
解题思路：
因为字符串的长度不超过100，可以计算出n最大是54，我们只需要枚举一位数和两位数。
先通过字符串的长度计算出n，开一个数组标记枚举过的数，只有没标记过的数并且小于等于n才会存下来继续往后搜。
size<=9: n=size
size>9: n=(size-9)/2+9
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #include <sstream> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 const double PI = acos(-1); 17 const double eps =1e-8; 18 #define Bug cout<<"---------------------"<<endl 19 const int maxn=1e5+10; 20 using namespace std; 21 const int prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; 22 23 string str; 24 int n;//提前计算出，可用来剪枝 25 int ans[105]; 26 bool vis[105];//判断某个数出现没 27 bool flag; 28 29 void DFS(int step,int num)//step表示第几个字符,num表示已经找到了num个数 30 { 31 if(flag) return;//最优性剪枝 32 if(step==str.size()) 33 { 34 for(int i=0;i<num;i++) 35 { 36 if(i==0) cout<<ans[i]; 37 else cout<<' '<<ans[i]; 38 } 39 cout<<endl; 40 flag=true; 41 return ; 42 } 43 int t=str[step]-'0'; 44 if(t<=n&&!vis[t])//搜一位 45 { 46 ans[num]=t; 47 vis[t]=true; 48 DFS(step+1,num+1); 49 vis[t]=false; 50 } 51 if(step!=str.size()-1) 52 { 53 t=t*10+str[step+1]-'0'; 54 if(t<=n&&!vis[t])//搜两位 55 { 56 ans[num]=t; 57 vis[t]=true; 58 DFS(step+2,num+1); 59 vis[t]=false; 60 } 61 } 62 } 63 64 int main() 65 { 66 #ifdef DEBUG 67 freopen("sample.txt","r",stdin); 68 #endif 69 // ios_base::sync_with_stdio(false); 70 // cin.tie(NULL); 71 72 cin>>str; 73 n=str.size()<=9?str.size():(str.size()-9)/2+9; 74 DFS(0,0); 75 76 return 0; 77 }
-