洛谷P5319 [BJOI2019] 奥术神杖 题解

题目链接：P5319 [BJOI2019] 奥术神杖

题意：

Bezorath 大陆抵抗地灾军团入侵的战争进入了僵持的阶段，世世代代生活在 Bezorath 这片大陆的精灵们开始寻找远古时代诸神遗留的神器，试图借助神器的神秘力量帮助她们战胜地灾军团。

在付出了惨痛的代价后，精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后，神杖上镶嵌的奥术宝石已经残缺，神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石，并重金悬赏天下能工巧匠修复这件神杖。

你作为神术一脉第五百零一位传人，接受了这个艰巨而神圣的使命。

神杖上从左到右镶嵌了 \(n\) 颗奥术宝石，奥术宝石一共有 \(10\) 种，用数字 0123456789 表示。有些位置的宝石已经残缺，用 . 表示，你需要用完好的奥术宝石填补每一处残缺的部分（每种奥术宝石个数不限，且不能够更换未残缺的宝石）。古老的魔法书上记载了 \(m\) 种咒语 \((S_i,V_i)\) ，其中 \(S_i\) 是一个非空数字串，\(V_i\) 是这种组合能够激发的神力。

神杖的初始神力值 \(\mathsf{Magic} = 1\)，每当神杖中出现了连续一段宝石与 \(S_i\) 相等时，神力值 \(\mathsf{Magic}\) 就会乘以 \(V_i\)。但神杖如果包含了太多咒语就不再纯净导致神力降低：设 \(c\) 为神杖包含的咒语个数（若咒语类别相同但出现位置不同视为多次），神杖最终的神力值为 $ $。（若 \(c = 0\) 则神杖最终神力值为 \(1\) ）

例如有两种咒语 \((01,3)\) 、\((10,4)\) ，那么神杖 0101 的神力值为 \(\sqrt[3]{ 3 \times 4 \times 3}\)

你需要使修复好的神杖的最终的神力值最大，输出任何一个解即可。

输入格式：

第一行两个正整数 \(n,m\) ，表示宝石数和咒语数。

第二行为一个长度为 \(n\) 的字符串 \(T\) ，表示初始的神杖。

接下来 \(m\) 行每行一个非空数字串 \(S_i\) 和一个正整数 \(V_i\) ，表示每种咒语。

输出格式：

输出最终神杖上从左到右镶嵌的宝石，多解时任意输出一个即可。

数据范围：

\(1 \le n,m \le 1501,~1 \le (\sum_{i=1}^{m} |S_i|) \le 1501,~1 \le V_i \le 10^9\) ，保证 \(S_i\) 互不相同。

记神力值 \(\mathrm{Ans} = \sqrt[c]{\prod_{i=1}^c w_i}\) ，对两侧取对数得 \[ \ln \mathrm{Ans} = \frac{1}{c}\sum_{i=1}^c w_i > x \] 显然这是个01分数规划。考虑二分 \(x\) ，则 \[ \frac{1}{c}\sum_{i=1}^c w_i > x\, \Rightarrow\,\sum_{i=1}^c (w_i - x) > 0 \] 问题就变成了最大化 \(w_i\) 的和。

那么对 \(S_i\) 建 AC 自动机，并设 \(f(i,j)\) 为考虑 \(T\) 的前 \(i\) 位且当前在节点 \(j\) 时的最大值，则 \[ f(i + 1,c) \,\big\uparrow\, f(i,j) + v_{c}\quad (c:=j\to s_{i+1},~t_{i+1}=s_{i+1}\,\lor\,t_{i+1}=\mathtt{.}) \] 时间复杂度 \[ \mathcal{O}\left(n|\Sigma|\cdot\sum |S_i| \log\left(\epsilon^{-1} \log (\max V_i)\right)\right) \] 其中 \(\epsilon=10^{-8}\) 表示精度，\(|\Sigma|=10\) 表示字符集大小。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
#define INF 0x3f3f3f3f3f3f3f3f
const double eps = 1e-8;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
int dcmp(double x) { if(fabs(x) <= eps) return 0; return x > eps ? 1 : -1; }
#define N ((int)(2019))

char t[N], ans[N]; queue<int> q;
double val[N], f[N][N];
int n, tot, ch[N][12], sum[N], fail[N], g[N][N][2];
void insert(char *s, double v)
{
    int u = 0;
    for(int i = 1, c; s[i]; i++)
    {
        c = s[i] - '0';
        if(!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    ++sum[u]; val[u] += v;
}
void build()
{
    for(int i = 0; i < 10; i++) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        sum[u] += sum[fail[u]]; val[u] += val[fail[u]];
        for(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];
        }
    }
}
double check(double mid)
{
    for(int i = 0; i <= tot; i++) val[i] -= sum[i] * mid;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= tot; j++) f[i][j] = -1e111;
    f[0][0] = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= tot; j++) if(f[i][j] > -1e100)
            for(int k = 0; k < 10; k++) if(t[i + 1] == '.' || t[i + 1] - '0' == k)
            {
                int c = ch[j][k];
                if(dcmp(f[i][j] + val[c] - f[i + 1][c]) > 0)
                {
                    f[i + 1][c] = f[i][j] + val[c];
                    g[i + 1][c][0] = j, g[i + 1][c][1] = k;
                }
            }
    for(int i = 0; i <= tot; i++) val[i] += sum[i] * mid;
    int pos = 0;
    for(int i = 1; i <= tot; i++) if(dcmp(f[n][i] - f[n][pos]) > 0) pos = i;
    for(int i = n, now = pos; i; i--) {
        ans[i] = g[i][now][1] + '0', now = g[i][now][0];
    }
    return f[n][pos];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> n >> m >> (t + 1);
    for(int i = 1, v; i <= m; i++)
    { 
        static char s[N];
        cin >> (s + 1) >> v; insert(s, log((double)v));
    }
    build(); double l = 0, r = log((double)1e9);
    while(fabs(r - l) > eps)
    {
        double mid = (l + r) / 2.0;
        if(dcmp(check(mid)) > 0) l = mid; else r = mid;
    }
    check(l); cout << (ans + 1) << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/5m7wm9eu

[2] https://www.luogu.com.cn/article/dunslmu5

---

题外话：

这 tag 太长了首页显示会有问题，完整如下：

tag: ["算法","数据结构","字符串","DP","01分数规划"]

AC 自动机怎么不是数据结构？

AC 自动机就是数据结构。AC 自动机就是数据结构。