算法

考场上想到了一些, 但不多

容易想到把相关的字符串全部加到字典树中

然后操作只有两种嘛

• 键盘输入
• 按 tab

显然的, 我们可以构造一颗 \(\rm{trie}\) 树, 对于键盘输入, 我们把 \(\rm{trie}\) 树上的点向其子节点连一条权值为 \(1\) 的点

对于按 tab 的情况, 分两种情况讨论

• 到达末尾
  显然, 到达下一个字符串的末尾
• 未到达末尾
  走到子树内编号最小的字符串的位置

先预处理好边, 然后就可以跑 \(\rm{bfs}\) 解决了

代码

主要问题在于下一个字符串的末尾和子树内编号最小的字符串的位置怎么找:

对于到达下一个字符串的末尾, 我们显然可以在每次标记末尾的时候记录一下, 最后一起加边即可

对于子树内编号最小的字符串, 在建立 \(\rm{trie}\) 树时, 我们就可以建好, 具体见代码

#include <bits/stdc++.h>
const int MAXN = 2e5 + 20;
const int MAXLEN = 1e6 + 20;
const int MAXM = 2e6 + 20;

int n;
std::string Aim;

std::string Folder[MAXN];
int EndNum[MAXN]; // 每个字符串的结尾点
int Past[MAXN]; // 路上经过的新点
int Past_Num = 0;

class Graph_Class
{
private:
    /*建立文件之间的边 (tab)*/
    void ADD1()
    {
        for (int i = 2; i <= n; i++)
            addedge(EndNum[i - 1], EndNum[i]);
            addedge(EndNum[n], EndNum[1]);
    }

    std::queue<int> Q;
    int dis[MAXLEN];
    bool inq[MAXLEN];
    void bfs()
    {
        Q.push(0);
        memset(dis, 0x3f, sizeof(dis));
        memset(inq, false, sizeof(inq));
        dis[0] = 0;
        inq[0] = true;
        while (!Q.empty())
        {
            int Now = Q.front();
            Q.pop();
            inq[Now] = false;
            if (Now == EndNum[n + 1]) {
                printf("%d",dis[Now]);
                exit(0);
            }

            for (int i = head[Now]; ~i; i = Edge[i].next) {
                int NowTo = Edge[i].to;
                if(dis[NowTo] > dis[Now] + 1) {
                    dis[NowTo] = std::min(dis[NowTo], dis[Now] + 1);
                    if(!inq[NowTo]) Q.push(NowTo), inq[NowTo] = true;
                }
            }
        }
    }

public:
    struct node
    {
        int to;
        int next;
    } Edge[MAXM << 1];
    int Edge_Cnt = 0;
    int head[MAXLEN];
    void head_init() { for (int i = 0; i <= 1e6 + 1; i++) head[i] = -1; }
    void addedge(int u, int v)
    {
        Edge[++Edge_Cnt].to = v, Edge[Edge_Cnt].next = head[u];
        head[u] = Edge_Cnt;
    }

    /*建图*/
    void solve()
    {
        ADD1();
    }

    /*求最短路*/
    void ShortestPath()
    {
        bfs();
    }
} Graph;

class Trie_Class
{
private:
    /*魔改 Trie 树*/
    struct node
    {
        int Son[26]; // 儿子 ('a' ~ 'z')
        int fa; // 父亲
        bool IsEnd = false; // 结尾 tag
    };

    void Insert(int Num)
    {
        int Now = 0;
        if(Num == 1)
            Past[++Past_Num] = Now;
        for (int i = 1; i < Folder[Num].length(); i++) {
            int ch = Folder[Num][i] - 'a';
            if (Trie[Now].Son[ch] == 0) Trie[Now].Son[ch] = ++Cnt, Trie[Cnt].fa = Now, Past[++Past_Num] = Cnt, Graph.addedge(Now, Cnt);

            Now = Trie[Now].Son[ch];
            if (i == Folder[Num].length() - 1) {
                Trie[Now].IsEnd = true;
                EndNum[Num] = Now;
            }
        }
        if (Num != n + 1)
            for (int i = 1; i <= Past_Num; i++) {
                Graph.addedge(Past[i], EndNum[Num]);
            }
    }

public:
    node Trie[MAXLEN];
    int Cnt = 0;

    /*建立 Trie 树*/
    void BuildTrie() {
        for (int i = 1; i <= n + 1; i++) Past_Num = 0, Insert(i);
    }
} Trie;

int main()
{
    scanf("%d", &n);
    std::cin >> Aim, Aim = " " + Aim;
    for (int i = 1; i <= n; i++) {
        std::cin >> Folder[i];
        Folder[i] = " " + Folder[i];
    }
    Folder[n + 1] = Aim;

    Graph.head_init();
    Trie.BuildTrie();

    Graph.solve();
    Graph.ShortestPath();

    return 0;
}

总结

最短操作不一定是 \(\rm{dp}\) , 也有可能建图跑最短路

利用输入建边是巧妙的, 利用好题中性质