T1、全连（fc）

Code

//PaperCloud 2019/2/12//60 pts#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    register int x=0,f=1;register char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return x*f;}#define MN 1000005int N,tm[MN];ll a[MN];namespace solve1{    ll f[10005],ans;    void work()    {        register int i,j;        memset(f,0,sizeof f);        ans=f[1]=a[1];        for(i=2;i<=N;++i)        {            f[i]=a[i];             for(j=i-1;j;--j) if(max(tm[i],tm[j])<=i-j) f[i]=max(f[i],f[j]+a[i]);            ans=max(ans,f[i]);        }        printf("%lld\n",ans);    }}namespace solve2{    struct Node    {        ll val,lazy;    }T[MN<<3];    void down(int x)    {        if(!T[x].lazy) return;        T[x<<1].val=max(T[x<<1].val,T[x].lazy);        T[x<<1].lazy=max(T[x<<1].lazy,T[x].lazy);        T[x<<1|1].val=max(T[x<<1|1].val,T[x].lazy);        T[x<<1|1].lazy=max(T[x<<1|1].lazy,T[x].lazy);        T[x].lazy=0;    }    void Mdf(int x,int l,int r,int a,int b,ll val)    {        if(a==l&&r==b) {T[x].val=max(T[x].val,val);T[x].lazy=max(T[x].lazy,val);return;}        register int mid=(l+r)>>1;down(x);        if(b<=mid) Mdf(x<<1,l,mid,a,b,val);        else if(a>mid) Mdf(x<<1|1,mid+1,r,a,b,val);        else Mdf(x<<1,l,mid,a,mid,val),Mdf(x<<1|1,mid+1,r,mid+1,b,val);        T[x].val=max(T[x<<1].val,T[x<<1|1].val);    }    ll Gi(int x,int l,int r,int p)    {        if(l==r) return T[x].val;        register int mid=(l+r)>>1;down(x);        if(p<=mid) return Gi(x<<1,l,mid,p);        else return Gi(x<<1|1,mid+1,r,p);    }    void work()    {        register int i;        Mdf(1,1,N<<1,tm[1]+1,N<<1,a[1]);        for(i=2;i<=N;++i)        {            //printf("update: %d 10 %lld",i+tm[i],a[i]+Gi(1,1,N<<1,i));            Mdf(1,1,N<<1,i+tm[i],N<<1,a[i]+Gi(1,1,N<<1,i));        }        printf("%lld\n",T[1].val);    }}int main(){    freopen("fc.in","r",stdin);    freopen("fc.out","w",stdout);    N=read();    register int i,j;    for(i=1;i<=N;++i) tm[i]=read();    for(i=1;i<=N;++i) a[i]=1ll*read()*tm[i];    bool flag=1;    for(i=1;i<=N;++i) if(tm[1]!=tm[i]) {flag=0;break;}    if(flag==1||N>10000) solve2::work();        else if(N<=10000) solve1::work();    return 0;}

/*    首先 写出一个dp    按照 i+tm[i] 从小到大考虑    维护 前缀的最大值    2019/2/12 19:40~20:02*/#include
    
     #define ll long longusing namespace std;inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 1000005 ll a[MN],ti[MN],t[MN],n,ans,f[MN];inline void rw(ll &x,ll y){if(y>x)x=y;}inline void C(int p,ll val){for(;p<=n;p+=(p&(-p))) rw(t[p],val);}inline ll G(int p){ll r=0;for(;p>0;p-=(p&(-p))) rw(r,t[p]);return r;}std::vector
     
       g[MN];int main(){    freopen("fc.in","r",stdin);    freopen("fc.out","w",stdout);    n=read();    register int i;    for(i=1;i<=n;++i) ti[i]=read();    for(i=1;i<=n;++i) a[i]=1ll*read()*ti[i];    for(i=1;i<=n;++i)    {        if(i+ti[i]<=n) g[i+ti[i]].push_back(i);        for(int j=g[i].size()-1;~j;--j) C(g[i][j],f[g[i][j]]);        f[i]=G(i-ti[i])+a[i];        rw(ans,f[i]);     }    return 0*printf("%lld\n",ans);}

T2、原样输出（copy）

Code

//PaperCloud 2019/2/12//40 pts#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define MX 1048580#define mod 1000000007#define MM MX<<1int c[MM][5],fa[MM],step[MM],val[MM];int v[MM],rk[MM],siz[MM];int last=1,cnt=1,Line,K,ans,n;void Insert(int x){    int p=last,np=++cnt;step[np]=step[p]+1;val[np]=1;    for(;p&&!c[p][x];p=fa[p]) c[p][x]=np;    if(!p) fa[np]=1;    else     {        int q=c[p][x];        if(step[q]==step[p]+1) fa[np]=q;        else         {            int nq=++cnt;step[nq]=step[p]+1;            memcpy(c[nq],c[q],sizeof c[q]);            fa[nq]=fa[q];fa[np]=fa[q]=nq;            for(;c[p][x]==q;p=fa[p]) c[p][x]=nq;        }        }    last=np;}inline int Num(char x){    if(x=='A') return 1;    if(x=='C') return 2;    if(x=='G') return 3;    if(x=='T') return 4;}inline void putch(int x){    if(x==1) putchar('A');    if(x==2) putchar('C');    if(x==3) putchar('G');    if(x==4) putchar('T');}namespace solve1{    char str[MX];int st[MX],nn;    inline void dfs2(int x)    {        register int i;        ans++;ans%=mod;        for(int j=1;j<=nn;++j) putch(st[j]);puts("");        for(i=1;i<=4;++i) if(c[x][i])        {            st[++nn]=i;            dfs2(c[x][i]);            --nn;        }    }    inline void ddd()    {        register int i,j;        for(i=1;i<=cnt;++i) ++v[step[i]];        for(i=1;i<=n;++i) v[i]+=v[i-1];        for(i=1;i<=cnt;++i) rk[v[step[i]]--]=i;        for(i=cnt;i;--i) siz[i]=1;        for(i=cnt;i;--i)for(j=1;j<5;++j)if(c[rk[i]][j]) (siz[rk[i]]+=siz[c[rk[i]][j]])%=mod;        ans=siz[1]%mod;    }    void work()    {        register int i;        scanf("%s",str+1);n=strlen(str+1);        for(i=1;i<=n;++i) Insert(Num(str[i]));        scanf("%d",&K);        if(K==0) ddd();else dfs2(1);        printf("%d\n",ans);    }}int main(){    freopen("copy.in","r",stdin);    freopen("copy.out","w",stdout);    scanf("%d",&Line);    if(Line==1) solve1::work();    //else if(Line<3) solve2::work();    return 0;}

/*    考虑每个串建一个后缀自动机 并且把他们连在一起    具体的 如果在当前点失配 就找到下一个包含失配字符的自动机    这样采用的时贪心的思想，每个字符串所对应的状态仍然是唯一的     学习一下读入优化？     2019/2/12 20:26~21:32*/#include
    
     #define ll long long#define mod 1000000007namespace IO{    const int lim=(1<<20)+5;    char buf[lim+5],*S,*T;    inline char gc(){if(S==T){T=(S=buf)+fread(buf,1,lim,stdin);if(S==T)return EOF;}return *S++;}    inline int read()    {        int x;char ch;bool f;        for(f=0;(ch=gc())<'0'||ch>'9';f=ch=='-');        for(x=ch^'0';(ch=gc())>='0'&&ch<='9';x=(x<<1)+(x<<3)+(ch^'0'));        return f?-x:x;    }    inline int Num(char x)    {        if(x=='A') return 0;        else if(x=='C') return 1;        else if(x=='G') return 2;        else if(x=='T') return 3;        else return -1;    }}using namespace IO; const char alpha[4]={'A','C','G','T'};int n,ans,k;class Suf_Automation{    private:    #define MN 1048580    int ch[MN<<1][4],cnt,last,step[MN<<1],sz[MN<<1],fa[MN<<1],rt[MN];    inline void Insert(int R,int x)    {        int np=++cnt,p;step[np]=step[last]+1;        for(p=last;!ch[p][x];p=fa[p]) ch[p][x]=np;        if(!p) fa[np]=R;        else        {            int q=ch[p][x];            if(step[q]==step[p]+1) fa[np]=q;            else            {                int nq=++cnt;step[nq]=step[p]+1;                memcpy(ch[nq],ch[q],sizeof ch[nq]);                fa[nq]=fa[q];fa[q]=fa[np]=nq;                for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq;            }        }        last=np;    }    inline void ins(int i)    {        register char c;        while(!(~Num(c=gc())));        last=rt[i]=++cnt;        for(;~Num(c);c=gc()) Insert(rt[i],Num(c));    }    char st[MN];int tp;    inline void dfs(int x)    {        if(!x) return ;        ++ans;puts(st+1);        for(int al=0;al<4;++al) st[++tp]=alpha[al],dfs(ch[x][al]),st[tp--]='\0';    }    int Dfs(int x)    {        if(!x) return 0;        if(sz[x]) return sz[x];        sz[x]=1;        for(int al=0;al<4;++al) (sz[x]+=Dfs(ch[x][al]))%=mod;        return sz[x];    }    public:    void solve()    {        n=read();register int i,j,al;        for(i=1;i<=n;++i) ins(i);        k=read();        for(i=n-1;i;--i)for(j=rt[i+1]-1;j>=rt[i];--j)for(al=0;al<4;++al)            if(!ch[j][al]) ch[j][al]=ch[rt[i+1]][al];        if(k==1) dfs(1);        else ans=Dfs(1);        printf("%d\n",ans);    }}pac;int main(){    freopen("copy.in","r",stdin);    freopen("copy.out","w",stdout);    pac.solve();    return 0;}

T3、不同的缩写（diff）

Code

/*    每个字符串只需要找出n个子序列即可（越短越好）    二分答案，dinic跑匹配    2019/2/13 12:07~13:00+15:30~16:07*/ #include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))const int MN=305,MS=305,TT=100505;int N,ch[MN][MS][26],len[MN];char s[MN][MS];int trie[MN*MN+10][26],tot,siz[MN*MN+10];char t[MN*MN][MS];int num;std::vector
     
       G[MN];std::queue
      
       
         > que;class Dinic{    private:        const int S=0,T=100500,inf=0x3f3f3f3f;        struct edge{int to,w,nex;}e[TT*2];int cur[TT],hr[TT],d[TT],q[TT],en;        inline void Ins(int f,int t)        {            e[++en]=(edge){t,1,hr[f]};hr[f]=en;            e[++en]=(edge){f,0,hr[t]};hr[t]=en;        }        inline bool bfs()        {            memset(d,0,sizeof d);register int i,j,tp;            for(d[q[i=tp=1]=S]=1;i<=tp;++i)            for(j=hr[q[i]];j;j=e[j].nex)                if(!d[e[j].to]&&e[j].w) d[q[++tp]=e[j].to]=d[q[i]]+1;            return d[T];        }        inline int dfs(int x,int f)        {            if(x==T) return f;register int used=0;            for(int &i=cur[x];i;i=e[i].nex)            if(d[e[i].to]==d[x]+1&&e[i].w)            {                int w=dfs(e[i].to,min(f-used,e[i].w));                used+=w;e[i].w-=w;e[i^1].w+=w;                if(used==f) return used;            }            return d[x]=-1,used;        }    public:        inline void ins(int f,int t){Ins(f,t+N);}        inline void init(){memset(hr,0,sizeof hr);en=1;}        bool check()        {            for(int i=1;i<=N;++i) Ins(S,i);            for(int i=1;i<=tot;++i) Ins(i+N,T);            int maxflow=0;            while(bfs()) memcpy(cur,hr,sizeof cur),maxflow+=dfs(S,inf);            return maxflow==N;        }        inline void G()        {            for(int i=1;i<=N;++i) for(int j=hr[i];j;j=e[j].nex)            if(!e[j].w&&e[j].to) {puts(t[e[j].to-N]);break;}        }}pac;bool chk(int mid){    register int i,j,S;pac.init();    for(i=1;i<=N;++i) for(S=G[i].size(),j=0;j
        
         =N) return;        }    }}int main(){    freopen("diff.in","r",stdin);    freopen("diff.out","w",stdout);    scanf("%d",&N);    register int i,j;    for(i=1;i<=N;++i) scanf("%s",s[i]+1),len[i]=strlen(s[i]+1);    for(i=1;i<=N;++i)    {        memset(ch[i][len[i]],0x3f,sizeof ch[i][len[i]]);        for(j=len[i]-1;~j;--j)            memcpy(ch[i][j],ch[i][j+1],sizeof ch[i][j]),            ch[i][j][s[i][j+1]-'a']=j+1;    }    for(i=1;i<=N;++i) num=0,bfs(i);    int mid,l=1,r=300,ans=-1;    for(;l<=r;mid=(l+r)>>1,chk(mid)?(ans=mid,r=mid-1):(l=mid+1));    if(ans==-1) return 0*puts("-1");    printf("%d\n",ans);getans(ans);return 0;}