专栏文章

题解：CF1110H Modest Substrings

XXiphi
CF1110H题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minb86xr
此快照首次捕获于
2025/12/01 23:34
3 个月前
此快照最后确认于
2025/12/01 23:34
3 个月前
查看原文
压缩 DFA 的好题。但是还挺难写的。代码参考了某篇题解。
首先我们考虑暴力，把 [l,r][l,r] 的所有数插入 AC 自动机里边去，转化成多模式串匹配问题（模式串为 [l,r][l,r] 所有整数的十进制表示）。设 flen,nodef_{len,node} 表示填完前 lenlen 位，目前在 nodenode 节点，合法子串数最多是多少。
然后另设辅助转移数组 gnodeg_{node} 表示根到 nodenode 的路径组成的串 TT 上，有多少个后缀（可以包含本身）为模式串。采用后缀的原因是，我们要记录新加的那个字符的贡献。
这个其实就是【模版】AC自动机。等价于 nodenode 在 fail 树上的所有祖先中，是模式串结尾的节点个数。这个也很好理解，直接用 fail 的定义就行（failnodefail_{node} 指向的节点 xx 代表一个最长的模式串的前缀，使其是 nodenode 所代表的串的后缀）。求这个东西直接递推就行。
考虑优化。朴素 DP 会在 [l,r][l,r] 中插入所有数字，状态量极大。观察到很多子树在本质上是「满 10 叉树」，可以被整体压缩。
我们类比数位 DP 的思想：当构造数时，只要前面的部分已经“脱离上界限制”，那么后续各位都可以自由取值。这类情况可以用一对参数 (d,m)(d,m) 来描述：
  • dd：表示固定的前缀；
  • mm：表示后续有 mm 位可以自由填。
这样一来，我们就可以只在压缩后的 DFA（相当于“数位状态自动机”）上进行转移，而不用显式展开所有数字。
我们考虑在压缩之后，通过计算“一定可以的贡献”来拼出答案。注意这里 ff 的转移不变。
我们先说怎么做，然后说为什么。
在压缩后的自动机上，我们需要考虑「当前节点后续还能接 mm 个自由位」时的最大匹配贡献。
对于每个节点 nodenode，若其后能接续 mm 个自由位，则「一定会产生贡献」的部分，就是所有满足条件的 (s,l)(s,l) 组合：
  • ss 是某个模式串的结尾（或者是某个参数 (d,l′)(d,l') 的结尾），并且是当前节点代表串的后缀；
  • ll 是自由位个数，且 l≤ml \le m。
由于无论后面具体走的 step≤mstep \le m 步怎么填，这些模式串都会出现，因此我们可以一次性累加这些确定的贡献：
那这个为啥是对的呢？我们可以将所有自由位上可能出现的情况分为两类讨论：
  • 形如 s+[0,9]ls+[0,9]^l 的串（其中 ss 是某个模式串的结尾并且是当前节点所代表串的某个后缀）。这类情形里，前缀 ss 已经构成一个匹配（以当前位置为结尾的匹配已经成立），因此不论后续自由位如何填充，匹配的这部分贡献都是必然发生的。我们将这类“必然发生的贡献”在预处理阶段计入相应的数组（记为 g[node][*] 的确定项），并在 DP 的转移时直接加上。
  • 形如 [0,9]l[0,9]^l 的串（若干完全由自由位组成的段）。这类串的前缀在当前节点并未与任何模式串匹配，上述的“必然发生”情形并不适用；它们是否产生匹配、产生多少匹配，取决于自由位的具体取值。这部分贡献不能事先以“必然项”完全归约到单个常数，而是需要通过在压缩 DFA 上的后续转移（即 DP 中按字符展开或通过 g[node][len] 的“可选/扩展”语义）来累积统计。换言之，预处理可把其中某些较为确定的累积项（例如长度小于等于某值时必然触发的模式）合并，但大部分依赖填法的贡献是在 DP 的转移过程中被计算（或通过 g[node][len] 的正确定义间接体现）。
我们可以可考虑用 gnode,leng_{node,len} 表示这个贡献，转移类似原来辅助数组的转移，不过是加了一维。
但如何算初始时有哪些形如 (d,m)(d,m) 的对也是一个问题。这个直接用 (d,m)(d,m) 的定义，枚举长度（等于 ∣l∣|l|，在 [∣l∣+1,∣r∣−1][|l|+1,|r|-1]，等于 ∣r∣|r|），和在哪一位分离，分讨即可。具体地，对当前走到的节点 xx，我们把 xx 的可以创造分离的儿子创建形如 (d,m)(d,m) 的对，在 [∣l∣+1,∣r∣−1][|l|+1,|r|-1] 就直接从根创建即可。注意分讨 ∣l∣=∣r∣|l|=|r| 的情况。
转移时，我们尝试所有数字字符 c∈[0,9]c \in [0,9]，并利用自动机转移函数 sonnode,cson_{node,c} 与自由位贡献 gnext,tailg_{next,tail} 更新状态：
fi,next=max⁡(fi,next,fi−1,node+gnext,tail)f_{i,next} = \max(f_{i,next}, f_{i-1,node} + g_{next,tail})
其中 tail=min⁡(n−i,LIM)tail = \min(n-i, LIM)，即剩余自由位上限，nextnext 为自动机接收 cc 后会跳到哪里。
最终答案为所有 fn,∗f_{n,*} 中的最大值。 为了得到字典序最小的最优解，直接从 fn,∗f_{n,*} 的最优解开始倒退，看他们能从哪里来。无需显式减出 dag，从 f0,0f_{0,0} 开始，选能到最优解且字典序最小的解即可。
CPP
#include<bits/stdc++.h>
#define _for(i,x,y) for(int i=x;i<=y;++i)
#define _forp(i,x,y,z) for(int i=x;i<=y;i+=z)
#define _rep(i,x,y) for(int i=x;i<y;++i)
using namespace std;
const int N=2005,Node=17005,M=805,V=9;		
string L,R;	
int lenl,lenr,n;
int f[N][Node];
int g[Node][N];
int son[Node][V+5];
int fail[Node];
int node;
bool vis[N][Node];
int ans=0;
int LIM;

int T(char c){
	return (int)(c-'0');
}

void CLEAR(int rt,int num){
	son[rt][num]=0;
}

void upd_son(int root,int l,int r,int len){
	if(l>r) return ;
	if(len<0) return;
	_for(i,l,r){ 
		if(!son[root][i]) son[root][i]=++node;
		g[son[root][i]][len]++;
	}
}

void first_build_G(){
	int pl=0,pr=0;
	if(lenl==lenr){
		_rep(i,0,lenl){
			if(pl==pr){
				//前缀相等
				upd_son(pl,T(L[i])+1,T(R[i])-1,lenl-i-1);
				
				if(!son[pl][T(L[i])]) son[pl][T(L[i])]=++node;
				if(!son[pr][T(R[i])]) son[pr][T(R[i])]=++node;
				pl=son[pl][T(L[i])];
				pr=son[pr][T(R[i])];
			}else{
				upd_son(pl,T(L[i])+1,9,lenl-i-1);
				upd_son(pr,0,T(R[i])-1,lenl-i-1);
				
				if(!son[pl][T(L[i])]) son[pl][T(L[i])]=++node;
				if(!son[pr][T(R[i])]) son[pr][T(R[i])]=++node;
				pl=son[pl][T(L[i])];
				pr=son[pr][T(R[i])];
			}	
		}
		if(L!=R){
			g[pl][0]++;
			g[pr][0]++;
			// cout<<'!'; 
		}else g[pl][0]++;
		CLEAR(0,0);
	}else{
		//在 (|L|,|R|)
		_for(len,lenl+1,lenr-1){
			upd_son(0,1,9,len-1);
		}
		//|L|
		_rep(i,0,lenl){
			upd_son(pl,T(L[i])+1,9,lenl-i-1);
			
			if(!son[pl][T(L[i])]) son[pl][T(L[i])]=++node;
			pl=son[pl][T(L[i])];
		}
		//|R|
		_rep(i,0,lenr){
			upd_son(pr,0,T(R[i])-1,lenr-i-1);
			
			if(!son[pr][T(R[i])]) son[pr][T(R[i])]=++node;
			pr=son[pr][T(R[i])];
		}
		g[pl][0]++;
		g[pr][0]++;
		CLEAR(0,0);
	}
	
	
	queue<int> q;
	_for(i,1,V) if(son[0][i]) q.push(son[0][i]),fail[son[0][i]]=0;
	
	while(!q.empty()){
		int top=q.front();
		q.pop();
		_for(i,0,V){
			if(son[top][i]){
				q.push(son[top][i]);
				fail[son[top][i]] = son[fail[top]][i];
				_for(j,0,LIM) g[son[top][i]][j]+=g[fail[son[top][i]]][j];
			}else{
				son[top][i]=son[fail[top]][i];
			}
		}
	}
}

void build_final_f(){
	// _for(i,0,node){
		// _for(j,1,n){
			// cout<<g[i][j]<<' ';
		// }
		// cout<<'\n';
	// }
	_for(i,0,node) _for(j,1,LIM)
		g[i][j]+=g[i][j-1];
		
	
	_for(i,0,n) _for(j,0,node) f[i][j]=-0x3f3f3f3f;
	
	f[0][0]=0;
	_for(i,1,n){
		_for(j,0,node){
			if(f[i-1][j]>=0){
				_for(c,0,9){
					int nxt=son[j][c];
					// cout<<i<<':'<<nxt<<'\n';
					// cout<<g[nxt][n-i]<<'\n';
					int tail=min(n-i,LIM);	
					f[i][nxt]=max(f[i-1][j]+g[nxt][tail],f[i][nxt]);
					ans=max(ans,f[i][nxt]);
				}
			}	
		}
	}
	cout<<ans<<'\n';
}

 
void solve(){
    memset(son,0,sizeof(son));
    memset(fail,0,sizeof(fail));
    memset(g,0,sizeof(g));
    node=0;ans=0;
    
	cin>>L>>R>>n;
	lenl=L.size();
	lenr=R.size();
	
	int maxTail = (lenl==lenr ? lenl-1 : lenr-1);
	LIM = min(n, maxTail);
	
	first_build_G();//不算前缀和，只算单点
	build_final_f();
	
	_for(i,n,n){
		_for(j,0,node){
			if(f[i][j]==ans){
				vis[i][j]=1; 
			}
		}
	}
	for(int i=n-1;i>=0;--i){
		_for(j,0,node){
			if(f[i][j]>=0){
				_for(c,0,9){
					int nxt=son[j][c];
					int tail=min(n-i-1,LIM);
					if(f[i][j]+g[nxt][tail]==f[i+1][nxt]&&vis[i+1][nxt]){
						vis[i][j]=1; 
					}
				}
			}
		}
	}
	int nw=0;
	_for(i,0,n-1){
		_for(c,0,9){
			int nxt=son[nw][c];
			int tail=min(n-i-1,LIM);
			if(f[i][nw]+g[nxt][tail]==f[i+1][nxt]&&vis[i+1][nxt]){
				nw=nxt;
				cout<<(char)('0'+c);
				break;
			}
		}
	}
}
signed main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
	int T=1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...