【题解】Luogu P5319 [BJOI2019]奥术神杖

原题传送门

题目让我们最大化$val=\sqrt[k]{\prod_{i=1}^k w_i}$，其中$k$是咒语的个数，$w_i$是第$i$个咒语的神力

看着根号和累乘不爽，我们两边同取$\ln$

$$\ln val=\frac{1}{k}\sum_{i=1}^k \ln w_i$$

易知当$\ln val$最大化时，$val$也最大化。所以我们将问题转化成了最大化$\frac{1}{k}\sum_{i=1}^k \ln w_i$，我们发现这是算数平均数。我们珂以通过二分答案找到它的最大值，问题就是二分答案如何check是否合法：

当$\frac{1}{k}\sum_{i=1}^k \ln w_i>mid$时才合法

即当$\sum_{i=1}^k(w_i-mid)>0$时才合法

我们先对所有咒语建AC自动机，在上面跑dp求出$\sum_{i=1}^k(w_i-mid)$的最大值，判断是否可行

具体dp：就像其他很多AC自动机上的dp一样，设$f[i][j]$表示神杖前$i$个字符，匹配到了AC自动机上$j$号节点，依照套路转移，就是不要忘了题目原有的限制

此算法精度误差较大，但本题还是珂以通过

#include <bits/stdc++.h>

#define db double

#define N 1505

#define eps 1e-6

using namespace std;

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<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

int n,m;

char T[N],s[N],ans[N];

db V[N],val[N],f[N][N];

pair<int,int> pre[N][N];

struct node{

    int son[10],fail,cnt;

    db val;

}tr[N];

int tot=0;

inline void Insert(register char *s,register db v)

{

    int len=strlen(s+1),now=0;

    for(register int i=1;i<=len;++i)

    {

        if(!tr[now].son[s[i]-'0'])

            tr[now].son[s[i]-'0']=++tot;

        now=tr[now].son[s[i]-'0'];

    }

    ++tr[now].cnt,tr[now].val+=v;

}

inline void getfail()

{

    queue<int> q;

    for(register int i=0;i<10;++i)

        if(tr[0].son[i])

            q.push(tr[0].son[i]);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        tr[u].cnt+=tr[tr[u].fail].cnt;

        tr[u].val+=tr[tr[u].fail].val;

        for(register int i=0;i<10;++i)

        {

            if(tr[u].son[i])

            {

                tr[tr[u].son[i]].fail=tr[tr[u].fail].son[i];

                q.push(tr[u].son[i]);

            }

            else

                tr[u].son[i]=tr[tr[u].fail].son[i];

        }

    }

}

inline void updateans(register int i,register int j)

{

    if(!i)

        return;

    updateans(i-1,pre[i][j].first);

    ans[i]=pre[i][j].second+'0';

}

inline bool check(register db mid)

{

    memset(f,-0x3f,sizeof(f));

    db inf=-f[0][0];

    f[0][0]=0;

    for(register int i=1;i<=n;++i)

        for(register int j=0;j<=tot;++j)

        {

            if(fabs(f[i-1][j]+inf)<1)

                continue;

            if(T[i]=='.')

            {

                for(register int k=0;k<10;++k)

                {

                    int v=tr[j].son[k];

                    if(f[i-1][j]+tr[v].val-tr[v].cnt*mid>f[i][v])

                    {

                        f[i][v]=f[i-1][j]+tr[v].val-tr[v].cnt*mid;

                        pre[i][v]=make_pair(j,k);

                    }

                }

            }

            else

            {

                int k=T[i]-'0',v=tr[j].son[k];

                if(f[i-1][j]+tr[v].val-tr[v].cnt*mid>f[i][v])

                {

                    f[i][v]=f[i-1][j]+tr[v].val-tr[v].cnt*mid;

                    pre[i][v]=make_pair(j,k);

                }

            }

        }

    int pos=0;

    for(register int i=1;i<=tot;++i)

        if(f[n][i]>f[n][pos])

            pos=i;

    if(f[n][pos]>eps)

    {

        updateans(n,pos);

        return 1;

    }

    else

        return 0;

}

int main()

{

    n=read(),m=read();

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

    db L=0,R=0;

    for(register int i=1;i<=m;++i)

    {

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

        V[i]=log(read());

        R=max(R,V[i]);

        Insert(s,V[i]);

    }

    getfail();

    while(R-L>eps)

    {

        db mid=(L+R)/2.0;

        if(check(mid))

            L=mid;

        else

            R=mid;

    }

    for(register int i=1;i<=n;++i)

        putchar(ans[i]);

    return 0;

}

巴特西

【题解】Luogu P5319 [BJOI2019]奥术神杖

原题传送门

题目让我们最大化\(val=\sqrt[k]{\prod_{i=1}^k w_i}\)，其中\(k\)是咒语的个数，\(w_i\)是第\(i\)个咒语的神力

看着根号和累乘不爽，我们两边同取\(\ln\)

$$\ln val=\frac{1}{k}\sum_{i=1}^k \ln w_i$$

易知当\(\ln val\)最大化时，\(val\)也最大化。所以我们将问题转化成了最大化\(\frac{1}{k}\sum_{i=1}^k \ln w_i\)，我们发现这是算数平均数。我们珂以通过二分答案找到它的最大值，问题就是二分答案如何check是否合法：

当\(\frac{1}{k}\sum_{i=1}^k \ln w_i>mid\)时才合法

即当\(\sum_{i=1}^k(w_i-mid)>0\)时才合法

我们先对所有咒语建AC自动机，在上面跑dp求出\(\sum_{i=1}^k(w_i-mid)\)的最大值，判断是否可行

具体dp：就像其他很多AC自动机上的dp一样，设\(f[i][j]\)表示神杖前\(i\)个字符，匹配到了AC自动机上\(j\)号节点，依照套路转移，就是不要忘了题目原有的限制

此算法精度误差较大，但本题还是珂以通过

最新文章

热门文章