Loj #3089. 「BJOI2019」奥术神杖

题目描述

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

力量帮助她们战胜地灾军团。

在付出了惨痛的代价后，精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后，神杖上镶嵌的奥术宝石

已经残缺，神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石，并重金悬赏天下能工巧匠修复这件神杖。

你作为神术一脉第五百零一位传人，接受了这个艰巨而神圣的使命。 神杖上从左到右镶嵌了 \(n\) 颗奥术宝石，奥术宝石一共有 \(10\) 种，用数字 0123456789

表示。有些位置的宝石已经残缺，用 . 表示，你需要用完好的奥术宝石填补每一处残缺的部分（每种奥术宝石个数不限，且不能够更换未残缺的宝石）。古老的魔法

书上记载了 \(m\) 种咒语 \((S_i,V_i)\)，其中 \(S_i\) 是一个非空数字串，\(V_i\) 是这种组合能够激发的神力。

神杖的初始神力值 \(\mathrm{Magic} = 1\)，每当神杖中出现了连续一段宝石与 \(S_i\) 相等时，神力值 \(\mathrm{Magic}\) 就会乘以 \(V_i\)。但神杖如果包含

了太多咒语就不再纯净导致神力降低：设 \(c\) 为神杖包含的咒语个数（若咒语类别相同但出现位置不同视为多次），神杖最终的神力值为 \(\sqrt[c]{\mathrm{Magic}}\)。（若 \(c = 0\) 则神杖最终神力值为 \(1\)。）

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

输入格式

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

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

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

输出格式

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

数据范围与提示

\(n,\sum_{i=1}^m|S_i|\leq 150\)。\(V_i\leq 10^9\)

\(\\\)

首先将答案取一个对数，

\[ \displaystyle \log_2^{\sqrt[c]{\prod_{i=1}^c V_i}}=\frac{\sum_{i=1}^c\log_2^{V_i}}{c} \]

要求最大化\(\frac{\sum_{i=1}^c V_i}{c}\)就是裸的\(0/1\)分数规划问题（我竟然没看出来，真是越来越zz了）。具体实现时在\(AC\)自动机上\(DP\)就好了。

代码：

#include
    
     #define ll long long#define N 1505#define eps 1e-8using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;char s[N],t[N];struct trie {    int ch[10];    int cnt,fail;    double sum;}tr[N];int cnt=1;void Insert(char *s,double val) {    int len=strlen(s+1);    int v=1;    for(int i=1;i<=len;i++) {        int j=s[i]-'0';        if(!tr[v].ch[j]) tr[v].ch[j]=++cnt;        v=tr[v].ch[j];    }    tr[v].cnt++;    tr[v].sum+=val;}void build_fail() {    static queue
     
      q;    for(int i=0;i<10;i++) {        if(!tr[1].ch[i]) tr[1].ch[i]=1;        else {            tr[tr[1].ch[i]].fail=1;            q.push(tr[1].ch[i]);        }    }    while(!q.empty()) {        int v=q.front();        q.pop();        tr[v].cnt+=tr[tr[v].fail].cnt;        tr[v].sum+=tr[tr[v].fail].sum;        for(int i=0;i<10;i++) {            if(!tr[v].ch[i]) tr[v].ch[i]=tr[tr[v].fail].ch[i];            else {                int sn=tr[v].ch[i];                tr[sn].fail=tr[tr[v].fail].ch[i];                q.push(sn);            }        }    }}double f[N][N];double tag[N];struct node {    int x,y,type;    node() {}    node(int _x,int _y,int _type) {        x=_x,y=_y,type=_type;    }};node fr[N][N];bool chk(double ans) {    for(int i=1;i<=cnt;i++) tag[i]=tr[i].sum-tr[i].cnt*ans;    for(int i=0;i<=n;i++)        for(int j=1;j<=cnt;j++)            f[i][j]=-1e9;    f[0][1]=0;    for(int i=0;i
      
       f[i+1][q]) {                        f[i+1][q]=f[i][j]+tag[q];                        fr[i+1][q]=node(i,j,k);                    }                }            } else {                int q=tr[j].ch[s[i+1]-'0'];                if(f[i][j]+tag[q]>f[i+1][q]) {                    f[i+1][q]=f[i][j]+tag[q];                    fr[i+1][q]=node(i,j,s[i+1]-'0');                }            }        }    }    for(int i=1;i<=cnt;i++) if(f[n][i]>0) return 1;    return 0;}void out(int x,int y) {    if(!x) return ;    out(fr[x][y].x,fr[x][y].y);    cout<
       
        0) {            out(n,i);            break ;        }    }    return 0;}