好久不更博了~~~

题目大意

定义一个数是好的当且仅当这个数 $x$ 满足 $l \leq x \leq r$

定义一个长度为 $n$ 的字符串的价值是所有好的数在这个字符串的出现次数的和。

现在给你 $l,r,n$ 让你构造出满足价值最大的情况下字典序最小的串。

$1 \leq l \leq r \leq 10^{800},1 \leq n \leq 2000$

题解

3500的题一看我就做不来。。
首先我们考虑如果 $r-l$ 比较小怎么办。
一个很显然的想法是将所有的数字暴力建 AC 自动机,然后 dp。
设 $f[i][j]$ 表示填了前 i 位,当前状态为 $j$ 的方案数。预处理 $g_i$ 表示 $i$ 状态能对答案造成的贡献。
求 $g_i$ 只需要把 fail 树建出来,然后求每个点到根的 $g$ 的和就可以了。
然后 $f[i][j] * g[ch] \to f[i+1][ch]$ 转移一下就好了。
现在考虑这个极其繁琐的限制 $l \leq x \leq r$。
想一想,我们如果暴力建出来 trie 树,这个树的形态会是一堆满 $10$ 叉子树,我们可以考虑压缩掉这些满 $10$ 叉子树。我们类比数位 dp 中卡上下界的方法,只需要把刚好“脱离”上下界的那些串建出来就好了。
于是我们现在设 $g[i][j]$ 表示第 $i$ 个点(按照未压缩树结构)继续走 $j$ 步对答案的贡献。然后更新一下就好了,最后转移是 $f[i][j] * \sum_{k=0}^{n-i-1}g[ch][k]\to f[i+1][ch]$
然后只需要前缀和优化一下就能快速转移了。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 30000 + 5;
const int MAXM = 2000 + 5;

int ch[MAXN][10],fail[MAXN];
int g[MAXN][MAXM];
int tot = 1,rt = 1;
int n;
char L[MAXN],R[MAXN];
std::vector<int> G[MAXN];

inline int get(int x,int y){
    if(!ch[x][y]) ch[x][y] = ++tot;
    return ch[x][y];
}

inline void build(){
    int lenL = strlen(L+1),lenR = strlen(R+1);
    int u = 1,v = 1;
    if(lenL == lenR){
        FOR(i,1,lenL){
            if(u == v){
                FOR(k,L[i]-'0'+1,R[i]-'0'-1) g[get(u,k)][lenL-i]++;
                u = get(u,L[i]-'0');
                v = get(v,R[i]-'0');
            }
            else{
                FOR(k,L[i]-'0'+1,9) g[get(u,k)][lenL-i]++;
                u = get(u,L[i]-'0');
                FOR(k,i==1,R[i]-'0'-1) g[get(v,k)][lenR-i]++;
                v = get(v,R[i]-'0');
            }
        }
        g[u][0]++;if(u != v) g[v][0]++;
    }
    else{
        FOR(i,1,lenL){
            FOR(k,L[i]-'0'+1,9) g[get(u,k)][lenL-i]++;
            u = get(u,L[i]-'0');
        }
        FOR(i,1,lenR){
            FOR(k,i==1,R[i]-'0'-1) g[get(v,k)][lenR-i]++;
            v = get(v,R[i]-'0');
        }
        FOR(i,lenL+1,lenR-1) FOR(j,1,9) g[get(rt,j)][i-1]++;
        g[u][0]++;g[v][0]++;
    }
    // ~~~
    std::queue<int> q;
    FOR(i,0,9){
        if(ch[rt][i]) fail[ch[rt][i]] = rt,q.push(ch[rt][i]);
        else ch[rt][i] = rt;
    }
    while(!q.empty()){
        int v = q.front();q.pop();
        FOR(i,0,n) g[v][i] += g[fail[v]][i];
        FOR(i,0,9){
            if(ch[v][i]){
                fail[ch[v][i]] = ch[fail[v]][i],q.push(ch[v][i]);
            }
            else ch[v][i] = ch[fail[v]][i];
        }
    }
    FOR(i,1,tot) FOR(j,1,n) g[i][j] += g[i][j-1];
    FOR(i,1,tot) FOR(j,0,9) G[ch[i][j]].pb(i);
}

int f[MAXM][MAXN],ans;
bool use[MAXM][MAXN];
// 第 i 位在第 j 个点上

inline void bfs(){
    std::queue<P> q;
    FOR(i,1,tot) if(f[n][i] == ans) q.push(MP(n,i)),use[n][i] = 1;
    while(!q.empty()){
        P v = q.front();q.pop();
        if(!v.fi) continue;
        for(auto x:G[v.se]){
            if(f[v.fi-1][x]+g[v.se][n-v.fi] == f[v.fi][v.se] && !use[v.fi-1][x]){
                q.push(MP(v.fi-1,x));use[v.fi-1][x] = 1;
            }
        }
    }
}

int main(){
    scanf("%s%s%d",L+1,R+1,&n);
    build();
    FOR(i,0,n) FOR(v,1,tot) f[i][v] = -1e9;
    f[0][1] = 0;
    FOR(i,0,n-1){
        FOR(v,1,tot){
            if(f[i][v] < 0) continue;
            FOR(k,0,9){
                if(!ch[v][k]) continue;
                f[i+1][ch[v][k]] = std::max(f[i+1][ch[v][k]],f[i][v]+g[ch[v][k]][n-i-1]);
            }
        }
    }
    ans = -1e9;
    FOR(v,1,tot) ans = std::max(ans,f[n][v]);
    printf("%d\n",ans);
    bfs();
    int now = 1;
    FOR(i,0,n-1){
        FOR(j,0,9){
            if(use[i+1][ch[now][j]] && f[i+1][ch[now][j]] == f[i][now]+g[ch[now][j]][n-i-1]){
                printf("%d",j);
                now = ch[now][j];break;
            }
        }
    }
    puts("");
    return 0;
}

总结

  1. trie 树满叉结构是可以优化掉的。
  2. 一般的这种 dp 还可以考虑加入每个点的贡献,每个结束点都会对 fail 树的子树有贡献。
  3. 我太菜了,活该 pupil

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/970/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏