題意

你有一個長度為 $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}})$。

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

1 #include<bits/stdc++.h> 2 #define N 1505 3 #define inf 1e99 4 #define eps 1e-6 5 using namespace std; 6 inline int read(){ 7 int x=0; bool f=1; char c=getchar(); 8 for(;!isdigit(c);c=getchar()) if(c=='-') f=0; 9 for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0'); 10 if(f) return x; 11 return 0; 12 } 13 int n,m; 14 char T[N]; 15 namespace AC{ 16 int cnt,ch[N][12],sum[N]; double val[N]; 17 inline void ins(char *s,double v){ 18 int u=0,len=strlen(s),c; 19 for(int i=0;i<len;++i){ 20 c=s[i]-'0'; 21 if(!ch[u][c]) ch[u][c]=++cnt; 22 u=ch[u][c]; 23 } 24 ++sum[u], val[u]+=v; 25 } 26 int que[N],l,r,fail[N]; 27 void BuildAC(){ 28 fail[0]=-1, que[l=r=1]=0; 29 while(l<=r){ 30 int u=que[l++]; 31 for(int i=0;i<10;++i) 32 if(!ch[u][i]) ch[u][i]=ch[fail[u]][i]; 33 else fail[ch[u][i]]=ch[fail[u]][i], que[++r]=ch[u][i]; 34 } 35 for(int i=2;i<=r;++i){ 36 sum[que[i]]+=sum[fail[que[i]]]; 37 val[que[i]]+=val[fail[que[i]]]; 38 //cout<<que[i]<<' '<<fail[que[i]]<<' '<<sum[que[i]]<<' '<<val[que[i]]<<endl; 39 } 40 } 41 42 double f[N][N]; int g[N][N][2]; char ansStr[N]; 43 double DP(double x){ 44 //cout<<x<<endl; 45 for(int j=0;j<=cnt;++j) val[j]-=sum[j]*x; 46 for(int i=0;i<=n;++i) 47 for(int j=0;j<=cnt;++j) 48 f[i][j]=-inf; 49 f[0][0]=0; 50 for(int i=0;i<n;++i){ 51 for(int j=0;j<=cnt;++j){ 52 if(f[i][j]==-inf) continue; 53 if(T[i]=='.'){ 54 for(int k=0;k<10;++k){ 55 int _j=ch[j][k]; 56 if(f[i+1][_j]<f[i][j]+val[_j]){ 57 f[i+1][_j]=f[i][j]+val[_j]; 58 } 59 } 60 } 61 else{ 62 int k=T[i]-'0', _j=ch[j][k]; 63 if(f[i+1][_j]<f[i][j]+val[_j]) f[i+1][_j]=f[i][j]+val[_j]; 64 } 65 } 66 } 67 for(int i=0;i<=cnt;++i) val[i]+=sum[i]*x; 68 int ans=0; 69 for(int j=1;j<=cnt;++j) if(f[n][j]>f[n][ans]) ans=j; 70 //cout<<f[n][ans]<<endl; 71 return f[n][ans]; 72 } 73 void _DP(double x){ 74 for(int j=0;j<=cnt;++j) val[j]-=sum[j]*x; 75 for(int i=0;i<=n;++i) 76 for(int j=0;j<=cnt;++j) 77 f[i][j]=-inf; 78 f[0][0]=0; 79 for(int i=0;i<n;++i){ 80 for(int j=0;j<=cnt;++j){ 81 if(f[i][j]==-inf) continue; 82 if(T[i]=='.'){ 83 for(int k=0;k<10;++k){ 84 int _j=ch[j][k]; 85 if(f[i+1][_j]<f[i][j]+val[_j]){ 86 f[i+1][_j]=f[i][j]+val[_j], 87 g[i+1][_j][0]=j, g[i+1][_j][1]=k; 88 } 89 } 90 } 91 else{ 92 int k=T[i]-'0', _j=ch[j][k]; 93 if(f[i+1][_j]<f[i][j]+val[_j]) 94 f[i+1][_j]=f[i][j]+val[_j], 95 g[i+1][_j][0]=j, g[i+1][_j][1]=k; 96 } 97 } 98 } 99 for(int i=0;i<=cnt;++i) val[i]+=sum[i]*x; 100 int ans=0; 101 for(int j=1;j<=cnt;++j) if(f[n][j]>f[n][ans]) ans=j; 102 for(int i=n;i>0;--i){ 103 ansStr[i-1]=g[i][ans][1]+'0'; 104 ans=g[i][ans][0]; 105 } 106 } 107 } 108 using namespace AC; 109 int main(){ 110 //freopen("1.in","r",stdin); 111 //freopen("1.out","w",stdout); 112 n=read(), m=read(); scanf("%s",T); 113 char S[N]; double V; 114 for(int i=1;i<=m;++i){ 115 scanf("%s%lf",S,&V); 116 ins(S,log(V)); 117 } 118 BuildAC(); 119 double l=0, r=log(1e9+1), mid, ans=0; 120 while(r-l>eps){ 121 mid=(l+r)/2; 122 if(DP(mid)>0) ans=mid, l=mid; 123 else r=mid; 124 } 125 //cout<<ans<<endl; 126 _DP(ans); 127 printf("%s\n",ansStr); 128 return 0; 129 } Viev Code

總結：

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

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

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

轉載于:https://www.cnblogs.com/scx2015noip-as-php/p/bjoi2019d1t1.html

總結

以上是生活随笔為你收集整理的【BJOI 2019】奥术神杖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。