2020牛客国庆集训派对day4 Jokewithpermutation

Jokewithpermutation

题目描述

Joey had saved a permutation of integers from 1 to n in a text file. All the numbers were written as decimal numbers without leading spaces. Then Joe made a practical joke on her: he removed all the spaces in the file. Help Joey to restore the original permutation after the Joe’s joke! 输入描述: The input file contains a single line with a single string — the Joey’s permutation without spaces. The Joey’s permutation had at least 1 and at most 50 numbers. 输出描述: Write a line to the output file with the restored permutation. Don’t forget the spaces! If there are several possible original permutations, write any one of them.

示例1 输入 复制

4111109876532

输出 复制

4 1 11 10 9 8 7 6 5 3 2

备注: Author: Mikhail Dvorkin

题意：

给你一串数，这串数字为n的全排列，问怎么将数分段格，使得成为n的全排列 看样例4111109876532，可以为4 1 11 10 9 8 7 6 5 3 2

题解：

队友做得，dfs暴力即可，就是假设当为一位数或者两位数时，看看情况 详细看代码吧

代码：

#include<bits/stdc++.h> #define maxn 6000 using namespace std; char a[maxn]; vector<int>ans; bool vis[maxn]; unordered_map<int,int>p; bool f=0; int s; void dfs(int n){ if(f) return ; int size=strlen(a+1); if(n>size){ printf("%d",ans[0]); for(int i=1;i<ans.size();i++){ printf(" %d",ans[i]); } f=1; return ; } if(p[a[n]-'0']==0){ p[a[n]-'0']=1; ans.push_back(a[n]-'0'); dfs(n+1); ans.pop_back(); p[a[n]-'0']=0; } if(f) return ; if(n<=size-1&&p[(a[n]-'0')*10+(a[n+1]-'0')]==0&&(a[n]-'0')*10+(a[n+1]-'0')<=s){ p[(a[n]-'0')*10+(a[n+1]-'0')]=1; ans.push_back((a[n]-'0')*10+(a[n+1]-'0')); dfs(n+2); ans.pop_back(); p[(a[n]-'0')*10+(a[n+1]-'0')]=0; } if(f) return ; } int main(){ scanf("%s",a+1); s=strlen(a+1)>9?(strlen(a+1)-9)/2+9:strlen(a+1); dfs(1); return 0; }