首页 > 其他 > 详细

CF:Jokewithpermutation

时间:2015-10-28 21:06:22      阅读:222      评论:0      收藏:0      [点我收藏+]

标签:class   style   log   com   http   si   it   src   la   

Jokewithpermutation

Input ?le: joke.in
Output ?le: joke.out
Joey had saved a permutation of integers from 1 to n in a text ?le. 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 ?le.
Help Joey to restore the original permutation after the Joe’s joke!
Input
The input ?le 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 ?le with the restored permutation. Don’t forget the spaces!
If there are several possible original permutations, write any one of them.
Sample input and output
joke.in

4111109876532

joke.out

4 1 11 10 9 8 7 6 5 3 2

 




题意:输入一排数字,所有的数字之间没有空格隔开,这些数字由1-n组,字符串的长度最少为1,最多为50。输出那一排数字,并用空格隔开。

这一题是一道经典的dfs搜索,按照我的dfs搜索方法,要把10,20先区分开。搜索到的当前状态是字符串的第i个字符,如果这个数字没有被标记,那就搜索dfs(i+1,t+1);如果这个数字被标记的话,再判断这个数字是否小于3,如果小于3的话,那么和后面那个字符一起组合成一个数字,如果这个数字没有被标记的话,那么就搜索dfs(i+1,t+1);

如果都不符合的话,那就return回溯。要注意dfs搜索不符合要求的话,要记得把数字的标记状态回溯恢复一下。




 

技术分享
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[55];
int flag[31];
int x[31];
int len,n;
void dfs(int i,int t);
int main()
{
    freopen("joke.in","r",stdin);
    freopen("joke.out","w",stdout);
    int i;
    memset(s,0,sizeof(s));
    memset(x,0,sizeof(x));
    memset(flag,0,sizeof(flag));
    while(scanf("%s",s)!=EOF)
    {
        len=strlen(s);
        if(len<10) //优化,如果都是十以内
        {
            n=len;
            for(i=0; i<n-1; i++)
                printf("%c ",s[i]);
            printf("%c\n",s[i]);
        }
        else
        {
            n=(len-11)/2+10;
            //cout<<len<<" "<<n<<endl;
            dfs(0,0);
            for(i=0; i<n-1; i++)
                printf("%d ",x[i]);
            printf("%d\n",x[i]);
        }
        memset(s,0,sizeof(s));
        memset(x,0,sizeof(x));
        memset(flag,0,sizeof(flag));
    }
    return 0;
}
void dfs(int i,int t)
{
    if(i==len) return;
    if((i+1)<len&&s[i+1]==0) //注意10,20这两个数据,比较特殊
    {
        flag[(s[i]-48)*10]=1;
        x[t]=(s[i]-48)*10;
        dfs(i+2,t+1);
        flag[(s[i]-48)*10]=1;
    }
    else if(flag[s[i]-48]==0)
    {
        flag[s[i]-48]=1;
        //cout<<s[i]-48<<" 1"<<endl;
        x[t]=s[i]-48;
        dfs(i+1,t+1);
        flag[s[i]-48]=0;
        //cout<<s[i]-48<<" 0"<<endl;
    }
    else if((s[i]-48)<3&&(i+1)<len&&flag[(s[i]-48)*10+(s[i+1]-48)]==0)
    {
        flag[(s[i]-48)*10+(s[i+1]-48)]=1;
        //cout<<(s[i]-48)*10+(s[i+1]-48)<<" 1"<<endl;
        x[t]=(s[i]-48)*10+(s[i+1]-48);
        dfs(i+2,t+1);
        flag[(s[i]-48)*10+(s[i+1]-48)]=0;
        //cout<<(s[i]-48)*10+(s[i+1]-48)<<" 0"<<endl;
    }
    return;
}
View Code

 

CF:Jokewithpermutation

标签:class   style   log   com   http   si   it   src   la   

原文:http://www.cnblogs.com/GeekZRF/p/4918347.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号