Joke with permutation
Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:65536KB
Total submit users: 87, Accepted users: 60
Problem 13341 : Special judge
Problem description
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!
Input
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.
Output
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.
Sample Input
4111109876532
Sample Output
4 1 11 10 9 8 7 6 5 3 2
Problem Source
NEERC 2014
题意是给出一个全排列的字符串，然后让你确定排列两个元素之间的空格位置。
先根据字符串的长度求出n是多大，然后用dfs搜索符合条件的排列。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 500
using namespace std;
int n,l,cnt;
int flag[maxn];
char str[maxn];
int hash[maxn];
bool ll;
void dfs(int k)//k表示当前处理到哪个字符
{
if(ll)
return ;
if(k>=n)
{
for(int i=0;i<n;i++)
{
printf("%c",str[i]) ;
if(flag[i]&&i!=n-1)
printf(" ");
} //当K>n时，输出排列，return
ll=1;
return ;
}
if(!hash[str[k]-'0']&&(k+1>=n||str[k+1]!='0'))//一个字有两种组合，要么自己组成一个数，要么和后面的字符组成两位数，注意组合完之后, 字符串的第一个不能是零
{
hash[str[k]-'0']=1;
flag[k]=1;
dfs(k+1);
flag[k]=0;//整数不可取，回退
hash[str[k]-'0']=0;
}
if(!hash[(str[k]-'0')*10+str[k+1]-'0']&&((str[k]-'0')*10+(str[k+1]-'0'))<=cnt&&(str[k+2]!='0'||k+2>=n))
{
hash[(str[k]-'0')*10+str[k+1]-'0']=1;
flag[k+1]=1;
dfs(k+2);
flag[k+1]=0;
hash[(str[k]-'0')*10+str[k+1]-'0']=0;
}
}
int main()
{
while(scanf("%s",str)!=EOF)
{
n=strlen(str);
if(n<=9)
{
for(int i=0;i<n-1;i++)
printf("%c ",str[i]);
printf("%c
",str[n-1]);
continue;
}
int num=n-9;
cnt=9+num/2;
ll=0;
memset(hash,0,sizeof(hash));
memset(flag,0,sizeof(flag));
dfs(0);
printf("
");
}
return 0;
}