题解

120 条题解

  • 20
    @ 2009-06-15 15:49:33

    这个题实在是太麻烦了!!高精度+枚举+字符串处理+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的也没了……于是全盘错误……关于这个问题,是可以跟上一个问题一起解决的,详情就是特殊判断!

    附录:

    提供两组数据:

    Test27:200个0,ans:17988……88691.

    Test29:200个9,ans:19988……8891。

    PS:

    找我上面的改后,把以下四组过了,基本上就差不多了。

    21:15.

    78910111:7。

    000000000:8888888891.

    999999999:7988888882.

  • 2
    @ 2016-04-21 17:39:32

    重发一下刚刚的那个代码,,,为啥不可以删除自己提交的题解呢,,真是郁闷

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<sstream>
    
    using namespace std; 
    
    string hahawodabiao;
    
    string inttostring(int a){
        string b;
        stringstream ss;
        ss << a;
        ss >> b;
        return b;
    }
    
    void makestring(){
        for(int i = 1;i <= 150000; i++){
            hahawodabiao += inttostring(i);
        }
    }
    
    int main()
    {
        makestring();
        string a;
        cin>>a;
        cout<<hahawodabiao.find(a)+1;
        return 0;
    }
    
    • @ 2018-07-24 18:17:19

      令人窒息的操作

    • @ 2018-08-18 16:28:10

      可以改a

    • @ 2018-10-26 16:05:02

      好像不行了,我开到2e7就超时了,短了又wa

    • @ 2021-07-14 08:22:25
      #include<bits/stdc++.h>
      using namespace std; 
      string szc;
      string int2str(int a){
          string b;
          stringstream ss;
          ss<<a;
          ss>>b;
          return b;
      }
      int main(){
          string a;
          cin>>a;
          for(int i=1;i<=1e9+10;i++){
              szc+=int2str(i);
              if(scz.find(a)!=string::npos){
                  cout<<szc.find(a)+1;return 0;
              }
          }
          return 0;
      }
      

      改良版代码
      超时18个测试点

  • 1
    @ 2020-11-26 19:40:52
    #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");   
        } 
    
  • 1
    @ 2016-02-21 11:00:17
    import java.io.*;
    import java.util.*;
    import java.math.*;
    
    public class Main {
        static final int ms = 250;
        static BigInteger [] beginValue = new BigInteger[ms];
        static final BigInteger negOne = BigInteger.valueOf(-1);
        static final BigInteger nine = new BigInteger("9");
        static BigInteger [] rec = new BigInteger[ms];
        static BigInteger minLength = new BigInteger("0");
    //--------------------------------------------------------------------------//
        //取得后面一个数字.
        public static String getNextInt(String a){
            String t = new String("");
            int len = a.length(), v, m = 1;
            for (int i = len - 1; i >= 0; --i){
                char c = a.charAt(i);
                v = (int)(c - 48) + m;
                m = v / 10;
                v %= 10;
                t = (char)(v + 48) + t;
            }
            while (m > 0){
                v = m % 10;
                t = (char)(v + 48) + t;
                m /= 10;
            }
            return t;
        }
        //取得前一个数字
        public static String getFrontInt(String a){
            String t = new String("");
            int len = a.length(), v, m = 1;
            for (int i = len - 1; i >= 0; --i){
                char c = a.charAt(i);
                v = (int)(c - 48) - m;
                if (v < 0){
                    v += 10;
                    m = 1;
                } else {
                    m = 0;
                }
                
                if (!(0 == i && v == 0)){
                    t = (char)(v + 48) + t;
                }
            }
            if (t.length() == 0){
                t = "0";
            }
            return t;
        }
        //比较两个字符串看看是否相等:相等则返回共长,否则返回-1
        public static int isEqualString(String a, String line, int pos){
            int i;
            for (i = 0; i < a.length() && (pos + i) < line.length(); ++i){
                if (a.charAt(i) != line.charAt(pos + i)) {
                    return -1;
                }
            }
            return i;
        }
        //这里按长度从next的segSize开始比较.
        public static boolean stringCompareBySegSize(String next, int segSize){
            int beginPos = segSize, ret = 0, next_len = next.length();
            String head = next.substring(0, segSize);
            while (beginPos < next_len){
                String back = getNextInt(head);
                ret = isEqualString(back, next, beginPos);
                if (-1 == ret) {
                    return false;
                } else {
                    beginPos += ret;
                    head = back;
                }
            }
            return true;
        }
        //查看是否有进位
        public static boolean isCarryOut(String a){
            int len = a.length();
            for (int i = 0; i < len; ++i){
                if (a.charAt(i) != '9') return false;
            }
            return true;
        }
    //    --------------------------------------------------------------------------//
        //rec[]数组记录了每种长度的起始位置:比如两位起始于10,一位起始于1
        public static void genBeginPos(){
            BigInteger [] len = new BigInteger[ms];
            BigInteger ten = BigInteger.ONE;
            len[0] = BigInteger.ZERO;
            rec[0] = BigInteger.ZERO;
            rec[1] = BigInteger.ONE;
            for (int i = 1; i < ms; ++i){
                len[i] = nine.multiply(ten);
                beginValue[i] = ten;
                ten = ten.multiply(BigInteger.valueOf(10));
            }
            for (int i = 2; i < ms; ++i){
                rec[i] = rec[i-1].add(len[i-1].multiply(BigInteger.valueOf(i-1)));
            }
        }
        public static BigInteger getPos(String value){
            int len = value.length();
            BigInteger bValue = beginValue[len];
            BigInteger from = rec[len];
            BigInteger ret = (new BigInteger(value)).subtract(bValue);
            ret = ret.multiply(BigInteger.valueOf(len));
            ret = from.add(ret);
            return ret;
        }
        
        public static void setMinLength(BigInteger a){
            if (minLength.compareTo(negOne) == 0 || minLength.compareTo(a) > 0) {
                minLength = a;
            }
        }
        
        public static boolean isAllZero(String a){
            for (int i = 0; i < a.length(); ++i){
                if (a.charAt(i) != '0') return false;
            }
            return true;
        }
    
        public static void main(String[] args) throws Exception {
            genBeginPos();
            BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
            String line;
            while ((line = cin.readLine()) != null){
                if (isAllZero(line)) {
                    line = "1" + line;
                    BigInteger pos = getPos(line);
                    pos = pos.add(BigInteger.ONE);
                    System.out.println(pos.toString());
                    continue;
                }
    
                final int line_len = line.length();
                /**
                 * 分段时有如下考虑:(假设除头部head,余下部分为next).
                 * 注意在分段过程中next的开头不能是以0字符开头。
                 * 1、每段的长度都比字符串长度(len)要小
                 *         这里需要分两种情况处理。
                 *         A、头部不能取到分段长度:
                 *             这里又分两种情况:
                 *          a、next部分可以取到分段长度,这个易于处理,
                 *          b、next部分不可以取到分段长度,这个不易处理。
                 *         B、头部可以取到分段长度:比如111213,当分段长度为2时,头部可以取到11那么后面的数就顺理成章地推导下去了。
                 * 2、每个分段的长度为len,但是头部与尾部均不足len,拼起来才足够.
                 *         这里需要推导出头部的整个数字,比如99|15,按四位数分的话我们需要推出头部数为14[9915]00。从1499与1500中取了中间四位。
                 * 3、整数字符串就是一个数(相当于第二种情况中头部长度为len),不可拆分比如100, 1000,
                 *    这时也不可以以0做为开头。
                 */
                boolean have_find_min_length = false;
                int segSize = 1;
                minLength = negOne;
                for (segSize = 1; segSize < line_len; ++segSize){
                    String head = new String(""), next = new String("");
                    int head_len = 0, next_len = 0;
                    
                    minLength = negOne;
                    //Condition 1.A
                    for (int headSize = 1; headSize < segSize; ++headSize){
                        head = line.substring(0, headSize); head_len = head.length();
                        next = line.substring(headSize, line_len); next_len = next.length();
                        if (next_len > 0 && next.charAt(0) == '0') continue;
                        
                        if (next_len >= segSize){
                            //Condition 1.A.a
                            String value = next.substring(0, segSize);
                            String front = getFrontInt(value);
                            
                            //这里利用next[0~segSize)取得的front值与head进行比较
                            boolean ret = true;
                            for (int i = head.length() - 1, j = front.length() - 1;
                                    i >= 0 && j >= 0; --i, --j){
                                if (head.charAt(i) != front.charAt(j)){
                                    ret = false;
                                    break;
                                }
                            }
                            
                            if (false == ret){
                                //比较失败,直接进行下轮测试。
                                continue;
                            } else {
                                //比较成功,那么从next开始,向后比较。
                                boolean bNextEqualToSegmentSize = stringCompareBySegSize(next, segSize);
                                if (false == bNextEqualToSegmentSize){
                                    continue;
                                } else {
                                    //这里需要推出完整的头值。
                                    String beginValue = getFrontInt(value);
                                    BigInteger pos = getPos(beginValue);
                                    pos = pos.add(BigInteger.valueOf(beginValue.length() - head.length()));
                                    setMinLength(pos);
                                    //System.out.println("C 1.A.a Next larger than segSize: value = " + beginValue + " pos = " + pos.toString());
                                    //System.out.println("Segment Size = " + segSize);
                                }
                            }
                        } else {
                            //Condition 1.A.b
                            String front_head = next.substring(0, segSize - head_len);
                            boolean bCarryOut = isCarryOut(head);
                            
                            String front_part_value = "";
                            if (bCarryOut){
                                front_part_value = getFrontInt(front_head);
                            } else {
                                front_part_value = front_head;
                            }
                            
                            String frontValue = "";
                            if (front_part_value.compareTo("0") != 0){
                                frontValue = front_part_value + head;
                            } else {
                                frontValue = head;
                            }
                            
                            String NextValue = getNextInt(frontValue);
                            boolean bIsEqual = true;
                            for (int i = 0, j = 0; i < NextValue.length() && j < next_len; ++i, ++j){
                                if (NextValue.charAt(i) != next.charAt(j)){
                                    bIsEqual = false;
                                    break;
                                }
                            }
                            
                            if (bIsEqual){
                                String beginValue = frontValue;
                                BigInteger pos = getPos(beginValue);
                                pos = pos.add(BigInteger.valueOf(beginValue.length() - head.length()));
                                setMinLength(pos);
                                //System.out.println("C 1.A.b Next small than segSize: value = " + beginValue + " pos = " + pos.toString());
                                //System.out.println("Segment Size = " + segSize);
                            } else {
                                continue;
                            }
                        }
                    }
                    
                    //Condition 1.B
                    if (line.charAt(segSize) != '0' && line.charAt(0) != '0'){
                        boolean bHeadEqualToSegmentSize = stringCompareBySegSize(line, segSize);
                        if (bHeadEqualToSegmentSize){
                            String beginValue = line.substring(0, segSize);
                            BigInteger pos = getPos(beginValue);
                            setMinLength(pos);
                            //System.out.println("C1.B head equal to segSize: value = " + beginValue + " pos = " + pos.toString());
                        }
                    }
    
                    
                    if (minLength.compareTo(negOne) != 0){
                        have_find_min_length = true;
                        break;
                    }
                }
                
                
                //Condition 2
                if (true == have_find_min_length){
                    System.out.println(minLength.toString());
                    continue;
                }
                
                for (int headSize = 1; headSize < line_len && have_find_min_length == false; ++ headSize){
                    String head = line.substring(0, headSize); 
                    final int head_len = head.length();
                    String next = line.substring(headSize, line_len);
                    final int next_len = next.length();
                    if (next_len > 0 && next.charAt(0) == '0') continue;
                    
                    boolean bCarryOut = isCarryOut(head);
                    String beginValue = "";
                    if (bCarryOut) {
                        beginValue = getFrontInt(next) + head;
                    } else {
                        beginValue = next + head;
                    }
                    
                    BigInteger pos = getPos(beginValue);
                    pos = pos.add(BigInteger.valueOf(beginValue.length() - head.length()));
                    setMinLength(pos);
                    //System.out.println("C2 add equal to line_len: value = " + beginValue + " pos = " + pos.toString());
                    //System.out.println("Segment Size = " + line_len);
                }
                
                //Condition 3
                if (line_len  > 0 && line.charAt(0) != '0'){
                    String beginValue = line;
                    BigInteger pos = getPos(beginValue);
                    setMinLength(pos);
                    //System.out.println("C3 hole length: front = " + beginValue + " pos = " + pos.toString());
                    //System.out.println("Segment Size = " + line_len);
                }
                
                //最后的输出
                if (minLength.compareTo(negOne) != 0){
                    //System.out.println("Find min length");
                    System.out.println(minLength.toString());
                    continue;
                }
            }
        }
    }
    
  • 0
    @ 2021-07-19 21:54:21

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<sstream>

    using namespace std;

    string hahawodabiao;

    string inttostring(int a){
    string b;
    stringstream ss;
    ss << a;
    ss >> b;
    return b;
    }

    void makestring(){
    for(int i = 1;i <= 150000; i++){
    hahawodabiao += inttostring(i);
    }
    }

    int main()
    {
    makestring();
    string a;
    cin>>a;
    cout<<hahawodabiao.find(a)+1;
    return 0;
    }

  • 0
    @ 2020-06-15 20:55:28

    感觉没几个好的
    ```cpp
    #include <iostream>
    #include <cstring>
    #include <string>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    class BigNum{
    private:
    enum {blen=4,MAX=53,base=10000};
    int len;
    int a[MAX];
    public:
    explicit BigNum(int num=0);
    BigNum(const BigNum& b);
    BigNum(int x,int b);
    explicit BigNum(string num);
    BigNum operator+ (const BigNum& b)const;
    BigNum operator+ (const int b)const;
    BigNum operator- (const BigNum& b)const;
    BigNum operator- (const int b)const;
    BigNum operator* (const BigNum& b)const;
    BigNum operator* (const int b)const;
    const int& operatorconst;
    int& operator;
    bool operator< (const BigNum& b)const;
    bool operator> (const BigNum& b)const;
    bool operator== (const BigNum& b)const;
    bool operator!= (const BigNum& b)const;
    string toString()const;
    friend ostream& operator<< (ostream& os,const BigNum& a);
    };
    BigNum::BigNum(int num){
    if (num==0){
    len=0;
    memset(a,0,sizeof(a));
    return;
    }
    len=0;
    memset(a,0,sizeof(a));
    while (num>0){
    a[len++]=num%base;
    num/=base;
    }
    }
    BigNum::BigNum(int x,int b){ // x*10^b
    if (x==0){
    len=0;
    memset(a,0,sizeof(a));
    return;
    }
    len=(b+1)/blen+1;
    if ((b+1)%blen==0) len--;
    memset(a,0,sizeof(a));
    int i=b%blen,j=1;
    while (i>0){
    j*=10;
    i--;
    }
    a[len-1]=x*j;
    }
    BigNum::BigNum(string num){
    const int nn[blen]={1,10,100,1000};
    if (num==string(num.size(),'0')){
    len=0;
    memset(a,0,sizeof(a));
    return;
    }
    memset(a,0,sizeof(a));
    len=0;
    for (int i=0;i<int(num.size());i++){
    if (i%blen==0) len++;
    a[len-1]+=(num[num.size()-i-1]-'0')*nn[i%blen];
    }
    }
    BigNum::BigNum(const BigNum& b){
    len=b.len;
    memcpy(a,b.a,sizeof(b.a));
    }
    int& BigNum::operator[](int i){
    return a[i];
    }
    const int& BigNum::operator[](int i)const{
    return a[i];
    }
    BigNum BigNum::operator+(const BigNum& b)const{
    BigNum c=BigNum();
    int k=0;
    c.len=max(len,b.len);
    for (int i=0;i<c.len;i++){
    c[i]=(a[i]+b[i]+k)%base;
    k=(a[i]+b[i]+k)/base;
    }
    while (k>0){
    c[c.len++]=k%base;
    k/=base;
    }
    return c;
    }
    BigNum BigNum::operator+(const int b)const{
    BigNum c=*this;
    int i=0;
    c[0]+=b;
    while (c[i]>=base){
    c[i+1]+=c[i]/base;
    c[i]%=base;
    i++;
    }
    while (c[c.len]>0) c.len++;
    return c;
    }
    BigNum BigNum::operator-(const BigNum& b)const{ //ensure that a>b
    BigNum c=BigNum();
    c.len=max(len,b.len);
    int k=0;
    for (int i=0;i<len;i++)
    if (a[i]-b[i]-k>=0)
    c[i]=a[i]-b[i]-k;
    else{
    k++;
    c[i]=a[i]-b[i]+base;
    }
    while (c.len>0 && c[c.len-1]==0) c.len--;
    return c;
    }
    BigNum BigNum::operator-(const int b)const{
    BigNum c=*this;
    int i=0;
    c[i]-=b;
    while (c[i]<0){
    c[i+1]--;
    c[i]+=base;
    i++;
    }
    while (c.len>0 && c[c.len-1]==0) c.len--;
    return c;
    }
    BigNum BigNum::operator*(const BigNum& b)const{
    BigNum c=BigNum();
    c.len=0;
    int t;
    for (int j=0;j<b.len;j++)
    for (int i=0;i<len;i++){
    t=c[i+j]+a[i]*b[j];
    c[i+j]=t%base;
    c[i+j+1]+=t/base;
    if (c[i+j]>0) c.len=max(c.len,i+j);
    if (c[i+j+1]>0) c.len=max(c.len,i+j+1);
    }
    c.len++;
    return c;
    }
    BigNum BigNum::operator*(const int b)const{
    BigNum c=BigNum();
    c.len=len;
    int k=0;
    for (int i=0;i<len;i++){
    c[i]=(a[i]*b+k)%base;
    k=(a[i]*b+k)/base;
    }
    while (k>0){
    c[c.len++]=k%base;
    k/=base;
    }
    return c;
    }
    bool BigNum::operator< (const BigNum& b)const{
    if (len<b.len) return true;
    if (len>b.len) return false;
    for (int i=len-1;i>=0;i--)
    if (a[i]<b[i]) return true;
    else if (a[i]>b[i]) return false;
    return false;
    }
    bool BigNum::operator> (const BigNum& b)const{
    if (len>b.len) return true;
    if (len<b.len) return false;
    for (int i=len-1;i>=0;i--)
    if (a[i]>b[i]) return true;
    else if (a[i]<b[i]) return false;
    return false;
    }
    bool BigNum::operator== (const BigNum& b)const{
    if (len!=b.len) return false;
    for (int i=0;i<len;i++)
    if (a[i]!=b[i]) return false;
    return true;
    }
    bool BigNum::operator!= (const BigNum& b)const{
    return !(*this==b);
    }
    ostream& operator<< (ostream& os,const BigNum& a){
    int i=a.len-1;
    os << a[i];
    for (i-=1;i>=0;i--){
    if (a[i]<a.base/10) os << '0';
    if (a[i]<a.base/100) os << '0';
    if (a[i]<a.base/1000) os << '0';
    os << a[i];
    }
    return os;
    }
    string BigNum::toString()const{
    int i=len-1;
    char s[MAX*blen+1];
    sprintf(s,"%d",a[i]);
    for (i-=1;i>=0;i--)
    {
    if (a[i]<base/10) sprintf(s+strlen(s),"%d",0);
    if (a[i]<base/100) sprintf(s+strlen(s),"%d",0);
    if (a[i]<base/1000) sprintf(s+strlen(s),"%d",0);
    sprintf(s+strlen(s),"%d",a[i]);
    }
    return string(s,s+strlen(s));
    }
    BigNum cal(BigNum a){
    string s=a.toString();
    int x=s[0]-'0';
    int b=s.size();
    if (b==1) return BigNum(x);
    BigNum tmp;
    for (int i=0;i<b-1;i++)
    tmp=tmp+BigNum(9,i)*(i+1);
    tmp=tmp+(a-BigNum(1,b-1)+1)*b;
    return tmp;
    }
    int get(string s1,string s2){
    int i,ans=0;
    for (i=1;i<=int(min(s1.size(),s2.size()));i++){
    string ss1=s1.substr(0,i);
    string ss2=s2.substr(s2.size()-i,i);
    if (ss1==ss2) ans=i;
    }
    return ans;
    }
    int main(){
    //freopen("in.txt","r",stdin);
    int i,j,len,n,k,slen;
    bool ff;
    BigNum ans,tmp;
    string s,ss,st,sp,s1,s2;
    cin >> s;
    n=s.size();
    if (s==string(n,'0')){
    ans=cal(BigNum(1,n))-n+1;
    cout << ans << endl;
    return 0;
    }
    if (n==1){
    cout << s << endl;
    return 0;
    }
    for (len=1;len<n;len++)
    for (i=0;i+len-1<n;i++){
    j=i+len-1;
    if (j>=n) continue;
    ff=true;
    st=s.substr(i,len);
    if (st[0]=='0') continue;
    if (i>0){
    sp=(BigNum(st)-1).toString();
    ss=s.substr(0,i);
    if (ss.size()>sp.size()) continue;
    if (sp.rfind(ss)!=sp.size()-ss.size()) ff=false;
    }
    if (!ff) continue;
    slen=len;
    for (k=j+1;k+slen-1<n;k+=slen){
    st=(BigNum(st)+1).toString();
    slen=st.size();
    if (k+slen-1>=n) break;
    if (st!=s.substr(k,slen)){
    ff=false;
    break;
    }
    }
    if (!ff) continue;
    if (k<n){
    st=(BigNum(st)+1).toString();
    ss=s.substr(k,n-k);
    if (st.find(ss)!=0) ff=false;
    }
    if (ff){
    st=s.substr(i,len);
    ans=cal(BigNum(st))-i-st.size()+1;
    goto ppp;
    }
    }
    ppp:
    for (i=0;i<n;i++){
    st=s.substr(0,i);
    st=(BigNum("1"+st)+1).toString();
    st=st.substr(1,st.size()-1);
    s2=s.substr(i,n-i);
    k=get(st,s2);
    if (k>=int(s2.size())) continue;
    st=s.substr(i,n-i-k)+st;
    if (st[0]=='0') continue;
    tmp=cal(BigNum(st)-1)-i+1;
    if (ans==BigNum(0)) ans=tmp;
    else if (tmp<ans) ans=tmp;
    }
    if (s[0]>'0'){
    tmp=cal(BigNum(s))-n+1;
    if (ans==BigNum(0)) ans=tmp;
    else if (tmp<ans) ans=tmp;
    }
    else{
    s="1"+s;
    tmp=cal(BigNum(s))-n;
    if (ans==BigNum(0)) ans=tmp;
    else if (tmp<ans) ans=tmp;
    }
    cout<< ans << endl;
    }

  • 0
    @ 2018-05-19 19:20:56

    var a:string;
    s:array[1..1700000000] of char;
    b,c,d,e:longint;
    procedure fty(b:longint);
    var zh:string;
    begin
    str(b,zh);
    for c:=1+d to d+length(zh) do
    s[c]:=zh[c-d];
    d:=d+length(zh);
    end;

    begin
    readln(a);
    for b:=1 to 1000100 do fty(b);
    for b:=1 to length(s)-length(a)+1 do
    if s[b]=a[1] then
    for c:=b to length(a)+b-1 do
    begin
    if s[c]<>a[c-b+1] then break;
    if (c=length(a)+b-1) and (s[c]=a[c-b+1]) then begin
    writeln(b);exit;end;
    end;
    end.

    230分。。。烦。。。

  • 0
    @ 2017-11-10 13:24:38

    把第一个数根据后面的数分情况补齐,然后判断整个字符串是否合法

    #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");
        
        
    
        } 
    
    
  • 0
    @ 2017-04-01 10:52:33

    非常复杂的一道题……强行AC
    ```c++
    #include <string>
    #include <iostream>
    #include <set>
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    struct BigInt
    {
    static const int Base = 100000000;
    static const int Width = 8;
    vector <int> s;
    BigInt(long long num = 0)
    {
    *this = num;
    }
    BigInt(const string &b)
    {
    *this = b;
    }
    BigInt operator = (long long num)
    {
    s.clear();
    do
    {
    s.push_back(num % Base);
    num /= Base;
    } while (num > 0);
    return *this;
    }
    BigInt operator = (const string& str)
    {
    s.clear();
    int x, len = (str.length() - 1) / Width + 1;
    for (int i = 0; i < len; i++)
    {
    int end = str.length() - i * Width;
    int start = max(0, end - Width);
    sscanf(str.substr(start, end - start).c_str(), "%d", &x);
    s.push_back(x);
    }
    return *this;
    }
    BigInt operator + (const BigInt &b) const
    {
    BigInt res;
    res.s.clear();
    for (int i = 0, count = 0;; i++)
    {
    if (count == 0 && i >= s.size() && i >= b.s.size()) break;
    int x = count;
    if (i < s.size()) x += s[i];
    if (i < b.s.size()) x += b.s[i];
    res.s.push_back(x % Base);
    count = x / Base;
    }
    return res;
    }
    BigInt operator * (const int times) const
    {
    BigInt res;
    res.s.clear();
    for (int i = 0, carry = 0; ; i++)
    {
    if (carry == 0 && i >= s.size()) break;
    long long x = carry;
    if (i < s.size()) x += (long long)times * s[i];
    res.s.push_back(x % Base);
    carry = x / Base;
    }
    return res;
    }

    friend ostream& operator << (ostream &out, const BigInt& x)
    {
    out << x.s.back();
    for (int i = x.s.size() - 2; i >= 0; i--)
    {
    char buf[20];
    sprintf(buf, "%08d", x.s[i]);
    for (int j = 0; j < strlen(buf); j++) out << buf[j];
    }
    return out;
    }
    };

    void find_bit(string num,int blank)
    {
    int size = num.size();
    BigInt ans = 1, count = 9;
    for (int i = 1; i < size; i++)
    {
    ans = ans + (count * i);
    count = count * 10;
    }

    if (num[0] > '0')num[0]--;
    if (num[0]=='0' && num !="0") num.erase(num.begin());

    ans = ans + BigInt(num) * size;

    ans = ans + BigInt(blank);

    cout << ans << endl;
    }
    struct node
    {
    string num;
    int blank;
    node(string num, int blank):num(num),blank(blank){
    }
    bool operator < (const node &b)const
    {
    if (num.size() < b.num.size()) return true;
    if (num.size() > b.num.size()) return false;
    if (num < b.num) return true;
    if (num > b.num) return false;
    if (blank < b.blank) return true;
    return false;
    }
    };

    set <node> ansSet;
    string& operator ++ (string &a)
    {
    int size = a.size();
    int carry = 1;
    for (int i = size - 1; i>=0; i--)
    {
    int x = carry + a[i] - '0';
    a[i] = x % 10 + '0';
    carry = x/10;

    }
    if (carry > 0)
    {
    a = "1";
    for (int i=0; i < size; i++) a+="0";
    }
    return a;
    }

    string& operator -- (string &a)
    {
    int size = a.size();
    int carry = -1;
    for (int i = size - 1; i >= 0; i--)
    {
    int x = carry + a[i] - '0';
    carry = 0;
    if (x < 0)
    {
    carry = -1;
    x += 10;
    }
    a[i] = x + '0';
    }
    if (a[0] == '0' && a.size()!=1) a.erase(0,1);
    return a;
    }

    bool check(string &a, string &b,int pos = 0, int blank = 0)
    {
    for (int i = 0, j = pos + blank;i < a.size() && j < b.size(); i++,j++)
    {
    if (a[i] != b[j]) return false;
    }
    return true;
    }

    bool check_through(string a,string &b, int pos)
    {
    for (;pos < b.size(); pos += a.size())
    {
    ++a;
    if (!check(a,b,pos)) return false;
    }
    return true;
    }

    bool all(string &a,char c)
    {
    for (int i = 0; i < a.size(); i++)
    if (a[i]!=c) return false;
    return true;
    }
    int main()
    {
    string s;
    cin >> s;
    if (all(s,'0'))
    {
    s = "1" +s;
    find_bit(s,1);
    }
    else for (int len = 1; len <= s.size(); len++)
    {
    ansSet.clear();
    for (int blank = 0; blank < len; blank++)
    {
    string a,num="";
    a.assign(s,0,len-blank);
    int p = len - blank;
    if (all(a,'9'))
    {
    string zero;
    zero.assign(len - blank, '0');
    string temp = "1";//1000000000
    temp.append(len, '0');
    if (check(temp,s,p))
    {
    num.assign(len, '9');
    }
    else if (s[p]!='0'&&check(zero,s,p,blank))
    {
    num.assign(s,p,blank);
    --num;
    num += a;
    }
    }
    else
    {
    string temp = a;
    ++temp;
    if (s[p]!='0'&&check(temp,s,p,blank))
    {
    num.assign(s,p,blank);
    num += a;
    }
    }
    /* test
    printf("len = %d, blank = %d, p = %d, num=",len,blank,p);
    cout << num << endl;
    // test*/

    if (num != "" && num[0]!='0'&& check_through(num,s,p))
    ansSet.insert(node(num,blank));
    }
    if (!ansSet.empty())
    {
    // cout << ansSet.begin()->num << endl;
    string num = ansSet.begin()->num;
    int blank = ansSet.begin()->blank;
    if (all(num,'0')){
    num = "1" +num;
    blank = 1;
    }
    find_bit(num,blank);

    break;
    }
    }
    }
    ```

  • 0
    @ 2016-11-26 21:42:06

    很复杂,基本上都是需要高精度。不明白为什么这样的题老是要搞高精度。我觉得思路更重要些。
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    void inc(int iArr, int num) {
    iArr[1] += num;
    if(iArr[0] == 0) iArr[0] = 1;
    iArr[iArr[0]+1] = 0;
    for(int i=1;i<=iArr[0];i++) {
    if(iArr[i] >= 10) {
    iArr[i] -= 10;
    iArr[i+1]++;
    } else break;
    }
    if(iArr[iArr[0]+1] != 0) iArr[0]++;
    }
    bool match(char
    cArr, int cALen, int init_len, int* tArr) {
    if(cALen > 0 && cArr[0] == '0') return false;
    if(cALen <= init_len) return true;
    tArr[0] = init_len;
    int i,j;
    for(i=1;i<=init_len;i++) tArr[i] = cArr[init_len - i] - '0';
    int sIndex = init_len;
    do {
    inc(tArr, 1);
    if(sIndex + tArr[0] <= cALen) {
    for(i=1;i<=tArr[0];i++)
    if(tArr[i] != cArr[sIndex + tArr[0] - i] - '0') return false;
    sIndex += tArr[0];
    } else {
    if(sIndex < cALen) {
    i = tArr[0];
    while(sIndex < cALen) {
    if(tArr[i] != cArr[sIndex] - '0') return false;
    i--;
    sIndex++;
    }
    return true;
    } else return true;
    }
    } while(1);
    }
    #define MAX 210
    int minNum[MAX];
    int bestSkip;
    int arr1[MAX], arr2[MAX], arr3[MAX], result[MAX];
    void time(int a,int num, int b) {// b= a*num
    int i;
    int len = a[0];
    memset(b+len+1,0,sizeof(int) * (MAX - (len+1)));
    for(i=1;i<=a[0];i++) {
    b[i] = a[i] * num;
    }
    for(i=1;i<=a[0] || b[i] != 0;i++) {
    if(b[i] >= 10) {
    b[i+1] += b[i] / 10;
    b[i] %= 10;
    }
    }
    b[0] = i-1;
    }
    void add(int *a,int *b) {
    int len = a[0] > b[0] ? a[0] : b[0];
    for(int i=1;i<=len;i++)
    a[i] += b[i];
    for(int i=1;i<=len;i++) {
    if(a[i] >= 10) {
    a[i] -= 10;
    a[i+1]++;
    }
    }
    if(a[len+1] != 0) len++;
    a[0] = len;
    }
    void minus(int *a,int *b) {
    for(int i=b[0];i>=1;i--)
    a[i] -= b[i];
    for(int i=1;i<=a[0];i++) {
    if(a[i] < 0) {
    a[i] += 10;
    a[i+1]--;
    }
    }
    int len = a[0];
    while(len>0 && a[len] == 0) len--;
    a[0] = len;
    }
    bool smaller(int a,int b) { // return a < b
    if(a[0] < b[0]) return true;
    else if(a[0] > b[0]) return false;
    int len = a[0];
    for(int i=len;i>=1;i--) {
    if(a[i] < b[i]) return true;
    else if(a[i] > b[i]) return false;
    }
    return false;
    }
    void calcFinalResult(int iArr,int oArr,int *tArr1, int tArr2, int tArr3) {
    memset(tArr1, 0, sizeof(int) * MAX);
    memset(tArr2, 0, sizeof(int) * MAX);
    memset(tArr3, 0, sizeof(int) * MAX);
    memset(oArr, 0, sizeof(int) * MAX);
    tArr2[0] = 1; tArr2[1] = 9;
    int len;
    for(len = 1;len < iArr[0]; len++) {
    time(tArr2, len, tArr3);
    add(oArr, tArr3);
    time(tArr2, 10, tArr2);
    }
    iArr[iArr[0]]--;
    if(iArr[iArr[0]] == 0) iArr[0]--;
    inc(iArr,1);
    time(iArr, len, tArr3);
    add(oArr, tArr3);
    }
    void copyNum(int *a, int * b){ // a = b
    a[0] = b[0];
    for(int i=1;i<=b[0];i++) {
    a[i] = b[i];
    }
    }
    void copyNum(char* buf, int *oArr, int len) {
    oArr[0] = len;
    for(int i=1;i<=len;i++) {
    oArr[i] = buf[len-i] - '0';
    }
    }
    void print(int *a) {
    if(a[0] == 0) putchar('0');
    else {
    for(int i=a[0];i>=1;i--) putchar(a[i]+'0');
    }
    }

    int* main23(char* buf)
    {
    memset(arr1, 0, sizeof(int) * MAX);
    memset(arr2, 0, sizeof(int) * MAX);
    memset(arr3, 0, sizeof(int) * MAX);
    memset(minNum, 0, sizeof(int) * MAX);
    memset(result, 0, sizeof(int) * MAX);
    //char buf[MAX]; gets(buf);
    int bLen = strlen(buf);
    bool allZero;
    bool found = false;
    int i;
    for(i=0;i<bLen;i++) if(buf[i] != '0') break;
    if(i>=bLen) allZero = true;
    else allZero = false;

    if(allZero) {
    minNum[0] = bLen+1;
    minNum[bLen+1] = 1;
    bestSkip = 1;
    } else {
    for(i=1;i<=bLen;i++) {
    if(match(buf, bLen, i, arr1)) {
    found = true;
    copyNum(buf, minNum, i);
    bestSkip = 0;
    }
    for(int skip=1;skip<i;skip++) {
    copyNum(buf, arr1, i-skip);
    int sIndex = i-skip;
    inc(arr1,1);
    int j;
    for(j=1;j<=i-skip;j++) {
    if(sIndex+i-j < bLen && arr1[j] != buf[sIndex+i-j] - '0') break;
    }
    if(j>i-skip) {
    if(match(buf+sIndex,bLen-sIndex,i,arr2)) {
    //copyNum(buf+sIndex, arr1, i);
    arr1[0] = i;
    for(j=i;j>i-skip;j--) arr1[j] = buf[sIndex + i - j] - '0';
    if(arr1[arr1[0]] != 0) {
    arr2[0] = 1; arr2[1] = 1;
    minus(arr1, arr2);
    if(!found || smaller(arr1,minNum)) {
    copyNum(minNum, arr1);
    bestSkip = minNum[0] - (i-skip);
    }
    found = true;
    }
    }
    }
    }
    if(found) break;
    }
    }

    //printf("minNum:"); print(minNum); printf("\n");
    int minNumLen = minNum[0];
    calcFinalResult(minNum, result, arr1, arr2, arr3);
    //printf("result:"); print(result); printf("\n");
    memset(arr1, 0, sizeof(int) * MAX);
    i = 1;
    bestSkip = minNumLen - bestSkip-1;
    while(bestSkip != 0) {
    arr1[i] = bestSkip % 10;
    bestSkip /= 10;
    i++;
    }
    arr1[0] = i-1;
    minus(result, arr1);
    return result;
    //print(result);
    //return 0;
    }

    char* testArr;
    int getPos(char* inC) {
    char * p = strstr(testArr, inC);
    if(p == NULL) {
    return -1;
    } else {
    return p - testArr + 1;
    }
    }
    int getAns(char* inC) {
    int * r = main23(inC);
    int sum = 0;
    for(int i=r[0];i>=1;i--) {
    sum *= 10;
    sum += r[i];
    }
    return sum;
    }

    void non_debug() {
    char buf[MAX]; gets(buf);
    print(main23(buf));
    }
    #define DEBUG 0
    int main() {
    //printf("%d",getAns("01"));
    //return 0;
    if(DEBUG) {
    #define MAX_TEST 100000000
    testArr = new char[MAX_TEST];
    int* testInt = new int[MAX];
    testInt[0] = 1; testInt[1] = 1;
    for(int i=0;i<MAX_TEST;) {
    for(int j=testInt[0];j>=1;j--)
    if(i<MAX_TEST) testArr[i++] = testInt[j] + '0';
    inc(testInt, 1);
    }
    memset(testInt, 0 , sizeof(int) * MAX);
    testInt[0] = 10;
    char iABuf[MAX]; memset(iABuf, 0, sizeof(iABuf));
    for(int wei=1;wei<10;wei++) {
    iABuf[wei] = '\0';
    while(testInt[wei+1] == 0) {
    for(int j=wei;j>=1;j--) iABuf[wei-j] = testInt[j] + '0';
    int rightAns = getPos(iABuf);
    int leftAns;
    if(rightAns != -1 && (leftAns = getAns(iABuf)) != rightAns) {
    printf("wrong str:%s\n",iABuf);
    printf("l:%d, r:%d",leftAns, rightAns);
    getchar();
    } else {
    printf("%s right.\n", iABuf);
    }
    inc(testInt, 1);
    }
    memset(testInt, 0 , sizeof(int) * MAX);
    testInt[0] = 10;
    }
    //printf("%d",getAns("010000001100000021000"));
    return 0;
    } else {
    non_debug();
    }

    return 0;
    }

    Accepted, time = 60 ms, mem = 516 KiB, score = 400

  • 0
    @ 2016-10-15 22:41:00

    测试数据 #0: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 3388 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #8: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
    测试数据 #9: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #10: Accepted, time = 15 ms, mem = 3396 KiB, score = 10
    测试数据 #11: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
    测试数据 #12: WrongAnswer, time = 15 ms, mem = 3392 KiB, score = 0
    测试数据 #13: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #14: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #15: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #16: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
    测试数据 #17: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #18: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
    测试数据 #19: Accepted, time = 0 ms, mem = 3396 KiB, score = 10
    测试数据 #20: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #21: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
    测试数据 #22: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
    测试数据 #23: WrongAnswer, time = 15 ms, mem = 3392 KiB, score = 0
    测试数据 #24: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
    测试数据 #25: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
    测试数据 #26: WrongAnswer, time = 15 ms, mem = 3384 KiB, score = 0
    测试数据 #27: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
    测试数据 #28: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
    测试数据 #29: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
    测试数据 #30: WrongAnswer, time = 15 ms, mem = 3384 KiB, score = 0
    测试数据 #31: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
    测试数据 #32: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
    测试数据 #33: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
    测试数据 #34: WrongAnswer, time = 15 ms, mem = 3392 KiB, score = 0
    测试数据 #35: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    测试数据 #36: WrongAnswer, time = 0 ms, mem = 3384 KiB, score = 0
    测试数据 #37: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
    测试数据 #38: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
    测试数据 #39: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
    WrongAnswer, time = 375 ms, mem = 3396 KiB, score = 220
    代码
    #include<bits/stdc++.h>
    using namespace std;
    char a[200001],b[200];
    string s;
    int i,p[200],j,n,m;
    int makea(int num,int x) {
    string s1;
    int k,t,i;
    t=0;
    k=num;
    while (k>0) {
    t++;
    s1[t]=k%10+'0';
    k=k/10;
    }
    for (i=t; i>0; i--)
    a[x+t-i]=s1[i];
    n=x+t;
    if (n<200000)
    makea(num+1,n);
    }
    int main() {
    cin>>s;
    for (i=1; i<=s.length(); i++)
    b[i]=s[i-1];
    m=s.length();
    n=1;
    makea(1,n);
    j=0;
    p[1]=0;
    for (i=2; i<=m; i++) {
    while (j>0&&b[j+1]!=b[i]) j=p[j];
    if (b[j+1]==b[i]) j++;
    p[i]=j;
    }
    j=0;
    for (i=1; i<=n; i++) {
    while (j>0&&b[j+1]!=a[i]) j=p[j];
    if (b[j+1]==a[i]) j++;
    if (j==m) {
    cout<<i-m+1<<endl;
    break;
    }
    }
    }
    这就是裸地KMP的死法。。。22个点,不然就爆了。。。

  • 0
    @ 2016-09-03 19:27:15

    //算是打表吧!
    #include<stdio.h>
    #include<iostream>
    #include<string.h>
    #include<string>
    using namespace std;

    void makenext(const char p[],int next[])//不理解就自己代一代
    {
    int q,k;
    int m=strlen(p);
    next[0]=0;
    for(q=1,k=0;q<m;++q)
    {
    while(k>0&&p[q]!=p[k])
    k=next[k-1];
    if(p[q]==p[k])
    {
    k++;//查找与前面有相同的,即前后缀有相同的元素,于是就加1
    }
    next[q]=k;
    }
    }

    int kmp(const char t[],const char p[],int next[])
    {
    int n,m;
    int i,q;
    n=strlen(t);
    m=strlen(p);
    makenext(p,next);
    for(i=0,q=0;i<n;++i)
    {
    while(q>0&&p[q]!=t[i])
    q=next[q-1];
    if(p[q]==t[i])
    {
    q++;
    }

    if(q==m)
    printf("%d\n",(i-m+2));
    }
    }

    int main()
    {
    int next[20]={0};
    char T[300]={
    49,50,51,52,53,54,55,56,57,49,48,49,49,49,50,49,51,49,52,
    49,53,49,54,49,55,49,56,49,57,50,48,50,49,50,50,50,51,50,
    52,50,53,50,54,50,55,50,56,50,57,51,48,51,49,51,50,51,51,
    51,52,51,53,51,54,51,55,51,56,51,57,
    52,48,52,49,52,50,52,51,52,52,52,53,52,54,52,55,52,56,52,57,
    53,48,53,49,53,50,53,51,53,52,53,53,53,54,53,55,53,56,53,57,
    54,48,54,49,54,50,54,51,54,52,54,53,54,54,54,55,54,56,54,57,
    55,48,55,49,55,50,55,51,55,52,55,53,55,54,55,55,55,56,53,57,
    };
    char P[30];
    cin.getline(P,30);
    int l=strlen(P);
    //for(int i=0;i<l;i++)printf("%d ",P[i]);
    kmp(T,P,next);
    return 0;
    }

  • 0
    @ 2016-07-13 14:26:14

    暴力做法:只能过22个点
    ~~~
    #include <iostream>
    #include <string>
    #include <sstream>
    using namespace std;
    string A,s,t;
    int main(){
    for(int i=1;i<=10000;i++){
    stringstream ss;
    ss<<i;ss>>t;s+=t;
    }
    getline(cin,A);
    cout<<s.find(A)+1<<endl;
    return 0;
    }


    发几个c++的参考代码膜拜一下。Orz。

    #include <iostream>
    #include <cstring>
    #include <string>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    class BigNum{
    private:
        enum {blen=4,MAX=53,base=10000};
        int len;
        int a[MAX];
    public:
        explicit BigNum(int num=0);
        BigNum(const BigNum& b);
        BigNum(int x,int b);
        explicit BigNum(string num);
        BigNum operator+ (const BigNum& b)const;
        BigNum operator+ (const int b)const;
        BigNum operator- (const BigNum& b)const;
        BigNum operator- (const int b)const;
        BigNum operator* (const BigNum& b)const;
        BigNum operator* (const int b)const;
        const int& operator[] (int i)const;
        int& operator[] (int i);
        bool operator< (const BigNum& b)const;
        bool operator> (const BigNum& b)const;
        bool operator== (const BigNum& b)const;
        bool operator!= (const BigNum& b)const;
        string toString()const;
        friend ostream& operator<< (ostream& os,const BigNum& a);
    };
    BigNum::BigNum(int num){
        if (num==0){
            len=0;
            memset(a,0,sizeof(a));
            return;
        }
        len=0;
        memset(a,0,sizeof(a));
        while (num>0){
            a[len++]=num%base;
            num/=base;
        }
    }
    BigNum::BigNum(int x,int b){ // x*10^b
        if (x==0){
            len=0;
            memset(a,0,sizeof(a));
            return;
        }
        len=(b+1)/blen+1;
        if ((b+1)%blen==0) len--;
        memset(a,0,sizeof(a));
        int i=b%blen,j=1;
        while (i>0){
            j*=10;
            i--;
        }
        a[len-1]=x*j;
    }
    BigNum::BigNum(string num){
        const int nn[blen]={1,10,100,1000};
        if (num==string(num.size(),'0')){
            len=0;
            memset(a,0,sizeof(a));
            return;
        }
        memset(a,0,sizeof(a));
        len=0;
        for (int i=0;i<int(num.size());i++){
            if (i%blen==0) len++;
            a[len-1]+=(num[num.size()-i-1]-'0')*nn[i%blen];
        }
    }
    BigNum::BigNum(const BigNum& b){
        len=b.len;
        memcpy(a,b.a,sizeof(b.a));
    }
    int& BigNum::operator[](int i){
        return a[i];
    }
    const int& BigNum::operator[](int i)const{
        return a[i];
    }
    BigNum BigNum::operator+(const BigNum& b)const{
        BigNum c=BigNum();
        int k=0;
        c.len=max(len,b.len);
        for (int i=0;i<c.len;i++){
            c[i]=(a[i]+b[i]+k)%base;
            k=(a[i]+b[i]+k)/base;
        }
        while (k>0){
            c[c.len++]=k%base;
            k/=base;
        }
        return c;
    }
    BigNum BigNum::operator+(const int b)const{
        BigNum c=*this;
        int i=0;
        c[0]+=b;
        while (c[i]>=base){
            c[i+1]+=c[i]/base;
            c[i]%=base;
            i++;
        }
        while (c[c.len]>0) c.len++;
        return c;
    }
    BigNum BigNum::operator-(const BigNum& b)const{ //ensure that a>b
        BigNum c=BigNum();
        c.len=max(len,b.len);
        int k=0;
        for (int i=0;i<len;i++)
            if (a[i]-b[i]-k>=0)
                c[i]=a[i]-b[i]-k;
            else{
                k++;
                c[i]=a[i]-b[i]+base;
            }
        while (c.len>0 && c[c.len-1]==0) c.len--;
        return c;
    }
    BigNum BigNum::operator-(const int b)const{
        BigNum c=*this;
        int i=0;
        c[i]-=b;
        while (c[i]<0){
            c[i+1]--;
            c[i]+=base;
            i++;
        }
        while (c.len>0 && c[c.len-1]==0) c.len--;
        return c;
    }
    BigNum BigNum::operator*(const BigNum& b)const{
        BigNum c=BigNum();
        c.len=0;
        int t;
        for (int j=0;j<b.len;j++)
            for (int i=0;i<len;i++){
                t=c[i+j]+a[i]*b[j];
                c[i+j]=t%base;
                c[i+j+1]+=t/base;
                if (c[i+j]>0) c.len=max(c.len,i+j);
                if (c[i+j+1]>0) c.len=max(c.len,i+j+1);
            }
        c.len++;
        return c;
    }
    BigNum BigNum::operator*(const int b)const{
        BigNum c=BigNum();
        c.len=len;
        int k=0;
        for (int i=0;i<len;i++){
            c[i]=(a[i]*b+k)%base;
            k=(a[i]*b+k)/base;
        }
        while (k>0){
            c[c.len++]=k%base;
            k/=base;
        }
        return c;
    }
    bool BigNum::operator< (const BigNum& b)const{
        if (len<b.len) return true;
        if (len>b.len) return false;
        for (int i=len-1;i>=0;i--)
            if (a[i]<b[i]) return true;
            else if (a[i]>b[i]) return false;
        return false;
    }
    bool BigNum::operator> (const BigNum& b)const{
        if (len>b.len) return true;
        if (len<b.len) return false;
        for (int i=len-1;i>=0;i--)
            if (a[i]>b[i]) return true;
            else if (a[i]<b[i]) return false;
        return false;
    }
    bool BigNum::operator== (const BigNum& b)const{
        if (len!=b.len) return false;
        for (int i=0;i<len;i++)
            if (a[i]!=b[i]) return false;
        return true;
    }
    bool BigNum::operator!= (const BigNum& b)const{
        return !(*this==b);
    }
    ostream& operator<< (ostream& os,const BigNum& a){
        int i=a.len-1;
        os << a[i];
        for (i-=1;i>=0;i--){
            if (a[i]<a.base/10) os << '0';
            if (a[i]<a.base/100) os << '0';
            if (a[i]<a.base/1000) os << '0';
            os << a[i];
        }
        return os;
    }
    string BigNum::toString()const{
        int i=len-1;
        char s[MAX*blen+1];
        sprintf(s,"%d",a[i]);
        for (i-=1;i>=0;i--)
        {
            if (a[i]<base/10) sprintf(s+strlen(s),"%d",0);
            if (a[i]<base/100) sprintf(s+strlen(s),"%d",0);
            if (a[i]<base/1000) sprintf(s+strlen(s),"%d",0);
            sprintf(s+strlen(s),"%d",a[i]);
        }
        return string(s,s+strlen(s));
    }
    BigNum cal(BigNum a){
        string s=a.toString();
        int x=s[0]-'0';
        int b=s.size();
        if (b==1) return BigNum(x);
        BigNum tmp;
        for (int i=0;i<b-1;i++)
            tmp=tmp+BigNum(9,i)*(i+1);
        tmp=tmp+(a-BigNum(1,b-1)+1)*b;
        return tmp;
    }
    int get(string s1,string s2){
        int i,ans=0;
        for (i=1;i<=int(min(s1.size(),s2.size()));i++){
            string ss1=s1.substr(0,i);
            string ss2=s2.substr(s2.size()-i,i);
            if (ss1==ss2) ans=i;
        }
        return ans;
    }
    int main(){
        //freopen("in.txt","r",stdin);
        int i,j,len,n,k,slen;
        bool ff;
        BigNum ans,tmp;
        string s,ss,st,sp,s1,s2;
        cin >> s;
        n=s.size();
        if (s==string(n,'0')){
            ans=cal(BigNum(1,n))-n+1;
            cout << ans << endl;
            return 0;
        }
        if (n==1){
            cout << s << endl;
            return 0;
        }
        for (len=1;len<n;len++)
            for (i=0;i+len-1<n;i++){
                j=i+len-1;
                if (j>=n) continue;
                ff=true;
                st=s.substr(i,len);
                if (st[0]=='0') continue;
                if (i>0){
                    sp=(BigNum(st)-1).toString();
                    ss=s.substr(0,i);
                    if (ss.size()>sp.size()) continue;
                    if (sp.rfind(ss)!=sp.size()-ss.size()) ff=false;
                }
                if (!ff) continue;
                slen=len;
                for (k=j+1;k+slen-1<n;k+=slen){
                    st=(BigNum(st)+1).toString();
                    slen=st.size();
                    if (k+slen-1>=n) break;
                    if (st!=s.substr(k,slen)){
                        ff=false;
                        break;
                    }
                }
                if (!ff) continue;
                if (k<n){
                    st=(BigNum(st)+1).toString();
                    ss=s.substr(k,n-k);
                    if (st.find(ss)!=0) ff=false;
                }
                if (ff){
                    st=s.substr(i,len);
                    ans=cal(BigNum(st))-i-st.size()+1;
                    goto ppp;
                }
            }
        ppp:
        for (i=0;i<n;i++){
            st=s.substr(0,i);
            st=(BigNum("1"+st)+1).toString();
            st=st.substr(1,st.size()-1);
            s2=s.substr(i,n-i);
            k=get(st,s2);
            if (k>=int(s2.size())) continue;
            st=s.substr(i,n-i-k)+st;
            if (st[0]=='0') continue;
            tmp=cal(BigNum(st)-1)-i+1;
            if (ans==BigNum(0)) ans=tmp;
            else if (tmp<ans) ans=tmp;
        }
        if (s[0]>'0'){
            tmp=cal(BigNum(s))-n+1;
            if (ans==BigNum(0)) ans=tmp;
            else if (tmp<ans) ans=tmp;
        }
        else{
            s="1"+s;
            tmp=cal(BigNum(s))-n;
            if (ans==BigNum(0)) ans=tmp;
            else if (tmp<ans) ans=tmp;
        }
        cout<< ans << endl;
    }
    
    
    
    
    
    
    
    #include<cstdio>
    #include<cstring>
    class BigNum{
    public:
            BigNum(char *str,int _len){
                    memset(a,0,sizeof(a));
                    len=_len;
                    for(int i=len-1;i>=0;i--) a[i]=(*str++)-'0';
            }
            BigNum(int n){
                    memset(a,0,sizeof(a));
                    for(len=0;n;n/=10,len++) a[len]=n%10;
            }
             operator bool() { return len>0; }
             BigNum operator++(){
                     a[0]++;
                     int i;
                     for(i=0;i<len && a[i]>9;i++)
                     {
                             a[i]-=10;
                             a[i+1]++;
                     }
                     if(i==len)
                     {
                             a[i]=1;
                             len++;
                     }
                     return *this;
             }
             void inc()
             {
                     a[0]++;
                     for(int i=0;i<len && a[i]>9;i++)
                     {
                             a[i]-=10;
                             a[i+1]++;
                     }
             }
             friend BigNum operator+(BigNum a,BigNum b)
             {
                     if(a.len<b.len) a.len=b.len;
                     for(int i=0;i<a.len;i++) a.a[i]+=b.a[i];
                     a.ceil();
                     return a;
             }
             friend BigNum operator+(BigNum a,int b)
             {
                     return a+(BigNum)b;
             }
             friend BigNum operator-(BigNum a,BigNum b)
             {
                     for(int i=a.len-1;i>0;i--)
                     {
                             a.a[i]-=b.a[i];
                             a.a[i]--;
                             a.a[i-1]+=10;
                     }
                     a.a[0]-=b.a[0];
                     a.ceil();
                     return a;
             }
             friend BigNum operator-(BigNum a,int b)
             {
                     return a-(BigNum)b;
             }
             friend BigNum operator*(BigNum a,BigNum b)
             {
                     BigNum c=0;
                     c.len=a.len+b.len;
                     for(int i=0;i<a.len;i++)
                             for(int j=0;j<b.len;j++) c.a[i+j]+=a.a[i]*b.a[j];
                     c.ceil();
                     return c;
             }
             friend BigNum operator*(BigNum a,int b)
             {
                     return a*(BigNum)b;
             }
             friend bool operator<(BigNum a,BigNum b)
             {
                     if(a.len==b.len)
                     {
                             int i;
                             for(i=a.len-1;i>0 && a.a[i]==b.a[i];i--);
                             return a.a[i]<b.a[i];
                     }
                     else return a.len<b.len;
             }
             friend bool find(BigNum a,char *str)
             {
                     for(int i=a.len-1;i>=0 && *str;i--)
                             if(a.a[i]!=(*str++)-'0') return false;
                     return true;
             }
             void print()
             {
                     for(int i=len-1;i>=0;i--) printf("%d",a[i]);
                     printf("\n");
             }
             int a[300],len;
     private:
             void ceil()
             {
                     for(int i=0;i<len;i++)
                     {
                             a[i+1]+=a[i]/10;
                             a[i]%=10;
                     }
                     len++;
                     while(len && !a[len-1]) len--;
             }
     };
    
     bool pd(char *a)
     {
             BigNum t=9,now=0;
             for(char *p=a;*p;p++,t=t*10+9)
             {
                     if(*p!='0') return false;
                     now=now*10+t;
             }
             now=now+2;
             now.print();
             return true;
     }
    
     char a[210];
     void work()
     {
             int len=strlen(a);
             BigNum t=0,now=0;
             if(pd(a)) return;
             for(int i=1;i<=len;i++,t=t*10+9)
             {
                     now=now+t;
                     BigNum ans=0;
                     for(int j=0;j<i;j++)
                     {
                             if(a[j]=='0') continue;
                             BigNum prev(a,j);
                             prev.inc();
                             if(j>0 && !find(prev,a+i)) continue;
                             char nn[210];
                             int k;
                             for(k=0;k<i && a[j+k];k++) nn[k]=a[j+k];
                             for(;k<i;k++) nn[k]=prev.a[i-k-1]+'0';
                             BigNum n(nn,i),temp=n;
                             int p;
                             for(p=j+i;p<len && find(++n,a+p);p+=n.len);
                             if(p>=len)
                             {
                                     temp=(temp-1)*i-now-j+1;
                                     if(!ans || temp<ans) ans=temp;
                             }
                     }
                     if(ans)
                     {
                             ans.print();
                             break;
                     }
             }
     }
     int main()
     {
             while (scanf("%s",a) != EOF)
             {
                 work();
             }
             return 0;
     }
    
  • 0
    @ 2016-05-19 16:58:13
  • 0
    @ 2016-04-21 17:37:10

    测试数据 #0: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
    测试数据 #1: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
    测试数据 #2: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
    测试数据 #3: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
    测试数据 #4: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
    测试数据 #5: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
    测试数据 #6: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
    测试数据 #7: Accepted, time = 828 ms, mem = 2628 KiB, score = 10
    测试数据 #8: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
    测试数据 #9: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
    测试数据 #10: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
    测试数据 #11: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
    测试数据 #12: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
    测试数据 #13: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
    测试数据 #14: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
    测试数据 #15: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
    测试数据 #16: WrongAnswer, time = 796 ms, mem = 2632 KiB, score = 0
    测试数据 #17: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
    测试数据 #18: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
    测试数据 #19: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
    测试数据 #20: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
    测试数据 #21: WrongAnswer, time = 765 ms, mem = 2628 KiB, score = 0
    测试数据 #22: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
    测试数据 #23: WrongAnswer, time = 781 ms, mem = 2628 KiB, score = 0
    测试数据 #24: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
    测试数据 #25: WrongAnswer, time = 906 ms, mem = 2628 KiB, score = 0
    测试数据 #26: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
    测试数据 #27: WrongAnswer, time = 796 ms, mem = 2632 KiB, score = 0
    测试数据 #28: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
    测试数据 #29: WrongAnswer, time = 812 ms, mem = 2632 KiB, score = 0
    测试数据 #30: WrongAnswer, time = 828 ms, mem = 2632 KiB, score = 0
    测试数据 #31: Accepted, time = 843 ms, mem = 2632 KiB, score = 10
    测试数据 #32: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
    测试数据 #33: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
    测试数据 #34: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
    测试数据 #35: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
    测试数据 #36: WrongAnswer, time = 812 ms, mem = 2628 KiB, score = 0
    测试数据 #37: WrongAnswer, time = 765 ms, mem = 2632 KiB, score = 0
    测试数据 #38: WrongAnswer, time = 765 ms, mem = 2632 KiB, score = 0
    测试数据 #39: Accepted, time = 781 ms, mem = 2632 KiB, score = 10
    WrongAnswer, time = 31540 ms, mem = 2632 KiB, score = 220

    用的c++的string的.find(),,
    生成一个字符串,,然后直接输出就好了,,
    但是只有220,并不知道为什么
    '''
    c++

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<sstream>

    using namespace std;

    string hahawodabiao;

    string inttostring(int a){
    string b;
    stringstream ss;
    ss << a;
    ss >> b;
    return b;
    }

    void makestring(){
    for(int i = 1;i <= 150000; i++){
    hahawodabiao += inttostring(i);
    }
    }

    int main()
    {
    makestring();
    string a;
    cin>>a;
    cout<<hahawodabiao.find(a)+1;
    return 0;
    }

    '''

  • 0
    @ 2016-03-06 19:39:37
    const
    maxl = 2000;
    type
    bitnode = array[0..maxl+1]of longint;
    var
    len, c,n: longint;
    t : array[1..maxl]of shortint;
    best, a, b : bitnode;
    procedure init;
    var
    st : string[200];
    i : longint;
    begin
    readln(st);
    len := length(st);
    for i := 1 to len do begin
    t[i] := ord(st[i])-48;
    end;
    end;
    
    procedure dec1(var a : bitnode);
    var i : longint;
    begin
    i := 1;
    while a[i] = 0 do begin
    a[i] := 9; inc(i);
    end;
    dec(a[i]);
    if (a[0] > 1) and (a[a[0]] = 0) then dec(a[0]);
    end;
    
    procedure inc1(var a : bitnode);
    var i : longint;
    begin
    i := 1;
    inc(a[i]);
    while a[i] = 10 do begin
    a[i] := 0;
    inc(i);
    inc(a[i]);
    end;
    if a[a[0]+1] <> 0 then inc(a[0]);
    end;
    
    function match(i : longint) : boolean;
    var j : longint;
    begin
    if a[0] < i then begin
    if t[1] <> 8 then exit(false);
    for j := 1 to a[0] do begin
    if t <> a[j] then exit(false);
    end;
    exit(true);
    end else begin
    for j := 1 to i do
    if t <> a[j] then exit(false);
    exit(true);
    end;
    end;
    
    function can(i : longint) : boolean;
    var j : longint;
    begin
    while i < len do begin
    inc1(b);
    j := i+1;
    while (j <= len) and (j-i <= b[0]) do begin
    if b[b[0]-j+i+1] <> t[j] then exit(false);
    inc(j);
    end;
    inc(i, b[0]);
    end;
    exit(true);
    end;
    
    procedure printnum(var a : bitnode);
    var i : longint;
    begin
    for i := a[0] downto 1 do write(a[i]);
    writeln;
    end;
    
    procedure mul(var a : bitnode);
    var b, i : longint;
    begin
    b := a[0];
    for i := 1 to a[0] do a[i] := a[i]*b;
    for i := 1 to a[0] do begin
    inc(a, a[i] div 10);
    a[i] := a[i] mod 10;
    end;
    while a <> 0 do begin
    inc(i);
    a := a[i] div 10;
    a[i] := a[i] mod 10;
    end;
    a[0] := i;
    end;
    
    procedure minus(var a, b : bitnode);
    var i : longint;
    begin
    for i := 1 to a[0] do begin
    if a[i]-b[i] < 0 then begin
    dec(a); inc(a[i], 10);
    end;
    dec(a[i], b[i]);
    end;
    while (a[0] > 1) and (a[a[0]] = 0) do dec(a[0]);
    end;
    
    procedure print;
    var
    i : longint;
    tem : bitnode;
    begin
    dec1(best);
    i := best[0]-1;
    mul(best);
    fillchar(tem, sizeof(tem), 0);
    while tem[0] < i do begin
    inc(tem[0]); tem[tem[0]] := 9;
    minus(best, tem);
    end;
    inc1(best);
    for i := 1 to c do inc1(best);
    printnum(best);
    halt;
    end;
    
    function bigger(var a, b : bitnode): boolean;
    var i : longint;
    begin
    if a[0] > b[0] then exit(true);
    if a[0] < b[0] then exit(false);
    for i := a[0] downto 1 do begin
    if a[i] > b[i] then exit(true);
    if a[i] < b[i] then exit(false);
    end;
    exit(false);
    end;
    
    procedure main;
    var l, i, j, tem : longint; flag : boolean;
    begin
    flag := true;
    for i := 1 to len do if t[i] <> 0 then begin flag := false; break; end;
    if flag then begin
    best[0] := len+1; best[best[0]] := 1; c := 1;
    print;
    end;
    for i := 1 to len do best[i] := t[len-i+1];
    best[0] := len;
    if t[1] = 0 then begin
    inc(best[0]);
    best[best[0]] := 1;
    end;
    for i := len-len shr 1-1 downto 0 do begin
    flag := true;
    for j := 1 to i do if t[j] <> t[len-i+j] then begin
    flag := false; break;
    end;
    if flag then begin
    a[0] := len-i;
    tem := 0;
    for j := 1 to a[0] do a[j] := t[a[0]-j+1];
    for j := 1 to a[0]-i do begin
    if (a[a[0]] <> 0) and ((i = 0) or (a[1] <> 9) or (t <> 9)) then if bigger(best, a) then begin best := a; c := tem; end;
    a[a[0]+1] := a[1];
    for l := 1 to a[0] do a[l] := a[l+1];
    a[a[0]+1] := 0;
    inc(tem);
    end;
    end;
    end;
    for l := 1 to best[0] do begin
    for i := l downto 1 do if (i < len) and (t <> 0) then begin
    fillchar(b, sizeof(b), 0);
    b[0] := l;
    for j := l downto 1 do begin
    if i+l-j+1 > len then break;
    b[j] := t;
    end;
    if (b[0] = 1) and (b[1] = 1) then continue;
    a := b; dec1(a);
    if match(i)
    and can(i+l) then begin
    if bigger(best, a) then begin
    c := a[0]-i;
    best := a;
    end;
    end;
    end;
    end;
    print;
    end;
    
    begin
    init;
    main;
    end.
    
  • 0
    @ 2015-07-23 19:24:16

    #include<cstdio>
    #include<cstring>
    int n,fp,ansp;
    char str[210],minf[210],fir[210],ans[210],temp[210],next[210],ret[210];
    void swap(char&a,char&b)
    {
    char tmp=a;
    a=b;
    b=tmp;
    }
    void get_Adjacent(char t[],int x)
    {
    char s[210];
    int i,flag=0,len=strlen(t);
    for(i=0;i<=len;i++)
    s[i]=t[i];
    if(x==-1)
    {
    for(i=len-1;i>=0&&s[i]=='0';i--);
    if(i>=0)
    s[i]--;
    if(len>1&&s[0]=='0')
    flag=-1;
    for(i=i+1;i<len;i++)
    s[i]='9';
    }
    else
    {
    for(i=len-1;i>=0&&s[i]=='9';i--);
    if(i>=0)
    s[i]++;
    else
    flag=1;
    for(i++;i<len;i++)
    s[i]='0';
    }
    i=0;
    if(flag==1)
    next[i++]='1';
    for(;i<len+flag;i++)
    next[i]=s[i-flag];
    next[i]='\0';
    }
    bool judgment(int p,int len)
    {
    int i ;
    if(str[p]!='1')
    return 0;
    for(i=1;i<p;i++)
    if(str[i]!='9')
    return 0;
    for(i=1;i+p<=n&&i<len;i++)
    if(str[i+p]!='0')
    return 0;
    return 1;
    }
    void getMin(char s[],char t[])
    {
    int i,ls=strlen(s),lt=strlen(t);
    if(t[0]=='0'||lt>ls)
    return;
    if(lt<ls)
    {
    strcpy(s,t);
    ansp=fp;
    return;
    }
    for(i=0;i<ls;i++)
    {
    if(s[i]>t[i])
    break;
    else
    if(s[i]<t[i])
    return;
    }
    strcpy(s,t);
    ansp=fp;
    }
    void find_FirstNumber()
    {
    int i,j,k,l,len,cnt;
    for(i=0;i<208;i++)
    minf[i]='A';
    minf[210-1]='\0';
    for(l=1;l<=n;l++)
    for(len=l,i=2;i<=len+1;i++)
    {
    fp=i;
    if(str[i]=='0')
    continue;
    if(n-i+1<len)
    {
    if(judgment(i,len+1))
    {
    for(j=0;j<len;j++)
    fir[j]='9';
    fir[j]='\0';
    getMin(minf,fir);
    continue;
    }
    for(j=1;j<i&&str[j]=='9';j++);
    if(j==i)
    {
    for(j=0;j+i<=n;j++)
    temp[j]=str[i+j];
    temp[j]='\0';
    get_Adjacent(temp,-1);
    k=j;
    cnt=1;
    while(next[j-1]=='9'&&cnt<i)
    {
    k--;
    j--;
    cnt++;
    }
    for(j=0;j<k;j++)
    fir[j]=next[j];
    for(j=1;j<i;j++)
    fir[k+j-1]=str[j];
    fir[k+j-1]='\0';
    getMin(minf,fir);
    continue;
    }
    for(j=1;j<i;j++)
    fir[len-j]=str[i-j];
    fir[len]='\0';
    for(j=0;j<=len-i;j++)
    fir[j]=str[i+j];
    get_Adjacent(fir,1);
    for(j=0;j<len&&i+j<=n;j++)
    if(next[j]!=str[i+j])
    break;
    if(j<len&&i+j<=n)
    continue;
    else
    {
    getMin(minf,fir);
    continue;
    }
    }
    if(judgment(i,len+1))
    {
    len++;
    for(j=1;j<len;j++)
    temp[j]='0';
    temp[0]='1';
    temp[j]='\0';
    for(j=0;j<len-1;j++)
    fir[j]='9';
    fir[j]='\0';
    }
    else
    {
    for(j=0;j<len;j++)
    temp[j]=str[j+i];
    temp[j]='\0';
    get_Adjacent(temp,-1);
    for(j=1;j<i;j++)
    if(next[len-j]!=str[i-j])
    break;
    if(j<i)
    continue;
    strcpy(fir,next);
    }
    k=i+len;
    while(k<=n)
    {
    get_Adjacent(temp,1);
    len=strlen(next);
    for(j=0;k+j<=n&&j<len;j++)
    if(next[j]!=str[k+j])
    break;
    if(k+j<=n&&j<len)
    break;
    strcpy(temp,next);
    k+=len;
    }
    if(k>n)
    getMin(minf,fir);
    }
    }
    void bigAdd(char a[],char b[])
    {
    int la=strlen(a),lb=strlen(b),i,j,carrt=0,tmp,cnt=0;
    for(i=la-1,j=lb-1;i>=0&&j>=0;i--,j--)
    {
    tmp=a[i]+b[j]-'0'-'0'+carrt;
    carrt=tmp/10;
    ret[cnt++]=tmp%10+'0';
    }
    for(;i>=0;i--)
    {
    tmp=a[i]-'0'+carrt;
    carrt=tmp/10;
    ret[cnt++]=tmp%10+'0';
    }
    for(;j>=0;j--)
    {
    tmp=b[j]-'0'+carrt;
    carrt=tmp/10;
    ret[cnt++]=tmp%10+'0';
    }
    while(carrt)
    {
    ret[cnt++]=carrt%10+'0';
    carrt/=10;
    }
    ret[cnt++]='\0';
    for(i=0;i<cnt/2;i++)
    swap(ret[i],ret[cnt-i-2]);
    strcpy(a,ret);
    }
    void bigMutil(char a[],int b)
    {
    int i,len=strlen(a);
    for(i=0;i<=len;i++)
    next[i]=a[i];
    for(i=1;i<b;i++)
    bigAdd(a,next);
    }
    void cal_Temp()
    {
    int i,j,len=strlen(minf);
    for(i=1;i<len&&minf[i]=='0';i++);
    if(i==len&&minf[0]=='1')
    {
    temp[0]='0';
    temp[1]='\0';
    return;
    }
    j=i=1;
    temp[0]=minf[0]-1;
    if(temp[0]=='0')
    i=0;
    for(;i<=len;i++,j++)
    temp[i]=minf[j];
    }
    void solve()
    {
    char a[210];
    int i,j,cnt,t,len=strlen(minf);
    ans[0]='0';
    ans[1]='\0';
    for(i=1;i<len;i++)
    {
    t=i*9;
    cnt=0;
    while(t)
    {
    a[++cnt]=t%10+'0';
    t/=10;
    }
    for(j=0;j<cnt;j++)
    temp[j]=a[cnt-j];
    cnt=j;
    for(j=0;j<i-1;j++)
    temp[cnt++]='0';
    temp[cnt]='\0';
    bigAdd(ans,temp);
    }
    cal_Temp();
    bigMutil(temp,len);
    bigAdd(ans,temp);
    for(i=-1;i<=len-ansp;i++)
    {
    get_Adjacent(ans,1);
    strcpy(ans,next);
    }
    }
    bool special_Judge()
    {
    int i,j;
    n--;
    for(i=1;i<=n&&str[i]=='0';i++);
    if(i<=n/2+1)
    return 0;
    ansp=i;
    if(i>n)
    {
    minf[0]='1';
    for(j=1;j<=n;j++)
    minf[j]='0';
    minf[j]='\0';
    }
    else
    {
    for(j=0;i+j<=n;j++)
    minf[j]=str[i+j];
    for(;j<n;j++)
    minf[j]='0';
    minf[j]='\0';
    }
    return 1;
    }
    main()
    {
    str[0]='0';
    scanf("%s",str+1);
    n=strlen(str);
    if(!special_Judge())
    find_FirstNumber();
    solve();
    printf("%s",ans);
    }

  • 0
    @ 2015-02-05 14:01:55

    这道题特别难,史诗级巨难。100行开外。不知道楼下用的是什么语言,看上去很好很简洁,但是没有大括号也挺乱。

  • 0
    @ 2014-12-11 04:01:26

    https://github.com/gaoyunzhi/online_judge/blob/master/vijos1005.py

    # https://vijos.org/p/1039
    # test cases http://acm.timus.ru/forum/?space=1&num=1165
    import sys, random

    class Solver():
    def init(self, string):
    self._string = string
    self.len = len(self._string)
    self.initMin()
    self.updateEasyCaseMin() # where start can be extraced
    self.updateHardCaseMin() # where start can not be extraced

    def getAns(self):
    digit = len(str(self.min))
    ans = 0
    for i in xrange(1, digit):
    ans += 9 * i * 10 ** (i - 1)
    ans += digit * (self.min - 10 ** (digit - 1))

    ans -= self.pos
    return ans + 1

    def initMin(self):
    if self._string[0] == '0':
    self.min = int('1' + self._string) + 1
    self.pos = self.len
    else:
    self.min = int(self._string)
    self.pos = 0

    def updateEasyCaseMin(self):
    for start_ind in xrange(self.len):
    if self._string[start_ind] == '0':
    continue
    for end_ind in xrange(start_ind * 2, self.len):
    start = self._string[start_ind: end_ind + 1]
    start_int = int(start)
    if start_int > self.min or (start_int == 1 and start_ind != 0):
    continue
    potential_list = map(
    str,
    range(start_int - 1, start_int + self.len / len(start) + 1)
    )
    potential_string = ''.join(potential_list)
    if not potential_string[len(potential_list[0]) - start_ind:] \
    .startswith(self._string):
    continue
    self._updateMin(start_int, start_ind)

    def updateHardCaseMin(self):
    for start_ind in xrange(1, self.len):
    second_part = self._string[start_ind:]
    if second_part[0] == '0':
    continue
    first_part = self._string[:start_ind]
    second_part_int = int(second_part)
    if second_part_int > self.min:
    continue
    for num in xrange(1, start_ind + 1):
    tail = first_part[start_ind - num:]
    if tail == '9' * num and second_part_int > 1 \
    and str(second_part_int - 1).endswith(first_part[:start_ind - num]):
    self._updateMin(int(str(second_part_int - 1) + tail) + 1, start_ind)
    if tail != '9' * num and second_part.endswith(first_part[:start_ind - num]):
    self._updateMin(int(second_part + tail) + 1, start_ind)

    def _updateMin(self, new_min, pos):
    if new_min == self.min:
    self.pos = max(self.pos, pos)
    return
    if new_min < self.min:
    self.min = new_min
    self.pos = pos

    def main():
    # handle=sys.stdin
    handle = open("1005.txt", "r")
    string = handle.readline().strip()
    sol = Solver(string)
    sys.stdout.write(str(sol.getAns()))

    def test():
    string = ''.join(map(str, xrange(1, 100000)))
    print Solver('999').getAns() == 2588
    print Solver(string[:100]).getAns() == 1
    print Solver('1').getAns() == 1
    print Solver('5').getAns() == 5
    print Solver('101').getAns() == 10
    print Solver('01').getAns() == 11
    print Solver('1011').getAns() == 10
    print Solver('12345').getAns() == 1
    print Solver('012345').getAns() == 629595
    print Solver('9920').getAns() == 488
    print Solver('0112').getAns() == 3373

    for i in xrange(2000):
    if random.random() > 0.005: continue
    for j in xrange(i, 2000):
    if random.random() > 0.005: continue
    substring = string[i: j + 1]
    ind = string.find(substring)
    if Solver(substring).getAns() != ind + 1:
    print '- attention -'
    print i, j
    print substring, Solver(substring).getAns()

    if name == '__main__':
    # main()
    test()

  • 0
    @ 2014-09-02 19:35:12

    var s,t,q,p,ans,v,z,da,u:string;
    a,b,c,d,e,g,i,j,k,m,n,ji:longint;
    h:array[1..200]of boolean;
    f:array[1..256]of string;
    function qian(l:string):string; //(求一个数的前面一个数,即a-1)
    var o,w:longint;r:string;
    begin
    o:=length(l);
    r:=l;
    while r[o]='0' do dec(o);
    r[o]:=pred(r[o]);
    for w:=o+1 to length(r) do r[w]:='9';
    if r[1]='0' then delete(r,1,1);
    qian:=r;
    end;
    function hou(l:string):string;//(后一个数,即a+1)
    var o,w:longint;r:string;
    begin
    o:=length(l);
    r:=l;
    while (r[o]='9')and(o>1) do dec(o);
    if (o=1)and(r[1]='9') then
    r:='1'+r else r[o]:=succ(r[o]);
    for w:=o+1 to length(r) do r[w]:='0';
    hou:=r;
    end;
    function sum(l1,w1:string):string;//(求两数之和)
    var o,r,e1:longint;l,w,x:string;
    begin
    l:=l1;w:=w1;
    x:='';
    if length(l)<length(w) then
    for o:=length(l)+1 to length(w) do l:='0'+l;
    if length(l)>length(w) then
    for o:=length(w)+1 to length(l) do w:='0'+w;
    e1:=0;
    for o:=length(w) downto 1 do
    begin
    r:=ord(l[o])+ord(w[o])-96+e1;
    e1:=r div 10;
    r:=r mod 10;
    x:=chr(r+48)+x;
    end;
    if e1>0 then x:=chr(e1+48)+x;
    sum:=x;
    end;
    begin
    readln(s);
    g:=length(s);
    f[1]:='9';v:='9';
    for i:=2 to 256 do
    begin
    v:=sum(v,'9');
    f[i]:=v;
    for j:=1 to i-1 do f[i]:=f[i]+'0';
    end;
    ans:='';
    for i:=1 to 250 do ans:=ans+'0';
    c:=1;
    for i:=1 to length(s) do if s[i]<>'0' then begin c:=0;break;end;
    if c=1 then begin ji:=1;ans:='1'+s;e:=length(ans)-1;end;//末尾全是0时特殊判断
    if ji=0 then
    for i:=1 to g do
    begin
    for j:=1 to g-i+1 do
    begin
    if s[j]='0' then continue;
    t:=copy(s,j,i);a:=j-1;b:=j+i;
    q:=t;p:=t;
    while a>0 do begin q:=qian(q);
    if length(q)>a then begin t:=copy(q,length(q)-a+1,a)+t;a:=0;end else
    begin t:=q+t;a:=a-length(q);
    if q='0' then continue;end;end;
    while b<=g do begin p:=hou(p);
    if length(p)>g-b+1 then begin t:=t+copy(p,1,g-b+1);b:=g+1;end else
    begin t:=t+p;b:=b+length(p);end;end;
    if t=s then begin ans:=copy(s,j,i);e:=j+i-1;break;end;
    end;
    if e>0 then break;
    end;
    if ji=0 then
    for i:=2 to g do
    begin
    for j:=g downto g-i+2 do
    if j-i<=0 then
    begin
    if s[j]='0' then continue;
    t:=copy(s,j,g-j+1);
    p:=copy(s,g-i+1,j-g+i-1);
    q:=hou(p);
    if length(q)>length(p) then
    begin t:=t+copy(q,2,length(q)-1);end else t:=t+q;
    c:=0;
    p:=qian(t);
    if copy(p,length(p)-j+2,length(p))=copy(s,1,j-1) then c:=1;
    if c=0 then continue;
    if length(t)<length(ans) then c:=0 else
    if length(t)=length(ans) then begin if t<ans then c:=0;end else
    continue;
    if c=0 then begin ans:=t;e:=j-1+length(t);end;
    end;
    end;
    if ji=0 then begin
    da:='0';
    ans[1]:=pred(ans[1]);
    ans:=sum(ans,'1');
    da:=ans;
    u:='0';
    for i:=1 to length(ans)-1 do u:=sum(u,f[i]);
    for i:=1 to length(ans)-1 do
    da:=sum(da,ans);
    da:=sum(da,u);
    end else
    begin
    da:='0';
    for i:=1 to e do da:=sum(da,f[i]);
    end;
    if ji=0 then begin
    if length(da)<6 then
    begin z:=da;da:='';end else
    begin z:=copy(da,length(da)-5,6);delete(da,length(da)-5,6);end;
    val(z,d);
    d:=d-e;
    str(d,z);
    da:=da+z;
    end;
    da:=sum(da,'1');
    if ji=1 then da:=sum(da,'1');
    writeln(da);
    end.

    果然超长。。。。。

    • @ 2014-10-20 12:35:24

      不分行会恶心死人的。。。。。。

信息

ID
1005
难度
8
分类
字符串 | KMP 点击显示
标签
(无)
递交数
6204
已通过
587
通过率
9%
被复制
12
上传者