蓝桥杯 试题H:子串分值
题目内容如下:
首先,理解题意——求解字符串所有子串Si的f(Si)之和,其中f(Si)实际就是统计字符串Si中只出现一次的字母的数目。
再根据样例说明,很容易想到,两层循环去遍历字符串的所有子串(子串按以不同字符开头,依次递增到最后一个字符),对于每一个子串,遍历的同时记录其f(Si)。
前面已经说到,f(Si)实际就是统计字符串Si中只出现一次的字母的个数,那么利用一个数组cnt[26]来统计字符串中每个字母出现的次数,用ff来记录Si中只出现一次的字母的个数。前面已经说到,每一层外层循环对应的所有的子串,规律是首字母相同,然后长度依次递增,那么cnt数组和ff值的记录,可以在前一次的基础上更改,不必对于每一个子串再单独写一个循环,去统计求ff。代码如下:
#include<bits/stdc++.h>
using namespace std;
string s;
int Function() {
int ff; //记录每一个子串的分值
int sum=0; //记录总的分值
int n = s.size();
int i, j;
//int cnt[26] = { 0 };//统计a-z出现的次数
//两次循环遍历所有的子串
for (i = 0; i < n; i++) {
//以不同字符开始递增子串,每轮循环需要将统计结果清零
//memset(cnt, 0, sizeof(cnt));
int cnt[26] = { 0 };//统计a-z出现的次数
ff = 0;
for (j = i; j < n; j++) {
//如果第一次出现 ff+1
if (cnt[s[j] - 'a'] == 0)
//记录每个子串的分值
ff++;
//第二次出现 需要将此字母第一次出现的分值减去 ff-1
else if(cnt[s[j]-'a']==1)
ff--;
//第三次及以上出现 对ff不再有影响
cnt[s[j] - 'a']++;
sum += ff;
}
}
return sum;
}
int main() {
cin >> s;
cout << Function() << endl;
return 0;
}
暴力求解只能通过60%的示例