zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

LG 1415 拆分数列加强版

复杂度要求减少

我们先来考虑dp方式

f_i = max(j)|(num(f[j],j) < num(j+1,i))

我们把填表式换成刷表式

现在不考虑0:

如果num(f[i],i)<num(i+1,i+1+i-f[i])

那么f(x) = max(f(x),i+1) (x\in[i+1+i-f[i],n])

否则f(x) = max(f(x),i+1) (x\in[i+1+i-f[i]+1,n])

(因为长度+1肯定满足)

于是我们可以令开一个数组来记录或者用线段树优化dp

现在考虑那个毒瘤的0:

要从i推到j

到达i时最小的数字应该是num(f[i],i)

这时候num(f[i],i)可能有前导0

num(i+1,i+1+i-f[i])也可能有前导0

我们用R0[i]表示从i开始有连续几个0

比较的时候就可以排除0的干扰

枚举的时候可以用hash+二分求出最大公共前缀优化到log n

#include<bits/stdc++.h>
namespace ZDY{
    #pragma GCC optimize(3)
    #define il __inline__ __attribute__ ((always_inline))
    #define rg register
    #define ll long long
    #define ull unsigned long long
    #define db double
    #define sht short
    #define MB template <class T>il
    #define Fur(i,x,y) for(int i=x;i<=y;++i)
    #define Fdr(i,x,y) for(int i=x;i>=y;--i)
    #define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdout)
    #define fcin ios::sync_with_stdio(false)
    #define l2(n) ((int)(log2(n)))
    #define inf 0x3f3f3f3f
    MB T ABS(T x){return x>0?x:-x;}
    MB T MAX(T x,T y){return x>y?x:y;}
    MB T MIN(T x,T y){return x<y?x:y;}
    MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
    MB void SWAP(T &x,T &y){T t=x;x=y;y=t;}
}using namespace ZDY;using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){clr(ch,0);if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}IN& operator>>(string& ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;ch+=c;while((c=gc())!=EOF&&!isspace(c))ch+=c;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(string s){for(int i=0;s[i];i++)pt(s[i]);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 1011
int n,f[N],R0[N];
char a[N];
int g[N],s[N];
ull h[N],pw[N];
#define base 1331
ull get(int l,int r){
    return h[r]-h[l-1]*pw[r-l+1];
}
il bool cmp(int l,int r,int L,int R){
    if(r-l<R-L)return 1;
    if(r-l>R-L)return 0;
    int ar=r-l+1,al=1,ans=0;
    while(al<=ar){
        int m=(al+ar)>>1;
        if(get(l,l+m-1)==get(L,L+m-1))ans=m,al=m+1;
        else ar=m-1;
    }
    return (ans!=r-l+1&&a[l+ans]<a[L+ans]);
}
int main(){
    fin("in");
    in>>(a+1);
    n=strlen(a+1);
    pw[0]=1;
    Fur(i,1,n){
        s[i]=1,f[i]=1;
        h[i]=h[i-1]*base+a[i];
        pw[i]=pw[i-1]*base;
    }
    Fdr(i,n,1)if(a[i]=='0')R0[i]=R0[i+1]+1;
    int S=1;
    Fur(i,1,n){
        S=MAX(S,s[i]);
        f[i]=MAX(f[i],S);
        int p,q,l,r;
        l=f[i]+R0[f[i]];r=i;l=MIN(l,r);
        p=r+1;p+=R0[p];q=p+r-l;
        if(cmp(l,r,p,q))s[q]=MAX(s[q],r+1);
        else s[q+1]=MAX(s[q+1],r+1);
    }

    clr(s,0);

    g[f[n]]=n;
    int zero=f[n];
    while(a[zero-1]=='0')g[--zero]=n;
    Fdr(i,f[n]-1,1){
        Fdr(j,f[n]-1,i)
            if(cmp(i,j,j+1,g[j+1])){
                g[i]=j;
                break;
            }
    }
    int p=1,ff=0;
    while(p<=n){
        if(ff)out.pt(',');
        ff=1;
        Fur(i,p,g[p])out.pt(a[i]);
        p=g[p]+1;
    }
}
LG 2282 [HNOI2003]历史年份
comment评论
Search
search