2017北京国庆刷题Day1 morning T2

T2火柴棒 (stick)

Time Limit:1000ms   Memory Limit:128MB

题目描述

众所周知的是，火柴棒可以拼成各种各样的数字。具体可以看下图：

通过2根火柴棒可以拼出数字“1”，通过5根火柴棒可以拼出数字“2”，以此类推。

现在LYK拥有k根火柴棒，它想将这k根火柴棒恰好用完，并且想知道能拼出的最小和最大的数分别是多少。

输入格式(stick.in)

一个数k。

输出格式(stick.out)

两个数，表示最小的数和最大的数。注意这两个数字不能有前导0。

输入样例

15

输出样例

108 7111111

数据范围

对于30%的数据k<=10。

对于60%的数据k<=20。

对于100%的数据1<k<=100。

k<=1e5可做？

知道什么叫搜索吗？就是dfs啊~

可以过k<=100000

贪心有反例 比如31  最小数是20088 不是22888

加了那么十来句剪枝就很快了~ 理论上还能更快

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 10100000

using namespace std;

int n,m,k,len1,len2,num,opt;

int ans1[N],ans2[N],pre[N],tmp[N],len;

int use[]={,,,,,,,,,};

bool cmp(int a,int b){return a>b;}

inline int read()

{

    int x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

void update(int num)

{

    if(len1<num) return;//8

    if(len1==num && pre[]>ans1[] || pre[]>ans1[]) return;//9

    for(int i=;i<=num;i++) tmp[i]=pre[i];

    sort(pre+,pre+num+);

    if(pre[]==)

    for(int i=;i<=num;i++)

    {

        if(pre[i]!=){int j=pre[i];pre[i]=;pre[]=j;break;}

    }

    int flag=;if(len1>num) flag=;

    else

    for(int i=;i<=num;i++)

    {

        if(pre[i]<ans1[i])

        {

            flag=;break;

        }

    }

    if(len1<num) flag=;

    if(flag)

    {

        for(int i=;i<=num;i++) ans1[i]=pre[i];len1=num;

    }

    for(int i=;i<=num;i++) pre[i]=tmp[i];

}

void dfs(int res)

{

    if(res==)

    {

        update(num);

        return;

    }

    //if(opt) return;

    /*if(res%7==0)

    {

        for(int i=1;i<=num;i++) ans1[i]=pre[i];

        for(int i=num+1;i<=num+res/7;i++) ans1[i]=8;

        opt=1;

    }*/

    if(pre[]>ans1[] || pre[]>ans1[]) return;//1

    if(len1-num> && (len1-num)*-res<) return;//2

    if(num>len1/ && k-res<res) return;//3

    if(num>=len1) return;//4

    if(res<) return;//5

    for(int i=;i<=;i++)

    {

        if(res== && i>)   break;//6

        if(res== && i>)   break;//7

        if(i== && num==)  continue;

        if(res-use[i]<)    continue;

        num+=;

        pre[num]=i;

        dfs(res-use[i]);num--;

    }

}

int main()

{

    k=read();

    memset(ans1,/,sizeof ans1);

    len1=k/+;

    if(k%==) for(int i=;i<=k/;i++) ans2[i]=;

    if(k%!=) {for(int i=;i<=k/;i++) ans2[i]=;ans2[]=;}

    if(k%==) for(int i=;i<=k/;i++) ans1[i]=,len1=k/;

    else dfs(k);

    for(int i=;i<=len1;i++) printf("%d",ans1[i]);

    printf(" ");

    for(int i=;i<=k/;i++) printf("%d",ans2[i]);

    return ;

}