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;
}