CF1312 G. Autocompletion

发表于 | 阅读数

明确题意！给你字符串集合$S$，打字其中一个字符串$s$,如果打到$t$,是就会和$vscode$,出现自动补全，并且按字典序排列，*如果$t$本身也在集合里他也会出现字典序排序，那么选排名$i$,费时$i$妙，任意加一个字符为 $1$秒。

看一看 样例1 $ieh, iqgp, i, iqge, ier.$
比如$iqge=0\rightarrow i \rightarrow iq \rightarrow iqgp =3$，$iqge=0\rightarrow i \rightarrow iqgp =3$

设$dp[i]$为到达$i$最少步数。

$id[i]$ 是这个点的字典序。如果不是集合里的元素，字典序等于他父亲的字典序。

对于一个$i$,他在$x$的排名下是$id[x]+(vis[x]=1)$，这个时候用自动补全就是$d[i]-id[x]-(vis[x]=1)+dp[x]$

只需要在$dfs$一边维护$dp[x]$,一边维护$min(-id[x]-(vis[x]=1)+dp[x])$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int tri[N][26];
int a[N], n, k, v[N], p[N], tcnt;
int dp[N];
void predfs(int x)
{
    if (v[x])
        ++tcnt;
    p[x] = tcnt;
    for (int i = 0; i < 26; i++)
        if (tri[x][i])
            predfs(tri[x][i]);
}
void dfs(int x, int w)
{
    //cout << x << ' ' << w << endl;
    if (v[x])
        dp[x] = min(dp[x], p[x] + w);
    for (int i = 0; i < 26; i++)
        if (tri[x][i])
        {
            int to = tri[x][i];
            dp[to] = dp[x] + 1;

            dfs(to, min(-p[x] + dp[x] + v[x], w));
        }
}
int main()
{

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        char c[10];
        int x;
        scanf("%d %s", &x, c);
        tri[x][c[0] - 'a'] = i;
    }
    scanf("%d", &k);
    for (int i = 1; i <= k; i++)
    {
        scanf("%d", &a[i]);
        v[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++)
        dp[i] = 1e9;
    dp[0] = 0;
    predfs(0);
    tcnt = 0;
    dfs(0, 1e9);
    for (int i = 1; i <= k; i++)
        printf("%d ", dp[a[i]]);
}