第十五届蓝桥杯省赛第二场C/C++B组E题【遗迹】题解

解题思路

错解

贪心：每次都移动至当前最近的对应方块上。

反例：

$s=$ abxac

$t=$ abac

贪心结果（下标） $0\to 1\to 0\to 4$，答案为 $5$。

正确结果（下标） $0\to 1\to 3\to 4$，答案为 $4$。

答案与逾期不符合，故贪心解法不正确。

正解

首先，我们注意到数据范围的最后一句话，数据保证随机，那么这样每个字符的数量约为 $\frac{n}{26}$。

当我们要在键盘串查找一种字符的位置时，$O(n)$ 遍历效率较低，可以考虑先将字符串进行预处理，将字符 a 的下标全部存入 $g[0]$，字符 b 的下标存入 $g[1]$，$\dots$

设 $f[x]$ 表示当前情况下，以 $s[x]$ 作为结尾字符，键盘指针指向 $x$，构成字符串的最小代价。例如，设键盘串为 $abcdef$，$f[3]$ 表示构成 $abcd$，且最终键盘指针指向 $3$ 的最小代价。

计算出字符串 abcc 所需要的步数时：

• 我们可以先计算构成 a 的所有最短步数，键盘串中一定存在 a，设其中一个为 a 的下标为 $x$，那么 $f[x]=0$，由于 $f$ 数组定义在全局，故此处在代码中不体现。
• 接下来计算构成 ab 的所有最短步数，由于我们已经计算出了构成 a 的所有最短步数，那么我们可以暴力枚举所有 a 的位置，与所有 b 的位置，假设其中一个 a 的位置为 $y$，其中一个 b 的位置为 $x$，那么 $f[x]=min(f[x],f[y]+abs(x-y))$。
• 计算所有构成 abc 的做法如上。
• 计算所有构成 abcc 的最短步数，由于 $t[3]=t[2]$，故本轮可跳过。

时间复杂度 $O(m(\frac{n}{26}{)}^2)$。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

int n, m, t;
string s, str;
vector<int> g[26];
int f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> t >> s >> str;
    
    for (int i = 0; i < n; ++ i )
        g[s[i] - 'a'].push_back(i);
    
    for (int i = 1; i < m; ++ i )
    {
        int u = str[i] - 'a', last = str[i - 1] - 'a';
        if (u != last)
        {
            int res = INF;
            bool find = false;
            for (auto x: g[u])
            {
                for (auto y: g[last])
                    res = min(res, f[y] + abs(x - y));
                f[x] = res;
                if (f[x] <= t)
                    find = true;
            }
            
            if (!find)
            {
                cout << i << endl;
                return 0;
            }
        }
    }
    
    cout << m << endl;
    
    return 0;
}