首页 > 代码库 > CodeForces 670F Restore a Number

CodeForces 670F Restore a Number

模拟。

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

#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-6;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=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-0; c=getchar();}}const int maxn=1000010;char s[maxn],t[maxn];int f[10],g[10],len,tLen,sLen;bool check(int x){    int tmp[10],sum=0,tt=x;    for(int i=0;i<10;i++) tmp[i]=f[i];    while(x)    {        tmp[x%10]--;        if(tmp[x%10]<0) return 0;        x=x/10; sum++;    }    if(tt+sum==sLen)    {        bool flag=0; for(int i=1;i<10;i++) if(tmp[i]) flag=1;        if(flag) return 1;        else        {            if(t[0]!=0) return 1;            return 0;        }    }    return 0;}char num[15][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=0;s[i];i++) f[s[i]-0]++;    for(int i=0;t[i];i++) g[t[i]-0]++;    len=tLen; if(t[0]==0) len++;    for(int i=0;i<10;i++) f[i]=f[i]-g[i]; bool F=0;    for(;len<=1000000;len++) { if(check(len)) {F=1;break;} }    if(F==0) { printf("0\n"); return 0;}    int ttt=len; while(ttt) f[ttt%10]--,ttt=ttt/10;    if(t[0]==0)    {        int xx; for(int i=1;i<10;i++) {if(f[i]){ xx=i;break; }}        f[xx]--;  printf("%d",xx); int sz=0;        for(int i=0; i<10; i++)        {            if(f[i]==0) continue;            for(int j=0; j<f[i]; j++) num[sz][j]=i+0;            sz++;        }        bool ff=0;        for(int i=0;i<sz;i++)        {            if(ff==1) printf("%s",num[i]);            else            {                char h1[maxn],h2[maxn]; h1[0]=h2[0]=0;                strcpy(h1,num[i]); strcat(h1,t);                strcpy(h2,t); strcat(h2,num[i]);                if(num[i][0]<t[0])  printf("%s",num[i]);                else if(strcmp(h1,h2)<0) printf("%s",num[i]);                else {  printf("%s%s",t,num[i]); ff=1; }            }        }        if(ff==0) printf("%s",t);        printf("\n");    }    else    {        int xx=-1; for(int i=1;i<10;i++) {if(f[i]){ xx=i;break; }}        if(xx==-1)        {            printf("%s",t);            for(int i=0;i<f[0];i++) printf("0"); printf("\n");        }        else if(xx>t[0]-0)        {            printf("%s",t);            for(int j=0;j<10;j++)                for(int i=0;i<f[j];i++) printf("%d",j);            printf("\n");        }        else if(xx==t[0]-0)        {            if(f[0]==0)            {                for(int i=0;i<f[xx];i++) tmp[i]=xx+0; tmp[f[xx]]=0;                char h1[maxn],h2[maxn]; h1[0]=h2[0]=0;                strcpy(h1,t); strcat(h1,tmp);                strcpy(h2,tmp); strcat(h2,t);                if(strcmp(h1,h2)<0) strcpy(ans,h1);                else strcpy(ans,h2);                int tt=strlen(ans);                for(int i=xx+1;i<10;i++)                    for(int j=0;j<f[i];j++)                        ans[tt++]=i+0;                ans[tt]=0;                printf("%s\n",ans);            }            else            {                tmp1[0]=tmp2[0]=0;                strcpy(tmp1,t); int tt=strlen(tmp1);                for(int i=0;i<f[0];i++) tmp1[tt++]=0+0;                for(int i=xx;i<10;i++)                    for(int j=0;j<f[i];j++)                        tmp1[tt++]=(i+0);                tmp1[tt]=0;                tmp2[0]=xx+0; f[xx]--; tt=1;                for(int i=0;i<f[0];i++) tmp2[tt++]=(0+0); tmp2[tt]=0;                for(int i=0;i<f[xx];i++) tmp[i]=xx+0; tmp[f[xx]]=0;                char h1[maxn],h2[maxn]; h1[0]=h2[0]=0;                strcpy(h1,t); strcat(h1,tmp);                strcpy(h2,tmp); strcat(h2,t);                if(strcmp(h1,h2)<0) strcat(tmp2,h1);                else strcat(tmp2,h2);                tt=strlen(tmp2);                for(int i=xx+1;i<10;i++)                    for(int j=0;j<f[i];j++)                        tmp2[tt++]=i+0;                tmp2[tt]=0;                if(strcmp(tmp1,tmp2)>0) printf("%s\n",tmp2);                else printf("%s\n",tmp1);            }        }        else        {            f[xx]--;  printf("%d",xx); int sz=0;            for(int i=0; i<10; i++)            {                if(f[i]==0) continue;                for(int j=0; j<f[i]; j++) num[sz][j]=i+0;                num[sz][f[i]]=0;                sz++;            }            bool ff=0;            for(int i=0;i<sz;i++)            {                if(ff==1) printf("%s",num[i]);                else                {                    char h1[maxn],h2[maxn]; h1[0]=h2[0]=0;                    strcpy(h1,num[i]); strcat(h1,t);                    strcpy(h2,t); strcat(h2,num[i]);                    if(num[i][0]<t[0])  printf("%s",num[i]);                    else if(strcmp(h1,h2)<0) printf("%s",num[i]);                    else {  printf("%s%s",t,num[i]); ff=1; }                }            }            if(ff==0) printf("%s",t);            printf("\n");        }    }    return 0;}

 

CodeForces 670F Restore a Number