【BJOI 2019】奧術神杖

題意

你有一個長度為 $n$ 的模板串（由 $0-9$ 這 $10$ 個數字和通配符 $.$ 組成），還有 $m$ 個匹配串（只由 $0-9$ 這 $10$ 個數字組成），每個匹配串有一個魔力值 $v_i$。你要把模板串的每個 $.$ 都換成一個數字，使得模板串的魔力值最大。模板串的魔力值定義為：模板串中每出現一次任意一個匹配串 $s_i$，字符串的魔力就 $\times v_i$。最終魔力值開 $c$ 次方根，$c$ 為模板串中出現的匹配串的總數。

$1\le n,m,s\le 1501,\space 1\le v_i\le 10^9$

題解

王·能過就行·子健

顯然只要三個 $10^9$ 大小的數乘起來就爆 $long\space long$ 了（即 $\prod v_i$ 會很大），而高精度開根既難寫又爆復雜度（光乘法就爆時間了），所以不能直接按題目的公式求。

如果你沒學過數學（比如我），可以把所有 $v_i$ 各自開 $c$ 次方根再相乘，但即使開 $long\space double$ 也會爆精度，不過可以拿 $80$ 分。

如果你學過數學，應該記得高一數學必修 $1$ 中有一章講了關于 $log$ 的各種性質，其中有兩條是

$$\log_a{MN} = \log_a{M}+\log_a{N}$$

$$\log_a{N}^k = k\times \log_a{N}$$

其中 $a$ 可以是任意實底數。

第一條式子中的 $MN$ 可以拓展成任意多個乘數，等號右邊就會得到一堆 $log$ 值相加。簡單地說就是因為冪值相乘等于指數相加（比如 $2^4$ 變成 $2^5$ 次方，值乘了 $2$，但指數只加了 $1$）。

具體證明可以去翻書。

?

把兩個公式組合一下，就可以推這題的公式

$$ans = \sqrt[c]{v_1\times v_2\times ...\times v_k} = (v_1\times v_2\times ...\times v_k)^{\frac{1}{c}}$$

兩邊同時取以一個實數 $a$ 為底的對數，得到

$$\log_a{ans} = \log_a{(v_1\times v_2\times ...\times v_k)^{\frac{1}{c}}}$$

$$\log_a{ans} = \frac{1}{c}\times \log_a{(v_1\times v_2\times ...\times v_k)}$$

$$\log_a{ans} = \frac{1}{c}(\log_a{v_1}+\log_a{v_2}+...+\log_a{v_k})$$

因為這題只需要你求方案，所以你只要確保不同方案之間的相對魔力值即可，不用維護具體的 $ans$ 值，所以可以把 $ans$ 取 $log$，$log$ 的底數 $a$ 也可以隨便取，大部分人應該都取的是自然對數 $e$。

?

不難發現等號右邊變成了一個類似于平均數的東西，仔細觀察即可發現，把所有匹配串的魔力值 $v_i$ 取 $ln$ 后，你要使出現的所有匹配串的 $v_i$ 的平均數最大。

平均數最大這種東西就是套路的01分數規劃……

具體做法就是，二分平均數 $x$，然后把所有匹配串的 $a_i$ 都減去 $x$，問題就變成了如何使 $v_i$ 之和最大。在所有模板串組成的 AC 自動機上 $dp$ 即可。

AC 自動機上 $dp$ 的狀態就是 $f_{i,j}$ 表示確定模板串的前 $i$ 位，按模板串的前 $i$ 位跑 AC 自動機到達的點的編號為 $j$ 時，模板串的魔力值最大是多少。

然后判斷一下模板串的第 $i$ 位是不是通配符就行了，是的話就可以往任意兒子轉移，不是的話就要沿對應的字符邊轉移。

時間復雜度 $O(10ns\log{\frac{\ln v_{max}}{eps}})$。

這他嗎什么復雜度，怎么跑過的……能過就行了

#include<bits/stdc++.h>
#define N 1505
#define inf 1e99
#define eps 1e-6
using namespace std;
inline int read(){
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    if(f) return x;
    return 0;
}
int n,m;
char T[N];
namespace AC{
    int cnt,ch[N][12],sum[N]; double val[N];
    inline void ins(char *s,double v){
        int u=0,len=strlen(s),c;
        for(int i=0;i<len;++i){
            c=s[i]-'0';
            if(!ch[u][c]) ch[u][c]=++cnt;
            u=ch[u][c];
        }
        ++sum[u], val[u]+=v;
    }
    int que[N],l,r,fail[N];
    void BuildAC(){
        fail[0]=-1, que[l=r=1]=0;
        while(l<=r){
            int u=que[l++];
            for(int i=0;i<10;++i)
                if(!ch[u][i]) ch[u][i]=ch[fail[u]][i];
                else fail[ch[u][i]]=ch[fail[u]][i], que[++r]=ch[u][i];
        }
        for(int i=2;i<=r;++i){
            sum[que[i]]+=sum[fail[que[i]]];
            val[que[i]]+=val[fail[que[i]]];
            //cout<<que[i]<<' '<<fail[que[i]]<<' '<<sum[que[i]]<<' '<<val[que[i]]<<endl;
        }
    }
    
    double f[N][N]; int g[N][N][2]; char ansStr[N];
    double DP(double x){
        //cout<<x<<endl;
        for(int j=0;j<=cnt;++j) val[j]-=sum[j]*x;
        for(int i=0;i<=n;++i)
            for(int j=0;j<=cnt;++j)
                f[i][j]=-inf;
        f[0][0]=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<=cnt;++j){
                if(f[i][j]==-inf) continue;
                if(T[i]=='.'){
                    for(int k=0;k<10;++k){
                        int _j=ch[j][k];
                        if(f[i+1][_j]<f[i][j]+val[_j]){
                            f[i+1][_j]=f[i][j]+val[_j];
                        }
                    }
                }
                else{
                    int k=T[i]-'0', _j=ch[j][k];
                    if(f[i+1][_j]<f[i][j]+val[_j]) f[i+1][_j]=f[i][j]+val[_j];
                }
            }
        }
        for(int i=0;i<=cnt;++i) val[i]+=sum[i]*x;
        int ans=0;
        for(int j=1;j<=cnt;++j) if(f[n][j]>f[n][ans]) ans=j;
        //cout<<f[n][ans]<<endl;
        return f[n][ans];
    }
    void _DP(double x){
        for(int j=0;j<=cnt;++j) val[j]-=sum[j]*x;
        for(int i=0;i<=n;++i)
            for(int j=0;j<=cnt;++j)
                f[i][j]=-inf;
        f[0][0]=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<=cnt;++j){
                if(f[i][j]==-inf) continue;
                if(T[i]=='.'){
                    for(int k=0;k<10;++k){
                        int _j=ch[j][k];
                        if(f[i+1][_j]<f[i][j]+val[_j]){
                            f[i+1][_j]=f[i][j]+val[_j],
                            g[i+1][_j][0]=j, g[i+1][_j][1]=k;
                        }
                    }
                }
                else{
                    int k=T[i]-'0', _j=ch[j][k];
                    if(f[i+1][_j]<f[i][j]+val[_j])
                        f[i+1][_j]=f[i][j]+val[_j],
                        g[i+1][_j][0]=j, g[i+1][_j][1]=k;
                }
            }
        }
        for(int i=0;i<=cnt;++i) val[i]+=sum[i]*x;
        int ans=0;
        for(int j=1;j<=cnt;++j) if(f[n][j]>f[n][ans]) ans=j;
        for(int i=n;i>0;--i){
            ansStr[i-1]=g[i][ans][1]+'0';
            ans=g[i][ans][0];
        }
    }
}
using namespace AC;
int main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read(), m=read(); scanf("%s",T);
    char S[N]; double V;
    for(int i=1;i<=m;++i){
        scanf("%s%lf",S,&V);
        ins(S,log(V));
    }
    BuildAC();
    double l=0, r=log(1e9+1), mid, ans=0;
    while(r-l>eps){
        mid=(l+r)/2;
        if(DP(mid)>0) ans=mid, l=mid;
        else r=mid;
    }
    //cout<<ans<<endl;
    _DP(ans);
    printf("%s\n",ansStr);
    return 0;
}

總結：

1. 這類題不能直接 $dp$ 求最大平均數。因為求最大平均數這種問題，除了分數規劃外（即二分答案），只能在某些情況下用貪心（比如從大到小取）。

? ? 若不能貪心，我們不能把上述 $dp$ 的值直接記為最大平均數 或者同時記一個最小的匹配數量。考慮平均數這個東西的本質，對于到達同一狀態的兩種情況，可能一種情況匹配的數少，平均數也更小；但把兩種情況同時加入一個新數，這種情況的新平均數就可能比另一種情況的新平均數大了。比如兩個數集 $\{10\}$ 和 $\{9,9,9,14\}$，前者的平均數是 $10$，后者的平均數是 $10.25$；但把兩個數集同時加入一個數 $11$，前者的平均數變成了 $10.5$，后者的平均數變成了 $10.4$。所以如果用 $dp$ 求最大平均數，必須再開一維狀態記匹配的串數（即要求多少個數的平均數），但匹配的串數可能很多，再開一維狀態的話時空復雜度都不能承受。所以只能分數規劃。

2. 這道題告訴我們一定要學好數學這門文化課，否則會被數學殺。