自动搬运

查看原文

来自洛谷，原作者为

	冒泡的笨小猴 就算前进的路再苦，也比站在原地更接近幸福

搬运于2025-08-24 21:25:54，当前版本为作者最后更新于2020-01-21 11:14:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题实在是太麻烦了！！高精度+枚举+字符串处理+AC，相当综合的一道题目！！！！！

首先，一种很显然的方法，就是枚举长度，之后枚举首位，之后判断这种情况是否满足。理论上，这个题已经做出来了，但是事实上，这个题99%在与细节！！

先说明一下我的判断方法，假设读入的长度是k，那么最终这个串所在的位置的那个数不会超过k位（除非k位全是0），于是对于确定的开始点和长度，前后扫描把这个数弄出来，之后在判断即可。

关于计算位数，这个也非常的讲究。根据WC2009高逸涵大牛的论文指示，一切从简单做起，分类讨论。详见下面的注意事项。

有以下几点注意：

1． 如果这个数后面的位数不够，比如98999，这个数出现在999处，后面的位数不够，要到前面找，此时得出这个数是998+1=999。但是，如果是99999，那么他会判断成99999+1，无法判断正确！！也就是说，如果后面的位数不够，前面的还全是9的话，就要对后面的数减1在加上前面的。比如99999，就是（9-1）+9999=89999，这个就对了。这一点如果不注意的话就得不出999999999--7988888882的解了。

2． 如果读入的数全是0，就在最前面加一个1，最后输出的时候在加对答案1即可。

3． 如果在判断的时候那个数多了一位，注意循环的次数。比如9991000，第一次是999，第二次是1000，我开始的程序始终是循环3次，就是最开始的长度，于是就有4个点WA。

4． 初始的时候答案设为无穷大，逐渐缩小。这个无穷大一定要大于200位，设成300肯定没问题。我开始设成200位，结果200个0和9的两个点WA了。

5． 关于计算位数。我开始是直接把小于这个位数的所有数的总长度*这一位是几累加的。后来发现，有两个问题。第一，如果是有首位的，这个长度就变了。比如，12345（5位），如果是在10之后的，就是0102030405（10位），这个一定要特殊判断。第二，你不感觉刚才的计算少了什么么？对！就是0！如果正常的这么算，100以上的时候，把100的两个0丢了，200的也没了……于是全盘错误……关于这个问题，是可以跟上一个问题一起解决的，详情就是特殊判断！

最后上代码（不要抄哦）

#include<iostream>
#include<string>
using namespace std;

string s;

int a[300][305]={0};
int flag=1;
int kk=0;  
//x[0~(n-m)]=s[n~m] 
int getNum(int x[],int m,int n){
    for(int i=n;i>=m;--i)
    x[n-i]=s[i]-'0';
    }
void print(int x[]){
     int i;
     for(i=300;i>=0;i--)
     if(x[i]!=0) break;
     while(i>=0) cout<<x[i--];
     cout<<endl;
     }
//打印补齐后的第一个数 
void print(int l){
     for(int i=1;i<=l;++i)
     cout<<s[i];
     cout<<endl;
     }
//x=x+t 
void add(int x[],int t){
     x[0]+=t;
     int i=0;
     while(x[i]>=10)
     {
       x[i+1]+=x[i]/10;
       x[i]%=10;
       i++;
                   }
     }
//x=x-t 
void sub(int x[],int t){
     x[0]-=t;
     int i=0;
     while(x[i]<0)
     {
       x[i]+=10;
       x[i-1]-=1;
       i++;
                   }
     }

//前后数位数都足够 
bool check(int i,int j,int m,int n){
     if(s[i]=='0'||s[m]=='0') return false;
     int x[305]={0},y[305]={0};
     getNum(x,i,j);
     getNum(y,m,n);
     add(x,1);
     for(int d=0;d<=300;d++)
     if(x[d]!=y[d]) return false;
     return true;
     }


//后一个数位数不够，只判断后一个数与前一个数对应的位数是否相等 
bool tailCheck(int i,int j,int m,int n){
     if(s[i]=='0'||s[m]=='0') return false;
     int x[305]={0},y[305]={0};
     getNum(x,i,j);
     getNum(y,m,n);
     add(x,1);
     int d1=300,d2=300;
     while(x[d1]==0) d1--;
     while(y[d2]==0) d2--;
     while(d1>=0&&d2>=0)
     {
        if(x[d1]!=y[d2]) return false;        
        d1--;d2--;        
                        }
     return true;
     }


//判断第一个数的位数是否能为l 
bool find(int l){
     int i,j,m,n;
     i=1;j=l;m=j+1;n=j+l;
     if(j==s.size()-1&&s[i]=='0') return false;
     while(true)
     {
       if(j>=s.size()-1) return true;
       if(n>=s.size()-1) {n=s.size()-1;if(!tailCheck(i,j,m,n)) return false;}
       else if(!check(i,j,m,n))  //前一个数和后一个数的位数都为l 
       {
         if(!check(i,j,m,n+1))   //前一个数位数为l,后一个数位数为l+1              
         return false;              
         else {l+=1;n+=1;}  
                            }
       i=m;
       j=n;
       m=j+1;
       n=j+l; 
             
             }
     
     return true;
     }

void Multiply(int x[],int y){
     for(int i=0;i<=300;++i)
     x[i]*=y;
     
     for(int i=0;i<=300;++i)
     if(x[i]>9)
     {
        x[i+1]+=x[i]/10;
        x[i]%=10;
                  }
     }
void add(int x[],int y[]){
     for(int i=0;i<=300;++i)
     x[i]+=y[i];
     int i=0;
     while(x[i]>=10)
     {
       x[i+1]+=x[i]/10;
       x[i]%=10;
       i++;
                   }
     }

bool comp(int x[],int y[]){
     for(int i=300;i>=0;--i)
     if(x[i]<y[i]) return true;
     else if(x[i]>y[i]) return false;
     return false;
     }

void getAns(int finalAns[],int l,int k){
     int x[305]={0},ans[305]={0};
     getNum(x,1,l);
     x[l-1]-=1;
     Multiply(x,l);
     for(int i=0;i<=300;++i)
     ans[i]=a[l-1][i]+x[i];
     ans[0]+=1+k+kk;
     for(int i=0;i<=300;++i)
     if(ans[i]>9)
     {
          ans[i+1]+=ans[i]/10;
          ans[i]%=10;
                    }   
     
     if(flag==1||comp(ans,finalAns))
     for(int i=0;i<=300;++i)
     finalAns[i]=ans[i];
     }
//判断数组是否为1000....0000的形式 
bool Equal1000(int x[]){
     int tot=0;
     for(int i=0;i<=300;++i)
     if(x[i]!=0) tot++;
     if(tot>1) return false;
     return true;
     }

//判断字符串是否为全0 
bool Equal000(string s1){
     for(int i=0;i<s1.size();++i)
     if(s1[i]!='0') return false;
     return true;
     }

     
int main()
{ 
    //a[i]表示所有位数<=i的字符串长度和
    for(int i=1;i<=200;++i)
    {
      a[i][i-1]=9;
      Multiply(a[i],i);
      add(a[i],a[i-1]);
            }
    
    int finalAns[305]={0};
    flag=1;
    
    string s1;
    cin>>s1;
    
    //如果字符串=000...0,则在最前面加上0,令kk=1,最后的答案要减去kk
    if(Equal000(s1))
    {s1="1"+s1;kk=1;}
    
    //l为字符串中第一个数的位数
    //k表示字符串中第一个字符是第一个数的第K+1位，k<l
    for(int l=1;l<=s1.size();++l)
    for(int k=0;k<l;++k)
    {
       s=" "+s1;string s2="";
       if(k==0)
       {
          if(find(l))
             {getAns(finalAns,l,k);flag=0;}
               }
               
       //如果K!=0,则补齐第一个数的前k位 
       if(k!=0)
       {

          int x[305]={0};
          getNum(x,l-k+1,l-k+k);
          
          //1.直接把第l-k+1至l-k+k之间的数补齐第一个数的前k位  
          s2="";
          int i=k-1;
          while(i>=0) s2+=x[i--]+'0';
          s=" "+s2+s1;
          if(find(l))
          {getAns(finalAns,l,k);flag=0;}
          
          //2.如果第l-k+1至l-k+k之间数的形式是10....000,也可以用99....999补齐第一个数的前k位  
          if(Equal1000(x))
          {
             s2="";
             i=k-1;
             while(i>=0) {s2+='9';i--;}
             s=" "+s2+s1;
             if(find(l))
             {getAns(finalAns,l,k);flag=0;}
                          }
          //3.用第l-k+1至l-k+k之间的数减去1,补齐第一个数的前k位  
          sub(x,1);
          i=k-1;
          s2="";
          while(i>=0) s2+=x[i--]+'0';
          s=" "+s2+s1;
          if(find(l))
          {getAns(finalAns,l,k);flag=0;}
               
               } 
            
            }
    
    print(finalAns);        
                  
  //  system("pause");   
    } 

望管理大大通过