题目描述

uoj131 品酒大会
给一串字符串,每个字符有权值,若有两个完全相等的字符串,可以计算出一个权值为这两个字符串权值的乘积,求这个积最大为多少。

解题报告

貌似sam做起来还不算很难,建出后缀树然后随便dp一下貌似就好了。。。

#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define dbg(x) cerr<<#x" = "<<x<<endl
#define cls(x,y) memset(x,y,sizeof x)
#define rep(i,a,b) for(register int i=(a),i##_end=(b);i<=i##_end;++i)
#define per(i,a,b) for(register int i=(a),i##_st=(b);i>=i##_st;--i)
#define rpg(i,x) for(register int i=fir[x];i;i=e[i].nxt)
typedef pair<int,int> pa;
typedef long long LL;
const LL INF = INT_MAX;
template <typename T>
inline void rd(T &x)
{
    x = 0; int f = 1; char CH = getchar();
    while(!isdigit(CH)) {if(CH=='-')f=0;CH=getchar();}
    while(isdigit(CH)) {x=((x+(x<<2))<<1)+(CH-48);CH=getchar();}
    x=(f==1)?x:-x;  return;
}
const int MXN = 6e5 + 5;
char s[MXN>>1];
int lens,val[MXN>>1];
struct edge{
    int to,nxt;
}e[MXN<<1];
int fir[MXN],tot;
LL mx[MXN],mi[MXN],a[MXN],ans[MXN];
inline void AE(int u,int v) {e[++tot].to=v;e[tot].nxt=fir[u];fir[u]=tot;}
inline void chmax(LL &x,LL y){x=x>y?x:y;}
inline void chmin(LL &x,LL y){x=x<y?x:y;}
struct SAM{
    int p,q,np,nq,last,root,cnt,ch[MXN][26],l[MXN],f[MXN],sz[MXN],num[MXN],w[MXN];
    SAM(){cnt=0;last=root=++cnt;}
    inline void ins(int W,int x) {
        p=last; last=np=++cnt; l[np]=l[p]+1; sz[np]=1; w[np]=W;
        while(p&&!ch[p][x]) ch[p][x]=np,p=f[p];
        if(!p) f[np]=1;
        else {
            q=ch[p][x];
            if(l[p]+1==l[q]) f[np]=q;
            else {
                nq=++cnt; l[nq]=l[p]+1; w[nq]=INF;
                memcpy(ch[nq],ch[q],sizeof ch[q]);
                f[nq]=f[q]; f[q]=f[np]=nq;
                while(ch[p][x]==q&&p) ch[p][x]=nq,p=f[p];
            }
        }
    }
    inline void dfs(int x) {
        mx[x]=-INF; mi[x]=INF; sz[x]=0;
        if(w[x]!=INF) sz[x]=1,mx[x]=mi[x]=w[x];
        rpg(i,x) {
            dfs(e[i].to);
            if(mx[x]!=INF&&mi[x]!=INF&&mx[e[i].to]!=INF&&mi[e[i].to]!=INF)
                chmax(ans[l[x]],max(mx[x]*mx[e[i].to],mi[x]*mi[e[i].to]));
            mx[x]=max(mx[x],mx[e[i].to]); mi[x]=min(mi[x],mi[e[i].to]);
            a[l[x]]+=(LL)sz[x]*sz[e[i].to];
            sz[x]+=sz[e[i].to];
        }
    }

    inline void read() {rd(lens),scanf("%s",s+1);rep(i,1,lens) rd(val[i]);}
    inline void build() {per(i,lens,1) ins(val[i],s[i]-'a');}
    inline void solve() {
        read(),build();
        rep(i,1,cnt) AE(f[i],i);
        rep(i,0,lens) ans[i]=-1e18;
        w[1]=INF;   dfs(1);
        per(i,lens-1,0) a[i]+=a[i+1],chmax(ans[i],ans[i+1]);
        rep(i,0,lens-1) if(a[i]) printf("%lld %lld\n",a[i],ans[i]); else printf("0 0\n");
    }
}sam;
int main()
{
#ifdef iloi
       freopen("test.txt","r",stdin);
#endif
    sam.solve();
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注