首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。