Solution CF1860E Fast Travel Text Editor

· · 题解

Solution CF1860E Fast Travel Text Editor

题目思路

对于这种求最小代价的题目，我们可以将其转换到图上来做。（算是一种套路）

如何建图

根据题意描述，设节点 i 为光标在 s_i 和 s_{i+1} 之间，发现光标可以移到相邻位置，可得：

i\leftrightarrow i+1

接下来考虑跳转。发现如果直接连边，最坏会有 n^2 条边（当 s 的字符相同时），无法承受。
此时增加中转点，我们可以连接 i 和其相邻的字符组成的点，此时最坏情况下会有 26^2 种边，可以承受。

放张图（样例）：

题目的每条边边权为 1 ，然而添加中转点后距离变为 2。

我们把图变为有向边，从 i 前往中转点边权为 1，从中转点回到 i 边权为 0。

然后在建完的图上直接对于每一个询问跑 01-bfs 就可以了。

完整代码

// E. Fast Travel Text Editor
#include <bits/stdc++.h>
using namespace std;

const int N = 50005, M = 2005;

vector< pair< int, bool > > edge[N + M];

char s[N];
int n, m;

int getpoint(char a, char b) {
    return 50005 + (a - 'A' + 1) + (b - 'A' + 1) * 30;
}

bool vis[N];
int dis[N];

// 0/1 bfs
void bfs(int s) {
    deque< int > q;

    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f3f3f3f, sizeof(dis));

    q.push_front(s);
    dis[s] = 0;
    vis[s] = true;

    int x, y;
    bool f;

    while (!q.empty()) {
        x = q.front();
        q.pop_front();

        for (int i = 0; i < edge[x].size(); i++) {
            y = edge[x][i].first;
            f = edge[x][i].second;
            if (vis[y]) continue;

            vis[y] = true;
            if (f) {
                dis[y] = dis[x] + 1;
                q.push_back(y);
            }  else {
                dis[y] = dis[x];
                q.push_front(y);
            }
        }
    }
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);

    // build edge
    for (int i = 1; i < n; i++) {
        edge[i].push_back({i + 1, 1});
        edge[i + 1].push_back({i, 1});

        int x = getpoint(s[i], s[i + 1]);
        edge[i].push_back({x, 1});
        edge[x].push_back({i, 0});
    }

    scanf("%d", &m);
    int f, t;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &f, &t);

        bfs(f);

        printf("%d\n", dis[t]);
    }
    return 0;
}