Luogu

BZOJ

分析

0/1分数规划+AC自动机+DP。


设 $ans=\sqrt[n]{\prod\limits_{i=1}^na_i}$ 。

那么有 $\ln ans=\frac{1}{n}\sum\limits_{i=1}^{n}\ln a_i$ 。

发现这是一个分数规划的形式。

二分答案 $mid$ ,假设右边大于 $mid$ ,可以化为 $\sum\limits_{i=1}^n(\ln a_i-mid)>0$ 。

那么只要求出这个东西的最大值即可判定 $mid$ 是否合法。

我们把所有小串建一个AC自动机,然后在上面DP即可求出最大值。

具体的DP方法是设 $f[i][j]$ 表示前 $i$ 个字符,匹配到了AC自动机上的 $j$ 节点的最大值。

转移就直接枚举子节点就行了。

至于怎么求方案,DP时记一下从哪转移过来即可。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1501+10;
const double eps=1e-6;

int n,m;
char T[N],S[N],ans[N];
double V[N],val[N],f[N][N];
int ch[N][10],fail[N],cnt[N],tot=0;
pair<int,int> pre[N][N];

inline void insert(char* s,double v) {
    int l=strlen(s+1),now=0;
    for (re int i=1;i<=l;++i) {
        int w=s[i]-'0';
        if (!ch[now][w]) ch[now][w]=++tot;
        now=ch[now][w];
    }
    val[now]+=v,++cnt[now];
}

inline void getfail() {
    queue<int> Q;
    for (re int i=0;i<10;++i)
        if (ch[0][i]) Q.push(ch[0][i]);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=0;i<10;++i) {
            if (ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],Q.push(ch[u][i]);
            else ch[u][i]=ch[fail[u]][i];
        }
        val[u]+=val[fail[u]],cnt[u]+=cnt[fail[u]];
    }
}

inline void print(int i,int j) {
    if (!i) return;
    print(i-1,pre[i][j].first);
    ans[i]=pre[i][j].second+'0';
}

inline int check(double mid) {
    memset(f,-0x3f,sizeof(f)); double inf=-f[0][0]; f[0][0]=0;
    for (re int i=1;i<=n;++i) {
        for (re int j=0;j<=tot;++j) {
            if (fabs(f[i-1][j]+inf)<1) continue;
            if (T[i]=='.') {
                for (re int k=0;k<10;++k) {
                    int v=ch[j][k];
                    if (f[i-1][j]+val[v]-cnt[v]*mid>f[i][v]) {
                        f[i][v]=f[i-1][j]+val[v]-cnt[v]*mid;
                        pre[i][v]=make_pair(j,k);
                    }
                }
            } else {
                int k=T[i]-'0',v=ch[j][k];
                if (f[i-1][j]+val[v]-cnt[v]*mid>f[i][v]) {
                    f[i][v]=f[i-1][j]+val[v]-cnt[v]*mid;
                    pre[i][v]=make_pair(j,k);
                }
            }
        }
    }
    int pos=0;
    for (re int i=1;i<=tot;++i)
        if (f[n][i]>f[n][pos]) pos=i;
    if (f[n][pos]>eps) { print(n,pos); return 1; }
    else return 0;
}

int main() {
    n=read(),m=read(); double L=0,R=0;
    scanf("%s",T+1);
    for (re 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) {
        double mid=(L+R)/2;
        if (check(mid)) L=mid;
        else R=mid;
    }
    for (re int i=1;i<=n;++i) putchar(ans[i]); puts("");
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 22 PM