蓝桥杯真题——前缀总分、遗迹
蓝桥杯2024年第十五届省赛真题-前缀总分
题目描述
给定 n 个由小写英文字母组成的字符串 s1, s2, · · · , sn ，定义前缀总分为V =∑i<j P(si, sj) ，其中 P(si, sj) 表示 si, sj 的最长公共前缀的长度。
小蓝可以选择其中一个字符串，并修改其中的一个字符。请问修改后前缀总分最大为多少？
输入格式
输入的第一行包含一个正整数 n 。接下来 n 行，每行包含一个字符串 si 。
输出格式
输出一行包含一个整数表示答案。
样例输入
3 aab bbb abb
样例输出
5
提示
【样例说明】
将第二个字符串改为 abb ，得分为 P(aab, abb)+P(aab, abb)+P(abb, abb) =1 + 1 + 3 = 5 。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n ≤ 20 ；
对于所有评测用例，1 ≤ n ≤ 200 ，1 ≤ |si| ≤ 200 ，其中 |si| 表示 si 的长度。
代码1：会超时
#include<bits/stdc++.h>
//#define int long long
using namespace std;const int N=200+10;int n;
string s[N];
int m[N][N];//存储字符串之间的相似度
int score;//存放前缀总分 //计算任意两个字符串之间的公共前缀长度
int cal(string s1,string s2)
{int j=0,tmp=0;while(s1[j]!='\0'&&s2[j]!='\0'){if(s1[j]!=s2[j])break;tmp++;j++;}return tmp;
}//计算所有字符串之间的相似度
int cal_all()
{int sum=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){m[i][j]=cal(s[i],s[j]);sum+=m[i][j];m[i][0]+=sum;//具有累加效果，存放第i个字符串与后面所有的字符串的前缀总分 }return sum;
}//只对改变的字符与所有其他字符进行计算
//即只是一部分的计算，所以要加上前面所计算的累加结果
//并且前面所计算的累加结果包含了当前所改变的字符，要注意减去
int cal_part(int i)
{int sum=0;for(int j=1;j<=n;j++){if(i==j) continue;sum+=cal(s[i],s[j]);sum+=m[j][0];if(j<i) sum-=m[j][i];}return sum;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>s[i];score=cal_all();//改变字符，遍历所有的可能for(int i=1;i<=n;i++){for(auto &c:s[i]){//记录，用于恢复现场 for(char ch='a';ch<='z';ch++){char tmp=c;c=ch;//替换字符 int sum=cal_part(i);score=max(sum,score); c=tmp;} //恢复现场，防止对后面产生影响 }} cout<<score<<endl;return 0;
}蓝桥杯2024年第十五届省赛真题-遗迹
题目描述
小蓝找到了一个外星文明留下来的遗迹，遗迹大门的屏幕上有一个长度为m 的字符串 t 和一个输入框，下面还有一个键盘，键盘为一个长度为 n 的字符串 s ，由一个可以横向移动的指针来敲击键盘，指针可以向左移或向右移，不能移出键盘。
小蓝需要在键盘字符串 s 上先指定指针初始位置然后不断移动指针的位置，过程中通过敲击指针所在的字符来进行输入。然而，指针最多只能移动 L 的距离，小蓝想输入一个尽可能长的一个 t 的前缀，请问他最多能输入多少位。
输入格式
输入的第一行包含三个正整数 n, m, L ，相邻整数之间使用一个空格分隔。
第二行包含一个长度为 n 的字符串 s 。
第三行包含一个长度为 m 的字符串 t 。
输出格式
输出一行包含一个整数表示答案。
样例输入
3 6 5 abc acbbac
样例输出
5
提示
【样例说明】
初始选择指针位于键盘 abc 上的 a ，输入 acbbac 这 6 个字符分别需要指针移动 0, 2, 1, 0, 1, 2 的距离，而最大移动距离为 5 ，所以最多输入 5 个字符，移动 0 + 2 + 1 + 0 + 1 = 4 的距离。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ m ≤ 20；
对于所有评测用例，1 ≤ n ≤ 10^3 ，1 ≤ m ≤ 10^5 ，1 ≤ L ≤ 10^9 且 s, t 中只包含小写字母，且 s 中一定包含所有 t 中出现过的字母，数据保证随机。
思路：
- 首先考虑保存键盘字符串s当中所有对应字母的位置，这样我们就可以知道某个字母在键盘字符串s里面的什么地方出现过了。
这里要注意，s中字母可能会重复，所以不能直接用数组，而是使用vector容器的数组，以便在同一字母下存储不同的位置，并且将字符 'a' ~ 'z' 映射到数组角标0~25，获得一个以字母为索引的角标查找表，存储形式如下图：
而且由题意知在键盘中的初始位置不定，不用纠结vector[]容器中的位置关系，直接从目标字符串t逐一扫描遍历即可
2. 遍历字符串t的每一个字符，但是for循环中要从1开始，小于m结束（因为会使用i-1实际上是从0开始），找到当前字符串t[i]、上一个字符串t[i-1]。将它们改写成上面提到的映射形式，字符t[i]、t[i-1]对应的数字映射分别是current、past。
这里由于要知道前后移动的长度（结束条件），所以不能只用一个指针变量来遍历t，要使用两个，即 current 和past，并且要设一个条件变量res来存放最小结果
3 . 如果current != past 即前后两个字符不相同，这时需要在键盘上移动。这里使用x、y两个int 类型元素遍历pos[current]、pos[past]。这样做是为了寻找键盘字符串s上从前一个字符s[y] 到当前字符s[x] 的移动后，总距离（之前移动的距离+现在移动距离abs(x-y) ），保持最短的一种可能。
这里外循环是current ，内循环是past，因为就是要从前一个的不同情况讨论起的
之前移动距离使用vector<int> shW(26，0）来存放，它在程序中意味着在键盘字符串s上，从一个字符s[x]到 'a' ~'z' 任意一个字符的距离加上之前曾经移动过的距离的最小值。 注：这里在程序中为什么是在for(auto y:pos[past]) 后shW[x]=res ，是因为在第一次循环中，past（y）就是从第一个开始的它的shW就默认从0开始，而curren（x）t是从第二个开始的，要使用x来进行累加，而不是使用y。并且服务于后面不同的i位置
for(auto y:pos[past])循环的作用是不断遍历所有y的可能值对res更新，使得其记录最小路径。
4 . 最后还要设置一个标记变量，在每一次遍历到的位置将其赋值为false，对每一次y循环结束后即进行判断是否小于l，如果小于或等于即继续遍历下一个位置（i++），如果大于就输出当前位置，即能输出的最多位
注意！！由范围可知m<l，所以有可能输出所有的字符，要在所有循环结束后加一个cout<<m;
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;const int MAX=1e10;int n,m,l;
int res;
string s,t;
vector<int> pos[26];
vector<int> shW(26,0);signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>l;cin>>s>>t;for(int i=0;i<n;i++)pos[(s[i]-'a')].push_back(i);for(int i=1;i<m;i++){int current=t[i]-'a';int past=t[i-1]-'a';res=MAX;if(current!=past){bool flag=false;for(auto x:pos[current]){for(auto y:pos[past])res=min(res,shW[y]+abs(x-y));shW[x]=res;if(res<=l)flag=true;}if(!flag){cout<<i<<endl;return 0;}}}cout<<m<<endl;return 0;
}