BZOJ 4199 [Noi2015] 品酒大会

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4199

题意：去 UOJ 或者 LOJ 看吧。

差异这题的加强版？

考虑到如果一对串 r 相似则 0~r-1 均相似，所以可以直接只考虑一对串的最长相似，最后答案做一下前缀和即可。

一对串的最长相似... 不就是这两个后缀的 lcp 吗...

于是翻转串后建后缀自动机转后缀树，对于树上节点维护 mx 和 mn 即可，因为有负负得正。

另外交完 BZ 建议也去 UOJ 交一发... 被 hack 数据洗礼后的程序将会更强大。

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 600010
#define ll long long
#define inf 1000000000000000000ll
using namespace std;
inline int read()
{
    int 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*10+ch-'0';ch=getchar();}
    return x*f;
}
struct zgz
{
    int next,to;
}edge[N];
int head[N],cnt=1;
void add(int from,int to)
{
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
ll ans1[N],ans2[N];
ll Mx_(ll a,ll b)
{return a>b?a:b;}
ll Mn_(ll a,ll b)
{return a<b?a:b;}
namespace SAM
{
    int ch[N][26],fail[N];
    int mx[N],sz[N];
    ll Mx[N],Mn[N];
    int last=1,tot=1;
    void ins(int x,int w)
    {
        int np=++tot,p=last,q,nq;
        last=np,mx[np]=mx[p]+1,sz[np]=1,Mx[np]=Mn[np]=w;
        while(p&&!ch[p][x])ch[p][x]=np,p=fail[p];
        if(p==0){fail[np]=1;return ;}
        q=ch[p][x];
        if(mx[q]==mx[p]+1){fail[np]=q;return ;}
        nq=++tot,mx[nq]=mx[p]+1;
        memcpy(ch[nq],ch[q],sizeof(ch[q]));
        fail[nq]=fail[q],fail[q]=fail[np]=nq;
        while(p&&ch[p][x]==q)ch[p][x]=nq,p=fail[p];
    }
    void build()
    {
        for(int i=2;i<=tot;i++)
        add(fail[i],i);
    }
    bool ok(int x)
    {return Mx[x]!=-inf&&Mn[x]!=inf;}
    void dfs(int x)
    {
        if(!Mn[x]&&!Mx[x])Mn[x]=inf,Mx[x]=-inf;
        for(int i=head[x];i;i=edge[i].next)
        {
            int to=edge[i].to;
            dfs(to);
            if(ok(x)&&ok(to))
            ans2[mx[x]]=Mx_(ans2[mx[x]],Mx_(Mx[x]*Mx[to],Mn[x]*Mn[to]));
            ans1[mx[x]]+=(ll)sz[x]*sz[to];

            Mx[x]=Mx_(Mx[x],Mx[to]);
            Mn[x]=Mn_(Mn[x],Mn[to]);
            sz[x]+=sz[to];
        }
    }
}
int n;
char s[N];
ll a[N];
int main()
{
    n=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=n;i>=1;i--)SAM::ins(s[i]-'a',a[i]);
    for(int i=0;i<=n;i++)ans2[i]=-inf;
    SAM::build();
    SAM::dfs(1);
    for(int i=n-1;i>=0;i--)
    ans2[i]=Mx_(ans2[i],ans2[i+1]),ans1[i]+=ans1[i+1];
    for(int i=0;i<=n-1;i++)
    if(ans1[i])printf("%lld %lld\n",ans1[i],ans2[i]);
    else puts("0 0");
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 600010

#define ll long long

#define inf 1000000000000000000ll

using namespace std;

inline int read()

{

int 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*10+ch-'0';ch=getchar();}

return x*f;

}

struct zgz

{

int next,to;

}edge[N];

int head[N],cnt=1;

void add(int from,int to)

{

edge[cnt].to=to;

edge[cnt].next=head[from];

head[from]=cnt++;

}

ll ans1[N],ans2[N];

ll Mx_(ll a,ll b)

{return a>b?a:b;}

ll Mn_(ll a,ll b)

{return a<b?a:b;}

namespace SAM

{

int ch[N][26],fail[N];

int mx[N],sz[N];

ll Mx[N],Mn[N];

int last=1,tot=1;

void ins(int x,int w)

{

int np=++tot,p=last,q,nq;

last=np,mx[np]=mx[p]+1,sz[np]=1,Mx[np]=Mn[np]=w;

while(p&&!ch[p][x])ch[p][x]=np,p=fail[p];

if(p==0){fail[np]=1;return ;}

q=ch[p][x];

if(mx[q]==mx[p]+1){fail[np]=q;return ;}

nq=++tot,mx[nq]=mx[p]+1;

memcpy(ch[nq],ch[q],sizeof(ch[q]));

fail[nq]=fail[q],fail[q]=fail[np]=nq;

while(p&&ch[p][x]==q)ch[p][x]=nq,p=fail[p];

}

void build()

{

for(int i=2;i<=tot;i++)

add(fail[i],i);

}

bool ok(int x)

{return Mx[x]!=-inf&&Mn[x]!=inf;}

void dfs(int x)

{

if(!Mn[x]&&!Mx[x])Mn[x]=inf,Mx[x]=-inf;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to;

dfs(to);

if(ok(x)&&ok(to))

ans2[mx[x]]=Mx_(ans2[mx[x]],Mx_(Mx[x]*Mx[to],Mn[x]*Mn[to]));

ans1[mx[x]]+=(ll)sz[x]*sz[to];

Mx[x]=Mx_(Mx[x],Mx[to]);

Mn[x]=Mn_(Mn[x],Mn[to]);

sz[x]+=sz[to];

}

int n;

char s[N];

ll a[N];

int main()

{

n=read();

scanf("%s",s+1);

for(int i=1;i<=n;i++)a[i]=read();

for(int i=n;i>=1;i--)SAM::ins(s[i]-'a',a[i]);

for(int i=0;i<=n;i++)ans2[i]=-inf;

SAM::build();

SAM::dfs(1);

for(int i=n-1;i>=0;i--)

ans2[i]=Mx_(ans2[i],ans2[i+1]),ans1[i]+=ans1[i+1];

for(int i=0;i<=n-1;i++)

if(ans1[i])printf("%lld %lld\n",ans1[i],ans2[i]);

else puts("0 0");

}

zgz233

zgz233

BZOJ 4199 [Noi2015] 品酒大会

l1ll5

Comments | NOTHING