CF1110H Modest Substrings 题解
zhouyixian
·
·
题解
本题统计的是 n 位数中（允许前导零）在 [l,r] 之间的子串计数的最大值及方案。
计数这个子串相当于是计数字典序在 l,r 之间的子串。
一个 naive的 想法是把 [l,r] 间的串全塞到 AC 自动机里，然后 dp ，考虑节点 i 对答案的贡献 g[i] 。这个贡献除了 i 代表的串自身产生的贡献，还应包括 fail[i] 的贡献（因为它同时也出现了）。也就是说，g[i] 应该是节点 i 跳 fail 能跳到的点的贡献总和。（也许是 AC 自动机 dp 常规操作？）
求 g[i] 很简单，就是插入时标记串的贡献，然后在 getfail 的时候每次查到一个后继节点就 g[to]+=g[fail[to]] 就行。
继续这个暴力的思路，考虑设计 dp，状态 dp[rt][len] 表示在节点 rt 上组成的 len 位数方案数。显然可以拿 dp[rt][len]+g[son] 去更新 dp[son][len+1] ，答案就是 \max \{ dp[i][n]\}。
这个TLE自动机+ dp 方法效率低下，我们考虑优化它。
这时 $g[i][len]$ 的的处理方式不变，转移变成了用 $dp[rt][len]+\sum \limits ^{n-len-1} _ {k=0} g[son][k]$ 更新 $dp[son][len+1]$ 。所以需要处理出 $g[son]$ 的前缀和，然后 $dp$ 即可。
现在剩下一个问题：如何按上面要求建出$trie$树。
用类似数位 $dp$ 的思想，需要分以下几种情况：
+ $l,r$ 长度相等：
1.当前节点是 $l,r$ 共同前缀：下一节点为终止点，当且仅当下一点数值 $num \in (l_i,r_i)$ 。
2.当前节点只是 $l$ 前缀：要求下一点数值 $num \in (l_i,9]$ 。
3.当前节点只是 $r$ 前缀：要求下一点数值 $num \in [0,r_i)$ 。
4.当前节点是 $l$ 或 $r$ 终点，对当前点记录贡献，即 $g[rt][0]++$.
+ $l,r$ 长度不等:
情况 $2,3,4$同上。
还需要额外添加一种情况：对于 $len \in (len_l,len_r)$的串，显然都是符合题意的，因此要对每一个 $g[son[0]][len-1]$ 记录贡献。
这样建树就完成了，$getfail$ 和原来几乎没有变化，只需要顺便处理下 $g$ 数组。
$dp$ 直接顺序枚举长度和当前节点，递推即可。每个数位产生至多十个新节点，故总复杂度大概是 $O(|\Sigma|^2N\log R)$，$R$为值域 $10^{800}$，$|\Sigma|=10$.（显然跑不满）
~~完结撒花~~
哦对，还要求字典序最小的方案。
先枚举所有 $dp[rt][n]$ 找到等于答案的节点并标记，再从后向前推。找到所有能到达答案的路径，再按字典序最小的方式遍历输出即可。
有一些小细节，看代码吧。
```cpp
#include<bits/stdc++.h>
#define for_each(i,bg,ed) for(int i=bg;i<ed;++i)
using namespace std;
const int M=2e4+10,N=2e3+10,SIG=10;
int ch[M][SIG],fail[M], //AC自动机部分
g[M][N], //g[u][len]:节点 u 处后接长度为 len 的自由数码的方案数。
dp[M][N], //dp[u][pos]:匹配到 pos 处，在节点 u 上的匹配数。
cnt,n,len_l,len_r,ans;
string sl,sr,str;
inline void Read(){
cin>>sl>>sr>>n;
len_l=sl.size();
len_r=sr.size();
for_each(i,0,len_l)sl[i]-='0';
for_each(i,0,len_r)sr[i]-='0';
}
inline void CreateNode(int rt,int son_id){if(!ch[rt][son_id])ch[rt][son_id]=++cnt;}
//判断并新建节点
inline void RegMsg(int rt,int l,int r,int len){
for_each(nxt,l,r){
CreateNode(rt,nxt);
g[ch[rt][nxt]][len]++;
}
}//对每个儿子记录信息
inline void MoveIter(int &rt,int num){
CreateNode(rt,num);
rt=ch[rt][num];
}//移动根节点。
//处理一个g数组，省略可以自由安排的部分，以减少AC自动机节点数。
void BuildTree(){
int rt_l=0,rt_r=0;
if(len_l==len_r){ //Case A:l,r长度相等
for_each(i,1,len_l+1){
int num_l=sl[i-1],num_r=sr[i-1];
if(rt_l==rt_r){ //case 1:当前节点属于l,r共同前缀
RegMsg(rt_l,num_l+1,num_r,len_l-i);
MoveIter(rt_l,num_l);
MoveIter(rt_r,num_r);
}else{ //case 2:分别处理l,r前缀。
RegMsg(rt_l,num_l+1,10,len_l-i);
RegMsg(rt_r,0,num_r,len_r-i);
MoveIter(rt_l,num_l);
MoveIter(rt_r,num_r);
}
}
g[rt_l][0]++;
if(rt_l!=rt_r)g[rt_r][0]++;
}else{ //Case B:l,r长度不等
for_each(i,1,len_l+1){ //处理 l
int num_l=sl[i-1];
RegMsg(rt_l,num_l+1,10,len_l-i);
MoveIter(rt_l,num_l);
}
for_each(i,1,len_r+1){ //处理 r
int num_r=sr[i-1];
RegMsg(rt_r,0,num_r,len_r-i);
MoveIter(rt_r,num_r);
}
g[rt_l][0]++,g[rt_r][0]++;
for_each(i,len_l+1,len_r) //处理长度介于 len_l 和 len_r 的部分。
for_each(nxt,1,10){
if(!ch[0][nxt])ch[0][nxt]=++cnt;
g[ch[0][nxt]][i-1]++;
}
}
ch[0][0]=0;
}
queue<int> q;
void GetFail(){
for(int i=0;i<SIG;++i)
if(ch[0][i])
q.push(ch[0][i]);
while(!q.empty()){
int it=q.front();
q.pop();
for(int i=0;i<SIG;++i){
int &to=ch[it][i];
if(to){
q.push(to),fail[to]=ch[fail[it]][i];
for_each(i,0,n+1)g[to][i]+=g[fail[to]][i];//继承fail树父亲的g值。
}else to=ch[fail[it]][i];
}
}
for_each(rt,0,cnt+1)
for_each(i,0,n+1)
g[rt][i]+=g[rt][i-1];
}
void GetAns(){
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for_each(i,0,n+1)
for_each(rt,0,cnt+1)
if(dp[rt][i]>=0){
dp[rt][i]+=g[rt][n-i];
for_each(nxt,0,10)
dp[ch[rt][nxt]][i+1]=max(dp[rt][i],dp[ch[rt][nxt]][i+1]);
}
for_each(rt,0,cnt+1)ans=max(ans,dp[rt][n]);
cout<<ans<<endl;
}
bool reg[M][N];//记录方案
void GetSolution(){
for_each(rt,0,cnt+1)
if(dp[rt][n]==ans)
reg[rt][n]=1;
for(int len=n-1;~len;len--)
for_each(rt,0,cnt+1)
if(dp[rt][len]>=0)
for_each(nxt,0,10)
if(reg[ch[rt][nxt]][len+1]&&dp[ch[rt][nxt]][len+1]==dp[rt][len]+g[ch[rt][nxt]][n-len-1]){
reg[rt][len]=1;
break;
}
int rt=0;
for_each(len,0,n)
for_each(nxt,0,10)
if(reg[ch[rt][nxt]][len+1]&&dp[ch[rt][nxt]][len+1]==dp[rt][len]+g[ch[rt][nxt]][n-len-1]){
putchar('0'+nxt);
rt=ch[rt][nxt];
break;
}
}
int main(){
Read();
BuildTree();
GetFail();
GetAns();
GetSolution();
}
```