蓝桥云客第 5 场 算法季度赛
题目：
问题描述
蓝桥杯组委会创作了一首气势磅礴的开赛主题曲，其歌词可用一个仅包含小写字母的字符串 S 表示。S 中的每个字符对应一个音高，音高由字母表顺序决定：a=1,b=2,...,z=26。字母越靠后，音高越高。
为了增强歌曲感染力，组委会希望从中选取一段子串作为副歌。该子串需满足以下条件：
- 所有字母都必须唯一。
此外，若副歌包含“lanqiobe”的前缀（例如“l”、“la”、“lan”等），则可额外获得创作灵感加成：
- “l”: 10 分
- “la”: 20 分
- “lan”: 30 分
- “lanq”: 40 分
- “lanqi”: 50 分
- “lanqio”: 60 分
- “lanqiob”: 70 分
- “lanqiobe”: 80 分
注意：创作灵感加成只能加一次，且只加最高的那个分数。例如，如果副歌是“la”，只会加 20 分，而不会再加上 10 分。
副歌的感染力 = 所有字母对应的音高之和 + 最高的创作灵感加成。
现在，请你找出最佳副歌子串。若有多个满足条件的子串，则输出字典序最小的一个。
输入格式
第一行包含一个正整数 NN ( 1≤N≤2×105 )，表示字符串 S 的长度。
第二行包含一个仅由小写字母所组成的字符串 S，长度为 N。
输出格式
输出一个字符串，表示最佳副歌子串。如果有多个满足条件的子串，则输出字典序最小的那个。
样例输入
8
lbcaccla
样例输出
cla
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 2s | 256M |
| Python3 | 3s | 256M |
| PyPy3 | 3s | 256M |
| Go | 3s | 256M |
| JavaScript | 3s | 256M |
总通过次数: 136 | 总提交次数: 464 | 通过率: 29.3%
难度: 简单 标签: 模拟, 暴力
思路：
1.首先要找出不重复出现字符的字符，以每一个字符为结尾作为子串。
2.利用桶思维，发现出现重复的字符直接break
3.有八个对应字符串得分，我们可以从最大个的开始比较。因为只增加最大得分。
4.感染力和字符串的更新，字典序的比较是很基础的，用stl比较就不多说了。（注意：只有字符串长度一样时候才能直接比较）
代码如下：
#include <iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
using namespace std;
int n;
int ans = -1;
string s;
string ans_s;
bool mem[30];
int main()
{
cin >> n;
cin >> s;
for(int i = 0 ; i < n ; i++)
{
memset(mem,false,sizeof(mem));
int sum = 0;
string sc;
for(int j = i ; j >= 0 ; j--)
{
int num = s[j] - 'a' + 1;
if(mem[num] == false)
{
mem[num] = true;
sc += s[j];
sum += num;
}
else
break;
}
reverse(sc.begin(),sc.end());//由于子串是从后往前加，与正常的子串相反，所以要转置一下。
if (sc.size() >= 8 && sc.find("lanqiobe")!=string::npos)
sum += 80;
else if (sc.size() >= 7 && sc.find("lanqiob")!=string::npos)
sum += 70;
else if (sc.size()>=6 && sc.find("lanqio")!=string::npos)
sum += 60;
else if (sc.size()>=5 && sc.find("lanqi")!=string::npos)
sum += 50;
else if (sc.size()>=4 && sc.find("lanq")!=string::npos)
sum += 40;
else if (sc.size()>=3 && sc.find("lan")!=string::npos)
sum += 30;
else if (sc.size()>=2 && sc.find("la")!=string::npos)
sum += 20;
// cout << "以" << i << "为结尾 "<<"出现的子串：" << sc << endl;
if(sum > ans)//感染力更大
{
ans = sum;
ans_s = sc;
}
else if(sum == ans)//感染力相等，比较字典序
{
if(sc.size() < ans_s.size())//比较长度
{
ans_s = sc;
}
else if(sc.size() == ans_s.size() && sc < ans_s)
{
ans_s = sc;
}
}
}
cout << ans_s;
// 请在此输入您的代码
return 0;
}
原文地址：https://blog.csdn.net/zqystca/article/details/145098336
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！