洛谷2454 [SDOI2006]数字串位置

这是一道山东省选的题目。听大佬说，山东省选是最难的省选。所以这题是和lpjworkroom和云中翻月两位大佬合作完成。
lpjworkroom https://www.jianshu.com/u/5b56e393a2eb
云中翻月 https://www.jianshu.com/u/0269cab93a42
首先，在将做法之前，先吐槽一下，这题是我目前做的最恶心的题目！。理由如下：
1.乍一看是个普通的字符串匹配问题，但是母串是无限长的字符串，而且字串的长度最大为200，所以，普通的字符串匹配是解决不了问题的。
2.即使求出来了字串开头的数字，但要求它所在的位置，还要用高精度，因此不管是思路上还是编码上，都是很不容易的。
3.最糟糕的是，这一题目前只找到两个oj上可以提交，vijos和洛谷，
https://vijos.org/p/1005，
https://www.luogu.org/problemnew/show/P2454，
而且这两个网站上的数据都有错！因为在vijos上找了一篇题解代码，用这篇代码在vijos上和洛谷上提交，都能AC，但是我们找到了反例输入，用题解代码运行答案显然错误。另外，网上也根本找不到题解，所以，我要写一下我们的思路。

方法一：滚动数组dp，找最长公共字串
结果：TLE，但保证正确。
这个是我自己的做法，做法很简单，只要会写最长公共字串，就会这样写。因为模式串最长只有200，所以只需开2*200的数组，第一维滚动母串的位置，循环1到无穷（不过显然不会到无穷），更新这个数字的代表的母串的位置的dp值，当公共字串的长度等于模式串的长度时输出当前位置即可。
代码如下：

//TLE
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s="#";
int curnum,curpos;
int dp[2][205];
string myto_string(int);
int main()
{
    ios::sync_with_stdio(false);
    string temp;
    cin>>temp;
    s+=temp;
    curnum=curpos=1;
    for(int i=1;;i++)
    {
        string temps=myto_string(curnum);
        char c=temps[curpos-1];
//      cout<<c;
        for(int j=1;j<s.size();j++)
        {
//          int x=i&1;
            if(c==s[j])
                dp[i&1][j]=dp[(i-1)&1][j-1]+1;
            else
                dp[i&1][j]=0;
        }
        curpos++;
        if(curpos>temps.size())
        {
            curpos=1;
            curnum++;
        }
        if(dp[i&1][s.size()-1]==s.size()-1)
        {
            cout<<i-s.size()+2<<endl;
            return 0;
        }
    }
//  cout<<endl;
    return 0;
}
string myto_string(int n)
{
    string res="";
    while(n)
    {
        res+=n%10+'0';
        n/=10;
    }
    reverse(res.begin(),res.end());
    return res;
}

方法二：分情况讨论，高精度求解
根据方法一的失败经验，我们很容易发现：在求解过程中，不能涉及对无穷长的母串的操作。而模式串的长度最大为200，所以很容易想到要对模式串进行操作。
首先，我们明确，模式串是由一个或多个连续的数字组成的。那么，我们怎么求模式串出现在母串里的位置呢？问题比较复杂，我们就先对问题进行分解：
1.求出模式串的开头数字，并求出开头数字前面被截掉了几位
2.高精度求最后答案
我们先做出几个规定：
（1）final：组成模式串的一系列连续数字的开头数字
（2）firlack：final前面被截掉的位数
然后，我们对这两个问题分别讨论。
1.
显然，我们只要能求出模式串是由哪个或哪一串尽量小的连续数字组成，就可以求出模式串在母串中的位置。我们假设模式串开始的数字为final。那么，我们就要对模式串进行划分来求解final。通俗的说，就是对模式串进行切割。而切割共有三种情况：
a.模式串是一个完整的数字
对于这种情况，如果模式串甚至不能表示一个完整的数字，假设记为fakefinal，那么显然fakefinal>final，其第一次出现的位置也在final后。所以模式串至少是一个完整的数字。
注意：
这种情况仅有一种反例，那就是模式串全0时。显然，这时候在这串0前面补上一个1作为final是最优情况。由于仅有一种特殊情况，特判即可。
b.模式串是多个（3个及以上）连续的数字
对于这种情况，我们需要枚举final在模式串里结束的位置和每个数字的长度，这样不断判断下一个数字是否为上一个数字+1即可。对于所有可行情况，取最小值。
注意：
枚举模式串里连续数字长度时，要注意进位问题，即若模式串为89101112131，显然final=8。但是当我们枚举连续数字长度时，若仅以final的长度作为连续数字长度，就会发生错误。如本例中的10 11等数字就是2位。因此要在循环时随时更新连续数字长度。
c.模式串是两个连续的数字
对于这种情况，我们只需枚举切割位置，前一半记做first，后一半记做second，然后把first当做不完整的final，将其加一后与second比较，看是否second的后边与first+1的前面有公共部分，若有，则去掉一个公共串后拼接作为final（如23124，实际是123 124，first=23，second=124，first+1=24，与second有公共部分，则拼接后final=124）若没有公共部分，则直接拼接（如231，实际为123 124 ，first=23，second=1，first+1=24，没有公共部分，则final=124）。取所有可能结果的最小值作为final。
综上三种情况，取最小值即为final。注意随时更新firlack。第1步结束。
2.
高精度求第一次出现的位置。推公式，难度不大，记得firlack。此处不加赘述。
代码如下：

#include<iostream>
#include<fstream>
#include<sstream>
#include<stdlib.h>
#include<string.h>
#include<string>
using namespace std;
const int MAXL=200+50;
const int base=10;
class Bignum{
    public:
    int size,len; //len limits tostr()'s length
    int data[MAXL];
    friend ostream& operator<<(ostream& out,Bignum& a); 
    
    int& operator[](int x)
    {
        return data[x];
    }
    
    void add(Bignum b)
    {
        int maxsize=max(size,b.size);
        for(int i=0;i<maxsize;i++) data[i]+=b.data[i];
        for(int i=0;i<maxsize;i++){
            data[i+1]+=data[i]/base;
            data[i]%=base;
        }
        if (data[maxsize])  maxsize++;
        size=maxsize;
    }
    
    //assume this>b
    void minus(Bignum b)
    {
        for(int i=0;i<size;i++)
        {
            if(data[i]>=b[i]) data[i]-=b[i];
            else
            {
                data[i]=data[i]+base-b[i];
                data[i+1]--;    
            }
        }
        while(data[size-1]==0&&size) size--;
    }
    
    Bignum operator*(Bignum b)
    {
        Bignum c("0");
        int maxsize=size+b.size-1;
        for(int i=0;i<size;i++) for(int j=0;j<b.size;j++) c[i+j]=data[i]*b[j];
        for(int i=0;i<maxsize;i++){
            c[i+1]+=c[i]/base;
            c[i]%=base;
        }
        while(c[maxsize]){
            c[maxsize]+=c[maxsize-1]/base;
            c[maxsize-1]%=base;
            if(c[maxsize])  maxsize++;
            else    break;
        }
        c.size=maxsize;
        return c;
    }
    
    bool operator==(Bignum& b)
    {
        if(size!=b.size) return false;
        for(int i=0;i<size;i++) if(data[i]!=b[i]) return false;
        return true;
    }
    
    bool operator<(Bignum& b)
    {
        if(size!=b.size) return size<b.size;
        for(int i=size-1;i>=0;i--) if(data[i]!=b[i]) return data[i]<b[i];
        return false;
    }
    
    void operator=(Bignum b)
    {
        size=b.size;
        len=b.len;
        memset(data,0,sizeof(data));
        for(int i=0;i<size;i++) data[i]=b[i];
    }
    
    Bignum(string str)
    {
        size=len=str.size();
        memset(data,0,sizeof(data));
        for(int i=0;i<size;i++) data[size-i-1]=str[i]-'0';
    }
    
    Bignum()
    {
        size=len=0;
        memset(data,0,sizeof(data));
    }
    
    string tostr()
    {
        string s="";
        for(int i=len-1;i>=0;i--) s+=(data[i]+'0');
        return s;
    }
    
};
ostream& operator<<(ostream& out,Bignum& a)
{
    for (int i=a.size-1;i>=0;i--)   out<<a.data[i];
    return out;
}

int N,firsta=0;
string data;
Bignum ans,final;

string itoa(int a);
bool all9(Bignum& a);

int main()
{
    
    //cin>>data;
    cin>>data;
    N=data.size();
    
    if (data==string(N,'0')){
        data="1"+data;
        N++;
        firsta=1;
    }
    final=Bignum(data);
    
    /*2*/
    /*i=0?*/
    for (int i=1;i<(N+1)/2;i++)
    {
        if (data[i]=='0')   continue;
        for (int j=i;j+i<N;j++)
        {
            Bignum fir=Bignum(data.substr(0,i)),sec=Bignum(data.substr(i,j));
            
            Bignum seclast=Bignum(data.substr(j,i));
            fir.add(Bignum("1"));
            if (!(fir.tostr()==seclast.tostr()))    continue;
            
            Bignum tmpfi=sec;
            tmpfi.minus(Bignum("1"));
            if (final<tmpfi)    continue;
            
            fir=sec;
            bool ok=true;
            fir.add(Bignum("1"));
            int k,nxtwid=fir.size;
            /**/
            for (k=j+i;k+nxtwid<N;k+=nxtwid)
            {
                nxtwid=fir.size;
                sec=Bignum(data.substr(k,nxtwid));
                //cout<<"now ought to be:"<<fir<<" sec is:"<<sec<<endl;
                if (!(fir==sec)){
                    ok=false;break;
                }
                fir.add(Bignum("1"));
            }
            if (!ok)    continue;
            
            //fir.add(Bignum("1"));
            for (int p=fir.size-1;k!=N;k++,p--)
            {
                if (fir.data[p]!=(data[k]-'0')){
                    ok=false;break;
                }
            }
            if (!ok)    continue;
            final=tmpfi;firsta=j-i;
        }
    }
    /*2 over*/
    /*3*/
    for (int i=1;i<=N-1;i++)
    {
        if (data[i]=='0')   continue;
        Bignum tt(data.substr(0,i));
        tt.add(Bignum("1"));
        string strfir=tt.tostr(),strsec=data.substr(i);
        int l;
        /*l: pre and suf 's public string*/
        for (l=min(i,N-i);l>0;l--)
        {
            string pre=strfir.substr(0,l),suf=strsec.substr(N-i-l);
            if (pre==suf)   break;
        }
        Bignum tmp=Bignum(strsec+strfir.substr(l));
        tmp.minus(Bignum("1"));
        
        
        if (tmp<final){
            final=tmp;firsta=strsec.size()-l;
        }
    }
    /*3 over*/
    if (all9(final))    firsta--;
    if (final.size==1){
        //cout<<final<<endl;
        cout<<final<<endl;
        return 0;
    }
    
    /*calculate answer*/
    int wid=final.size;
    ans=Bignum(string(wid-1,'1'));
    
    Bignum pow("1");
    for (int i=0;i<wid-1;i++)   pow=pow*Bignum("10");
    
    pow=pow*Bignum(itoa(wid-1));
    pow.minus(ans);
    ans=pow;
    Bignum tmp=final;
    
    tmp.minus(Bignum("1"+string(wid-1,'0')));
    tmp=tmp*Bignum(itoa(wid));
    tmp.add(Bignum(itoa(firsta)));
    tmp.add(Bignum("1"));
    ans.add(tmp);
    //cout<<ans;
    cout<<ans<<endl;
return 0;
}

string itoa(int a)
{
    stringstream ss;
    ss<<a;
    string ret;
    ss>>ret;
    return ret;
}


bool all9(Bignum& a)
{
    for (int i=0;i<a.size;i++)
        if (a[i]!=9)    return false;
    return true;
}

总结：
1.这道题的代码其实我也不知道是否正确，因为网上找不到真正正确的题解和数据，所以仅附思路和代码，如果发现问题，欢迎指正。
2.这道题与其说是考算法，不如说是考编程能力和细心程度。不管是划分时的复杂情况，还是高精度类，都有一定的难度。