题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=13341&courseid=0
| Joke with permutation |
| Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:65536KB |
| Total submit users: 85, Accepted users: 57 |
| 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 Help |
| Input |
|
The input file contains a single line with a single string — the Joey’s The Joey’s permutation had at least 1 and at |
| Output |
|
Write a line to the output file with the restored permutation. Don’t forget If there are several possible original permutations, write |
| Sample Input |
4111109876532 |
| Sample Output |
4 1 11 10 9 8 7 6 5 3 2 |
| Problem Source |
| NEERC 2014 |
| Submit Discuss Judge Status Problems Ranklist |
题目大意：将一串完整的字符串分成1~n个数。将空格补进去，并将其输出。
解题思路：1、注意这个n是可以求出来的
2、一个数字一个数字比较，只要满足这个数字小于n，还有保证这个数字没有访问过就ok啦
详见代码。
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int n,flag;
char ch[];
int ans[];
bool vis[]; bool dfs(int i,int k)
{
if (flag==)
return true;
if (k==n+)
{
for (int i=;i<k-;i++)
{
printf ("%d ",ans[i]);
}
printf ("%d\n",ans[k-]);
flag=;
return true;
}
if (ch[i]-''<=n&&!vis[ch[i]-'']&&ch[i]-''>)
{
ans[k]=ch[i]-'';
vis[ch[i]-'']=;
if(dfs(i+,k+)) return true;
vis[ch[i]-'']=;
}
if ((ch[i]-'')*+ch[i+]-''<=n&&(ch[i]-'')*+ch[i+]-''>&&!vis[(ch[i]-'')*+ch[i+]-''])
{
ans[k]=(ch[i]-'')*+ch[i+]-'';
vis[(ch[i]-'')*+ch[i+]-'']=;
if(dfs(i+,k+)) return true;
vis[(ch[i]-'')*+ch[i+]-'']=;
}
return false;
} int main()
{
while (scanf("%s",ch)!=EOF)
{
flag=;
memset(ans,,sizeof(ans));
memset(vis,,sizeof(vis));
int len=strlen(ch);
if (len>)
n=(len-)/+;
else
n=len;
dfs(,);//dfs();
}
return ;
}