@Jerusalem 2015-11-13T16:34:37.000000Z 字数 3427 阅读 1437

### HDU2296

#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>using namespace std;const int maxnode=300005,sigma=26,maxn=20005;queue<int> Q;vector<int> G[maxnode];int num[maxnode];string S[maxn];int w[maxn];int f[maxn];struct Node{    int ls,rs;    int w;    int Lazy;    Node(){        ls=rs=0;        w=0;        Lazy=0;    }    void Clear(){        ls=rs=0;        w=0;        Lazy=0;    }};struct Segement_Tree{    Node tree[maxnode*4];    int root,num;    Segement_Tree(){        root=num=0;    }    void Clear(){        root=num=0;    }    void MakeTree(int& root,int l,int r){        root=++num;        tree[root].Clear();        if(l==r)            return;        int mid=(l+r)/2;        MakeTree(tree[root].ls,l,mid);        MakeTree(tree[root].rs,mid+1,r);    }    void PushDown(int root){        tree[tree[root].ls].Lazy=max(tree[tree[root].ls].Lazy,tree[root].Lazy);        tree[tree[root].rs].Lazy=max(tree[tree[root].rs].Lazy,tree[root].Lazy);        tree[root].Lazy=0;    }    void Maintain(int root){        tree[root].w=max(tree[root].Lazy,max(tree[tree[root].ls].w,tree[tree[root].rs].w));    }    void Update(int root,int l,int r,int y1,int y2,int Set){        if(y1<=l&&r<=y2){            tree[root].Lazy=max(tree[root].Lazy,Set);        }        else{            PushDown(root);            int mid=(l+r)/2;            if(y1<=mid)                Update(tree[root].ls,l,mid,y1,y2,Set);            else                Maintain(tree[root].ls);            if(mid<y2)                Update(tree[root].rs,mid+1,r,y1,y2,Set);            else                Maintain(tree[root].rs);        }        Maintain(root);    }    int Query(int root,int l,int r,int y1,int y2){        if(y1<=l&&r<=y2)            return tree[root].w;        int mid=(l+r)/2;        PushDown(root);        Maintain(tree[root].ls);        Maintain(tree[root].rs);        int ans=0;        if(y1<=mid)            ans=max(ans,Query(tree[root].ls,l,mid,y1,y2));        if(mid<y2)            ans=max(ans,Query(tree[root].rs,mid+1,r,y1,y2));        return ans;    }};struct Trie{    int tot;    int num;    int ch[maxnode][sigma];    int f[maxnode];    vector<int> G[maxnode];    int l[maxnode];    int r[maxnode];    bool val[maxnode];    Trie(){        tot=1;        num=0;        memset(ch,0,sizeof(ch));        memset(f,0,sizeof(f));        memset(val,false,sizeof(val));    }    void Clear(){        tot=1;        num=0;        memset(ch[0],0,sizeof(ch[0]));        memset(val,false,sizeof(val));        for(int i=0;i<maxnode;i++)            G[i].clear();    }    int newnode(){        memset(ch[tot],0,sizeof(ch[tot]));        return tot++;    }    int idx(char a){        return a-'a';    }    void Insert(string s){        int len=s.length();        int u=0;        for(int i=0;i<len;i++){            if(!ch[u][idx(s[i])])                ch[u][idx(s[i])]=newnode();            u=ch[u][idx(s[i])];        }        val[u]=true;    }    void GetLine(int u){        l[u]=num;        for(int i=0;i<G[u].size();i++){            int v=G[u][i];            num++;            GetLine(v);        }        r[u]=++num;    }    void Build(){        while(!Q.empty())            Q.pop();        for(int i=0;i<sigma;i++)            if(ch[0][i]){                f[ch[0][i]]=0;                Q.push(ch[0][i]);                G[0].push_back(ch[0][i]);            }        while(!Q.empty()){            int u=Q.front();            Q.pop();            for(int i=0;i<sigma;i++){                if(!ch[u][i])                    continue;                int v=ch[u][i],r=f[u];                while(r&&!ch[r][i])                    r=f[r];                Q.push(v);                f[v]=ch[r][i];                G[f[v]].push_back(v);            }        }        GetLine(0);    }};Trie Aho_Corasick;Segement_Tree DfsOrder;int n,T;void Solve(){    for(int k=1;k<=T;k++){        cin>>n;        Aho_Corasick.Clear();        memset(num,0,sizeof(num));        for(int i=1;i<=n;i++){            cin>>S[i]>>w[i];            Aho_Corasick.Insert(S[i]);        }        int ans=0;        DfsOrder.Clear();        Aho_Corasick.Build();        int l=0,r=Aho_Corasick.num;        DfsOrder.MakeTree(DfsOrder.root,l,r);        for(int i=1;i<=n;i++){            int len=S[i].length();            int u=0;            int tmp=0;            for(int j=0;j<len;j++){                u=Aho_Corasick.ch[u][S[i][j]-'a'];                tmp=max(tmp,DfsOrder.Query(DfsOrder.root,l,r,Aho_Corasick.l[u],Aho_Corasick.l[u])+w[i]);            }            DfsOrder.Update(DfsOrder.root,l,r,Aho_Corasick.l[u],Aho_Corasick.r[u],tmp);            ans=max(ans,tmp);        }        printf("Case #%d: %d\n",k,ans);    }}void ReadData(){    freopen("4117.in","r",stdin);    freopen("4117.out","w",stdout);    ios::sync_with_stdio(false);    cin>>T;}void Close(){    fclose(stdin);    fclose(stdout);}int main(){    ReadData();    Solve();    Close();    return 0;}

• 私有
• 公开
• 删除