C++11(clang++ 3.9) 解法, 执行用时: 846ms, 内存消耗: 2652K, 提交时间: 2019-04-30 19:40:57

#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=2020,P=131;

inline ll rd(){
    ll x=0;char c=getchar();int neg=1;
    while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*neg;
}

char num[maxn];
int N,M,f[maxn],nn0[maxn],pn0[maxn];
int laz[maxn<<2],ma[maxn<<2];
ull hsh[maxn],bin[maxn];

inline bool bigger(int x1,int x2,int l){
    int a=1,b=l,k=0;
    while(a<=b){
        int m=a+b>>1;
        if(hsh[x1+m-1]-hsh[x1-1]*bin[m]==hsh[x2+m-1]-hsh[x2-1]*bin[m]) a=m+1,k=m;
        else b=m-1;
    }
    if(k>=l) return 0;
    else return num[x1+k]>num[x2+k];
    return 0;
}

inline void pushdown(int p){
    if(!laz[p]) return;
    int a=p<<1,b=p<<1|1;
    ma[a]=max(laz[p],ma[a]),ma[b]=max(laz[p],ma[b]);
    laz[a]=max(laz[a],laz[p]),laz[b]=max(laz[b],laz[p]);
    laz[p]=0;
}

inline void change(int p,int l,int r,int x,int y,int z){
    ma[p]=max(ma[p],z);
    if(x<=l&&r<=y){
        laz[p]=max(laz[p],z);
    }else{
        pushdown(p);
        int m=l+r>>1;
        if(x<=m) change(p<<1,l,m,x,y,z);
        if(y>=m+1) change(p<<1|1,m+1,r,x,y,z);
    }
}

inline int query(int p,int l,int r,int x){
    if(l==r) return ma[p];
    int m=l+r>>1;
    pushdown(p);
    if(x<=m) return query(p<<1,l,m,x);
    else return query(p<<1|1,m+1,r,x);
}

int main(){
    //freopen(".in","r",stdin);
    int i,j,k;
    bin[0]=1;for(i=1;i<=2000;i++) bin[i]=bin[i-1]*P;
    while(~scanf("%s",num+1)){
        N=strlen(num+1);
        for(i=1;i<=N;i++)
            hsh[i]=hsh[i-1]*P+num[i];
        CLR(ma,0);CLR(laz,0);
        nn0[N+1]=N+1;
        for(i=N;i>=0;i--)
            nn0[i]=(num[i+1]!='0')?i+1:nn0[i+1];
        for(i=1;i<=N;i++)
            pn0[i]=(num[i-1]!='0')?i-1:pn0[i-1];
        change(1,1,N,1,N,1);
        for(i=1;i<=N;i++){
            f[i]=query(1,1,N,i);
            int y=nn0[i],nxt=y+i-nn0[f[i]-1]+1;
            if(bigger(y,nn0[f[i]-1],i-nn0[f[i]-1]+1)) nxt--;
            if(nxt<=N) change(1,1,N,nxt,N,i+1);
        }
        M=f[N];
        CLR(f,0);CLR(ma,0);CLR(laz,0);
        change(1,1,N,pn0[M]+1,M,N);
        for(i=M;i;i--){
            f[i]=query(1,1,N,i);
            int y=nn0[i-(f[i]-nn0[i-1]+1)-1],nxt;
            if(i-y<f[i]-nn0[i-1]+1||(i-y==f[i]-nn0[i-1]+1&&bigger(nn0[i-1],y,f[i]-nn0[i-1]+1))) nxt=pn0[y]+1;
            else nxt=y+1;
            if(nxt<=i-1) change(1,1,N,nxt,i-1,i-1);
        }
        if(N<nn0[0]) printf("%s",num+1); 
        else{
            for(i=1;i<=N;i=f[i]+1){
                for(j=i;j<=f[i];j++)
                    putchar(num[j]);
                if(f[i]!=N) putchar(',');
            }   
        }printf("\n");
    }
    return 0;
}