要求的东西带个根号,这玩意叫几何平均数,说到平均数,我们就能想到算术平均数(就是一般意义下的平均数),而这个东西是一堆数之积开根号,所以如果每个数取对数,那么乘法会变成加法,开根号变成除法,所以我们只要最大化\(\frac{\sum_i ln_{a_i}}{c}\)就行了
这是一个分数规划的形式,首先二分最终答案\(mid\),然后我们要求最大答案,所以要检查\(\frac{\sum_i ln_{a_i}}{c}\)是否可以\(\ge mid\),可以改成$$\sum_i ln_{a_i}\ge mid*c$$$$\sum_i ln_{a_i}-mid\ge 0$$
所以出现一个串,权值加上\(ln_{a_i}-mid\),并且这是多个串在一个串上匹配,所以可以建出AC自动机后dp,设\(f_{i,j}\),表示放完前\(i\)个字符,在自动机的\(j\)处的最大权值,转移枚举下一位放什么转移(如果下一位确定就只能用那个字符),每到一个点就加上这个点权值,这个点权值为这个点以及跳\(fail\)能到的点的\(\sum ln_{a_i}-mid\).转移时顺便记录从哪转移,就可以倒序输出方案了
实现优秀的话\(eps\)可以开到\(1e-3\)
// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double
using namespace std;
const int N=1500+10;
const db eps=1e-3;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
char cc[N],ss[N],an[N];
db ma,a[N],nm[N],f[N][N];
int n,m,ch[N][10],fl[N],tt,pr[N][N][2];
void inst()
{
scanf("%s",ss+1);
int len=strlen(ss+1),x=0;
db va=log(rd());
ma=max(ma,va);
for(int i=1;i<=len;++i)
{
if(!ch[x][ss[i]-'0']) ch[x][ss[i]-'0']=++tt;
x=ch[x][ss[i]-'0'];
}
a[x]+=va,++nm[x];
}
void bui()
{
queue<int> q;
for(int i=0;i<10;++i)
if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty())
{
int x=q.front();
q.pop();
a[x]+=a[fl[x]],nm[x]+=nm[fl[x]];
for(int i=0;i<10;++i)
{
if(ch[x][i]) fl[ch[x][i]]=ch[fl[x]][i],q.push(ch[x][i]);
else ch[x][i]=ch[fl[x]][i];
}
}
}
void print(int x,int j)
{
if(!x) return;
an[x]=pr[x][j][1]+'0',print(x-1,pr[x][j][0]);
}
int main()
{
n=rd(),m=rd();
scanf("%s",cc+1);
while(m--) inst();
bui();
for(int i=1;i<=tt;++i) f[0][i]=-1e9;
db l=0,r=ma;
while(r-l>eps)
{
db mid=(l+r)/2;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=tt;++j) f[i][j]=-1e9;
for(int j=0;j<=tt;++j)
{
if(fabs(f[i-1][j]-1e9)<1) continue;
int st=0,en=9;
if(cc[i]>='0'&&cc[i]<='9') st=en=cc[i]-'0';
for(int k=st;k<=en;++k)
{
int nt=ch[j][k];
if(f[i][nt]<f[i-1][j]+a[nt]-nm[nt]*mid)
f[i][nt]=f[i-1][j]+a[nt]-nm[nt]*mid,pr[i][nt][0]=j,pr[i][nt][1]=k;
}
}
}
int jj=0;
db mx=f[n][0];
for(int j=1;j<=tt;++j)
if(mx<f[n][j]) mx=f[n][j],jj=j;
if(mx>eps)
{
print(n,jj);
l=mid+eps;
}
else r=mid-eps;
}
for(int i=1;i<=n;++i) putchar(an[i]);
return 0;
}