蓝桥云客第 5 场 算法季度赛

题目：

2.开赛主题曲【算法赛】 - 蓝桥云课

问题描述

蓝桥杯组委会创作了一首气势磅礴的开赛主题曲，其歌词可用一个仅包含小写字母的字符串 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

运行限制

总通过次数: 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;
}