CF1312G Autocompletion-题解

skyx · 2026-02-27 19:20:35 · 题解

CF1312G Autocompletion-题解

简要题意

给出一堆串，每次可以手打一个字符，或者按字典序自动补全跳到某个目标串（代价为排名），求打出每个目标串的最小时间。

题目分析

先考虑这个奇形怪状的输入，描绘了一种父子关系，再发现前缀有非常突出的作用，这启示我们可能要用到树相关的内容，显然是字典树。

次数的转移显然是依赖于某个字符串的祖先节点的，对于手打一个字符，直接在父节点加 1 就可以，考虑自动补全的转移。

注意到自动补全是只涵盖目标串的，于是从某个前缀转移来，代价包括目标串在这个前缀列表的字典序名次，这个显然是需要做到尽可能快的查询。

我们在全局看所有目标串的字典序，发现某个前缀对应的目标串一定是连续的递增的一段，但是前缀不一定是目标串，如果前缀有字典序，排名就容易求了。

那就考虑维护子树内的最小字典序 dfn：

如果 x 是目标单词节点，\mathrm{dfn}_x 就是它自己的编号。
如果 x 不是目标单词节点，\mathrm{dfn}_x 会等于以它为根的子树中，所有目标单词节点里最小的编号。

这利用字典树的性质很容易做到。排名利用前缀的 dfn，也很容易求。

整理两种转移，设 dp_x 为最短时间，有：

dp_x = \min\Big( dp_{\mathrm{fa}(x)}+1,\ \min_{p\text{ 是 }x\text{ 的祖先}} \big( dp_p+\mathrm{dfn}_x-\mathrm{dfn}_p+1 \big)\Big)

发现这个维护 p 需要优化，关于 p 要的是不变的最值，可以提出来优化。

考虑定义：

g_x=\min_{p}\big(dp_p-\mathrm{dfn}_p\big)

把 dp 转移式的 1 提出来，另做一遍 dfs 就很容易计算了！

代码实现

考虑几个实现细节：

值得注意的是，根据定义，g_0 的初值是 -1。

自动补全的范围只包括目标字符串。


#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int ch[N][26]; int a[N]; bool is[N]; int cnt; int dfn[N],dp[N],g[N]; void dfs(int x) { if(is[x]) dfn[x]=++cnt; for(int i=0;i<26;i++) { if(ch[x][i]) { dfs(ch[x][i]); dfn[x]=min(dfn[x],dfn[ch[x][i]]); } }

} void dfs1(int x) { for(int i=0;i<26;i++) { int son=ch[x][i]; if(son!=0) { if(is[son]) { dp[son]=min(dp[x]+1,dfn[son]+g[x]+1); } else dp[son]=dp[x]+1; g[son]=min(g[x],dp[son]-dfn[son]); dfs1(son); }

} int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

memset(dfn,0x3f,sizeof(dfn));
memset(dp,0x3f,sizeof(dp));
memset(g,0x3f,sizeof(g));
int n,k;
cin>>n; 

for(int i=1;i<=n;i++)
{
    int x;
    char s;
    cin>>x>>s;
    ch[x][s-'a']=i;
}
cin>>k;
for(int i=1;i<=k;i++)
{
    cin>>a[i];
    is[a[i]]=1;
}

dfs(0);
g[0]=-1;dp[0]=0;
dfs1(0);
for(int i=1;i<=k;i++)
{
    cout<<dp[a[i]]<<" ";
}
cout<<endl;
return 0;

}