第十一届蓝桥杯大赛第二场省赛试题 CC++ 研究生组-子串分值和

本文主要是介绍第十一届蓝桥杯大赛第二场省赛试题 CC++ 研究生组-子串分值和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

solution1（通过40%）

依次求子串并统计出现过的字母个数

#include<iostream>
#include<string>
#include<set>
using namespace std;
int main(){string s, subs;cin >> s;int len = s.size(), ans = 0;for(int j = 1; j <= len; j++){for(int i = 0; i < len; i++){if(i + j > len) break;set<char> set1;subs = s.substr(i, j);//cout << subs << endl;for(int i = 0; i < subs.size(); i++){set1.insert(subs[i]);}ans += set1.size();}}printf("%d", ans);return 0;
}

solution1.2(通过50%)

#include<iostream>
#include<string>
using namespace std;
int main(){string s, subs;cin >> s;int len = s.size(), ans = 0;for(int j = 1; j <= len; j++){for(int i = 0; i < len; i++){if(i + j > len) break;int flag[24] = {0};subs = s.substr(i, j);for(int i = 0; i < subs.size(); i++){if(!flag[subs[i] - 'a']){ans++;flag[subs[i] - 'a']++;}}}}printf("%d", ans);return 0;
}

solution2递推

每位上的字母的贡献为从最左首次不出现到，到字符串末尾
例如ababc里第二个位置上的b
左边未出现过b的子串为 : ，a
右边从当前到末尾的子串可能有 , a, ab, abc
则第二个位置的b贡献为24 = (2 - 0)(5 - 2 + 1)//这里加上是该字母单独为子串的情况，即子串b

#include<iostream>
#include<string>
using namespace std;
int main(){string s;cin >> s;int pre[25] = {0};long long len = s.size(), ans = 0;//有两个测试点结果超出intfor(int i = 1; i <= len; i++){ans += (i - pre[s[i - 1] - 'a']) * (len - i + 1);pre[s[i - 1] - 'a'] = i;}printf("%lld", ans);return 0;
}