CodeForces 670F Restore a Number

时间：2021-11-26 16:05:48

模拟。

首先暴力找到答案的位数，然后就是分类讨论输出答案。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c=getchar(); x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) {x=x*+c-''; c=getchar();}

}

const int maxn=;

char s[maxn],t[maxn];

int f[],g[],len,tLen,sLen;

bool check(int x)

{

    int tmp[],sum=,tt=x;

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

    while(x)

    {

        tmp[x%]--;

        if(tmp[x%]<) return ;

        x=x/; sum++;

    }

    if(tt+sum==sLen)

    {

        bool flag=; for(int i=;i<;i++) if(tmp[i]) flag=;

        if(flag) return ;

        else

        {

            if(t[]!='') return ;

            return ;

        }

    }

    return ;

}

char num[][maxn];

char tmp[maxn],ans[maxn];

char tmp1[maxn],tmp2[maxn];

int main()

{

    scanf("%s%s",s,t); sLen=strlen(s); tLen=strlen(t);

    for(int i=;s[i];i++) f[s[i]-'']++;

    for(int i=;t[i];i++) g[t[i]-'']++;

    len=tLen; if(t[]=='') len++;

    for(int i=;i<;i++) f[i]=f[i]-g[i]; bool F=;

    for(;len<=;len++) { if(check(len)) {F=;break;} }

    if(F==) { printf("0\n"); return ;}

    int ttt=len; while(ttt) f[ttt%]--,ttt=ttt/;

    if(t[]=='')

    {

        int xx; for(int i=;i<;i++) {if(f[i]){ xx=i;break; }}

        f[xx]--;  printf("%d",xx); int sz=;

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

        {

            if(f[i]==) continue;

            for(int j=; j<f[i]; j++) num[sz][j]=i+'';

            sz++;

        }

        bool ff=;

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

        {

            if(ff==) printf("%s",num[i]);

            else

            {

                char h1[maxn],h2[maxn]; h1[]=h2[]=;

                strcpy(h1,num[i]); strcat(h1,t);

                strcpy(h2,t); strcat(h2,num[i]);

                if(num[i][]<t[])  printf("%s",num[i]);

                else if(strcmp(h1,h2)<) printf("%s",num[i]);

                else {  printf("%s%s",t,num[i]); ff=; }

            }

        }

        if(ff==) printf("%s",t);

        printf("\n");

    }

    else

    {

        int xx=-; for(int i=;i<;i++) {if(f[i]){ xx=i;break; }}

        if(xx==-)

        {

            printf("%s",t);

            for(int i=;i<f[];i++) printf(""); printf("\n");

        }

        else if(xx>t[]-'')

        {

            printf("%s",t);

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

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

            printf("\n");

        }

        else if(xx==t[]-'')

        {

            if(f[]==)

            {

                for(int i=;i<f[xx];i++) tmp[i]=xx+''; tmp[f[xx]]=;

                char h1[maxn],h2[maxn]; h1[]=h2[]=;

                strcpy(h1,t); strcat(h1,tmp);

                strcpy(h2,tmp); strcat(h2,t);

                if(strcmp(h1,h2)<) strcpy(ans,h1);

                else strcpy(ans,h2);

                int tt=strlen(ans);

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

                    for(int j=;j<f[i];j++)

                        ans[tt++]=i+'';

                ans[tt]=;

                printf("%s\n",ans);

            }

            else

            {

                tmp1[]=tmp2[]=;

                strcpy(tmp1,t); int tt=strlen(tmp1);

                for(int i=;i<f[];i++) tmp1[tt++]=+'';

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

                    for(int j=;j<f[i];j++)

                        tmp1[tt++]=(i+'');

                tmp1[tt]=;

                tmp2[]=xx+''; f[xx]--; tt=;

                for(int i=;i<f[];i++) tmp2[tt++]=(+''); tmp2[tt]=;

                for(int i=;i<f[xx];i++) tmp[i]=xx+''; tmp[f[xx]]=;

                char h1[maxn],h2[maxn]; h1[]=h2[]=;

                strcpy(h1,t); strcat(h1,tmp);

                strcpy(h2,tmp); strcat(h2,t);

                if(strcmp(h1,h2)<) strcat(tmp2,h1);

                else strcat(tmp2,h2);

                tt=strlen(tmp2);

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

                    for(int j=;j<f[i];j++)

                        tmp2[tt++]=i+'';

                tmp2[tt]=;

                if(strcmp(tmp1,tmp2)>) printf("%s\n",tmp2);

                else printf("%s\n",tmp1);

            }

        }

        else

        {

            f[xx]--;  printf("%d",xx); int sz=;

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

            {

                if(f[i]==) continue;

                for(int j=; j<f[i]; j++) num[sz][j]=i+'';

                num[sz][f[i]]=;

                sz++;

            }

            bool ff=;

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

            {

                if(ff==) printf("%s",num[i]);

                else

                {

                    char h1[maxn],h2[maxn]; h1[]=h2[]=;

                    strcpy(h1,num[i]); strcat(h1,t);

                    strcpy(h2,t); strcat(h2,num[i]);

                    if(num[i][]<t[])  printf("%s",num[i]);

                    else if(strcmp(h1,h2)<) printf("%s",num[i]);

                    else {  printf("%s%s",t,num[i]); ff=; }

                }

            }

            if(ff==) printf("%s",t);

            printf("\n");

        }

    }

    return ;

}

相关文章