Radical

用户名：dotcpp0602299

访问量：969

签　名：

等　　级
排　　名	3171
经　　验	2010
参赛次数	0
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2024年第十五届C/C++大学A组省赛真题-训练士兵
浏览：57

蓝桥杯2024年第十五届省赛真题-团建
浏览：121

蓝桥杯2024年第十五届省赛真题-成绩统计
浏览：104

你可能喜欢

A+B for Input-Output Practice (VI) （C语言代码）

蓝桥杯2024年第十五届省赛真题-遗迹

　　作者: Radical　　　　发表时间：2024-11-14 02:05:06 浏览：47　|　评论：0　

原题链接：蓝桥杯2024年第十五届省赛真题-遗迹

## 知识点
动态规划。
## 题面
小蓝找到了一个外星文明留下来的遗迹，遗迹大门的屏幕上有一个长度为m 的字符串 t 和一个输入框，下面还有一个键盘，键盘为一个长度为 n 的字符串 s ，由一个可以横向移动的指针来敲击键盘，指针可以向左移或向右移，不能移出键盘。
小蓝需要在键盘字符串 s 上先指定指针初始位置然后不断移动指针的位置，过程中通过敲击指针所在的字符来进行输入。然而，指针最多只能移动 L 的距离，小蓝想输入一个尽可能长的一个 t 的前缀，请问他最多能输入多少位。
###### 输入格式
输入的第一行包含三个正整数 n, m, L ，相邻整数之间使用一个空格分隔。
第二行包含一个长度为 n 的字符串 s 。
第三行包含一个长度为 m 的字符串 t 。
###### 输出格式
输出一行包含一个整数表示答案。
###### 样例输入
3 6 5
abc
acbbac
###### 样例输出
5
## 思路
首先考虑保存键盘字符串s当中的所有对应字母的位置，这样我们就可以知道某个字母在键盘字符串s里面的什么地方出现过了。这可以利用26个对应的数组`vector<int>pos[26]`解决。遍历键盘字符串s，检测到一个字母s[i]就将其角标i加入对应数组`pos[s[i]-'a']`中去。由此，我们将字符'a'-'z'映射到数组角标0-25，获得了一个以字母为索引的角标查找表。
在该样例中，我们获得的角标查找表pos内容是：

`pos[0]: 0 //（意为字符'a'在键盘字符串s内对应的角标有0，也意味着s[0]=='a'。注意键盘字符串s当中可能出现重复字母）`
`pos[1]: 1`
`pos[2]: 2`
`pos[3]: //空`
`...`
`pos[25]: //空`

之后，遍历字符串t的每一个字符，但是从下标1开始（看到后面就会知道为什么不从0开始）。找到当前字符t[i]、上一个字符t[i-1]（知道了吧？如果从0开始就会出错。当然你也可以分别改成t[i+1]和t[i]，这样就能从0开始，但需修改循环条件为i<=m）。将它们改写成我们上一段提到的映射的形式，也就是把它们从'a'-'z'改写成0-25。字符t[i]和t[i-1]对应的数字映射分别是current和past,在第一次循环中它们的值如下：
`t="acbbac"`
`i=1`
`t[i]='c'`
`t[i-1]='a'`
`current=2`
`past=0`
如果前后两字符不同，就用x和y两个int类型元素遍历pos[current]和pos[past]。这样做是为了寻找键盘字符串s上从前一个字符s[x]（也就是t[i]）到当前字符s[y]（也就是t[i-1]）的移动之后，总距离（之前移动过的距离加现在移动的距离abs(x-y)）保持最短的一种可能。
我们声明一个数组vector<int>shortestWay(26, 0)来帮助我们完成这件事。这个vector容器里面包含26个被初始化为0的int元素。它在接下来的程序中意味着在键盘字符串s上，从前一个字符s[x]（也就是t[i]）到'a'-'z'任意一个字符的距离加上之前曾经移动过的距离的最小值。
在第一次循环中，曾经移动过的距离显然为0。
先睡觉了不写了，代码你们自己看。

## 代码

```cpp
#include <bits/stdc++.h>
#define MAX 0x3f3f3f3f
using namespace std;
int n, m, L, res;
string s, t;
vector<int> pos[26];
vector<int> shortestWay(26, 0);
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> L;
	cin >> s >> t;
	for (int i = 0; i < n; ++i)
	{
		pos[int(s[i] - 'a')].push_back(i);
	}
	for (int i = 1; i < m; ++i)
	{
		int current = int(t[i] - 'a');
		int past = int(t[i - 1] - 'a');
		res = MAX;
		if (current != past)
		{
			bool find = false;
			for (auto x : pos[current])
			{
				for (auto y : pos[past])
				{
					res = min(res, shortestWay[y] + abs(x - y));
				}
				shortestWay[x] = res;
				if (res <= L)
				{
					find = true;
				}
			}
			if (!find)
			{
				cout << i;
				return 0;
			}
		}
	}
	cout << m;
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Radical

TA的其他文章

你可能喜欢

C二级辅导-分段函数（C++代码）

A+B for Input-Output Practice (VI) （C语言代码）

交换Easy （Java代码）

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C++代码）

蓝桥杯2024年第十五届省赛真题-遗迹

评论区

精彩推荐

【计算两点间的距离】（C语言代码）

Minesweeper （C语言代码）

【蟠桃记】（C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

母牛的故事（C语言代码）

C语言训练-求函数值（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

Radical

TA的其他文章

你可能喜欢

C二级辅导-分段函数 （C++代码）

A+B for Input-Output Practice (VI) （C语言代码）

交换Easy （Java代码）

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C++代码）

蓝桥杯2024年第十五届省赛真题-遗迹

评论区

精彩推荐

【计算两点间的距离】 （C语言代码）

Minesweeper （C语言代码）

【蟠桃记】 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

母牛的故事 （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C二级辅导-分段函数（C++代码）

　　评论区

【计算两点间的距离】（C语言代码）

【蟠桃记】（C语言代码）

C二级辅导-分段函数（C语言代码）

母牛的故事（C语言代码）

C语言训练-求函数值（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）