⭐蓝桥杯高频题单——1.子串分值和（枚举 / 计算贡献 / 前缀数组 / 哈希思想）

⭐子串分值和⭐

在这里插入图片描述

方法一：暴力

在做这道题的时候我想到了以前力扣做的一道Leetcode.78. 子集__DFS算法剖析讲解。初始我的想法是通过深搜找到所有可能的子串，再对他们分别计算f(S)，从而得到所有的f(S)之和。但是经过思考发现，这里找子串的过程和找子集的方式是完全不同的，问题就在于子集可以是不连续的几个数字组成，而子串这里一定是连续的。因此可知，这里就不需要麻烦的深搜来帮助完成了，因为找连续序列情况下的枚举是非常简单的，我们只需要对子串的起点和终点进行枚举即可实现对所有可能的序列进行搜寻，因此这里我们通过两个for循环即可解决问题，搭配哈希思想计算每一个序列的f(S)值即可。

Code:

#include <iostream>
#include <string>
#define int long long
// #include <bits/stdc++.h>
using namespace std;
signed main()
{
  string s;
  cin >> s;
  int sum = 0;
  int len = s.size();
  for(int i=0;i<len;i++){
    for(int j=i;j<len;j++){
      int hash[26] = {0};
      for(int index=i;index<=j;index++){
        hash[s[index] - 'a']++;
      }

      for(int temp=0;temp<26;temp++){
        if(hash[temp] != 0)
          sum++;
      }
    }
  }
  cout << sum;
  return 0;
}

在这里插入图片描述

方法二：前缀和 + 数学法分析

我们不妨先对题目所给定的ababc序列进行简要的分析，可以看到其子序列及每个子序列对应的f(S)一共为：
在这里插入图片描述

⭐通过观察，我们可以发现，当相同字母出现在一个序列中时，其只会贡献一个价值，因此对于如“aba”等序列，其相当于只有一个a能成功贡献，因此第二个a无法贡献。因此我们发现如“aba”序列中，对于第二个a来说，其等价于“_ba”的，所以即“abc”并不是第三个a的有效序列，为它的无效序列。

⭐同时我们可以化此大问题为小问题，即我们如果可以算出总序列中，每一个字母在其所构成的所有序列中所贡献的有效值之和，进行累加即可得到总序列的贡献值f(S)。此时我们发现不用像方法一那样一个一个的枚举起点终点，我们可以一个字母一个字母的去探寻该位置的字母可能生成的所有有效序列，有效序列的个数即为该位置的字母的有效贡献值。

具体流程即：

我们从左方第一个字母a开始，对其来说，其起点只可为自己，而对其来说，其由于为“先手”，所以像"aba"，“abab”，“ababc”含有a的序列均为“先手用a”的有效序列，所以可知其终点可取0，1，2，3，4，即五种，所以1 * 5 = 5种（起点种类个数 X 终点种类个数 = 能组成的序列个数）为该位置字母的有效贡献值(能组成的有效序列个数)。
接着对第二位置b，同上，其起点可为0，1（因为左方0位置与其字母值不同，所以向左方取不会出现无效序列），由于为先手，所以终点可为1，2，3，4，即2 * 4 = 8种。
对第三位置a，对其分析，其起点只可为1，2，不可为0，这是因为0位置为a与其字母值相同，此时它即为“后手”，所以带上0位置的所有序列其都被“先手”拿去作为它的有效序列了，因此对后手来说带上0位置的序列均为无效序列，不计算贡献。而终点可同上延展到最后，因为对于后方来说它算先手，先手具有强大的率先夺取能力！
对第四位置b，对其分析，其起点可为2，3，不可为1，之所以不可为0是因子串具有连续性，一断即断，其余分析同上，终点可延展到最后。
对第五位置c同理。

⭐总结一下上面的流程，即对于字母相同的先手和后手，先手可率先拿走其能拿的所有序列，而后手只能拿不带先手的序列；对于字母不同的先手和后手，其不为竞争关系可相互共存；且某一位置的字母对于其后面的所有字母均为绝对先手；

⭐因此可知算法的核心即将枚举起点和终点改为直接定位起点和终点可能的取值个数，继而使用乘法代替加法，而此算法的计算机算法核心即为维护一个前缀数组pre_same_first_char，pre_same_first_char[s[i] - 'a'] = i 即代表与序列s中第i个位置所对应的字母值相同的相对先手的位置，即找到起点取值的断点（前一个字母值相同的先手位置）即可。

Code：

#include <iostream>
#include <string>
#define int long long
// #include <bits/stdc++.h>
using namespace std;
signed main()
{
  string s;
  cin >> s;
  int sum = 0;
  int pre_same_first_char[26];
  for(int i=0;i<26;i++){
    pre_same_first_char[i] = -1;
  }

  int len = s.size();
  for(int i=0;i<len;i++){
    if(pre_same_first_char[s[i] - 'a'] == -1){
      sum += (i+1) * (len-i);
      pre_same_first_char[s[i] - 'a'] = i;
    }
    else{
      sum += (i - pre_same_first_char[s[i] - 'a']) * (len-i);
      pre_same_first_char[s[i] - 'a'] = i;
    }
  }
  cout << sum;
  return 0;
}