题解
(AC)自动机+一些小(trick)
首先看如果当前串的一个子串能匹配某个串,那么就要加上那个串的贡献
这样的多串匹配问题显然只能是(AC)自动机
然后可以先预处理出来在(AC)自动机上每个节点的价值
也就是加上这个点(u)后可以匹配(Num_u)个子串,总价值是(val_u)
看到题目计算的答案是若干个数连乘然后最后还要开个根号
那么就可以想到对每个点的价值取(log)然后将乘法转化成加法,开根号转化成除法
这样题目就变成了求(max (frac{sum val_i}{sum num_i}))
这个东西就可以用分数规划来二分一个(k)
然后对每个(val_u)减去(num_u imes k)
直接跑(dp),(f[i][j])表示匹配到第i个字符,到节点(j)处的最大贡献
如果最后(max (f_{n,i}) > 0)(这里如果写>=0会出问题)就说明这个(k)合法
(dp)的时候记录一下前驱然后输出即可
代码
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 1550 ;
const double EPS = 1e-4 ;
using namespace std ;
char s[M] , st[M] , ans[M] ;
double f[M][M] , val[M] ;
int n , m , v , cnt , nowp , Num[M] ;
struct Node {
int p , c ;
} pre[M][M] ;
struct Trie {
int son[10] , fail ;
double val ; bool End ;
} t[M] ;
inline void insert(double dlt) {
int len = strlen(s + 1) , now = 0 ;
for(int i = 1 , c ; i <= len ; i ++) {
c = s[i] - '0' ;
if(!t[now].son[c])
t[now].son[c] = ++ cnt ;
now = t[now].son[c] ;
}
t[now].val += dlt ; t[now].End = true ;
}
inline void build_fail() {
queue < int > q ;
for(int i = 0 ; i < 10 ; i ++)
if(t[0].son[i])
q.push(t[0].son[i]) ;
while(!q.empty()) {
int u = q.front() ; q.pop() ;
for(int c = 0 ; c < 10 ; c ++) {
if(!t[u].son[c])
t[u].son[c] = t[t[u].fail].son[c] ;
else {
t[t[u].son[c]].fail = t[t[u].fail].son[c] ;
q.push(t[u].son[c]) ;
}
}
}
for(int u = 1 ; u <= cnt ; u ++) {
int p = u ;
while(p) {
val[u] += t[p].val ;
if(t[p].End) ++ Num[u] ;
p = t[p].fail ;
}
}
}
inline double check(double k) {
for(int u = 1 ; u <= cnt ; u ++)
val[u] -= Num[u] * k ;
memset(f , -63 , sizeof(f)) ;
f[0][0] = 0 ;
for(int i = 0 , c ; i < n ; i ++) {
if(st[i + 1] != '.') c = st[i + 1] - '0' ;
for(int u = 0 ; u <= cnt ; u ++) {
if(st[i + 1] != '.') {
if( f[i][u] + val[t[u].son[c]] > f[i + 1][t[u].son[c]] ) {
pre[i + 1][t[u].son[c]].p = u , pre[i + 1][t[u].son[c]].c = c ;
f[i + 1][t[u].son[c]] = f[i][u] + val[t[u].son[c]] ;
}
}
else {
for(c = 0 ; c < 10 ; c ++) {
if( f[i][u] + val[t[u].son[c]] > f[i + 1][t[u].son[c]] ) {
pre[i + 1][t[u].son[c]].p = u , pre[i + 1][t[u].son[c]].c = c ;
f[i + 1][t[u].son[c]] = f[i][u] + val[t[u].son[c]] ;
}
}
}
}
}
double tmp = -1e8 ;
for(int i = 0 ; i <= cnt ; i ++)
tmp = max(tmp , f[n][i]) ;
for(int u = 1 ; u <= cnt ; u ++)
val[u] += Num[u] * k ;
return tmp ;
}
int main() {
scanf("%d%d",&n,&m) ;
scanf("%s",st + 1) ;
for(int i = 1 ; i <= m ; i ++) {
double v ;
scanf("%s",s + 1) ;
scanf("%lf",&v) ;
v = log(v) ;
insert(v) ;
}
build_fail() ;
double l = 0 , r = 1e5 , k ;
while(r - l >= EPS) {
double mid = (l + r) / 2.0 ;
if(check(mid) > 0) l = mid , k = mid ;
else r = mid ;
}
check(k) ;
double tmp = 0 ;
for(int i = 0 ; i <= cnt ; i ++)
if(f[n][i] > tmp) {
tmp = f[n][i] ;
nowp = i ;
}
int w = n ;
while(w) {
ans[w] = pre[w][nowp].c + '0' ;
nowp = pre[w][nowp].p ;
-- w ;
}
printf("%s
",ans + 1) ;
return 0 ;
}