子串分值和（蓝桥杯C组）

首先我们要弄清楚，所有f [ i . . j ] f[i..j]f[i..j]之和，即对于每个下标的字符包含这个下标的字符的子串之和，还要加一点限制,选择的子串只能有一个这个下标的字符。

(1).当选择一个子串时，如果重复选择了一个字符，那么这个字符的对答案的贡献变为0，否则只有一个这个字符，对答案的贡献为1。

比如f [ " a b " ] = 2 , 但 f [ " a b a " ] = 1 。 因 为 ‘ a ’ 重 复 选 取 了 f["ab"]=2,但f["aba"]=1。因为‘a’重复选取了f["ab"]=2,但f["aba"]=1。因为‘a’重复选取了

再来一个例子如样例s ss=“a b a b c ababcababc”

当i = 0 时 i=0时i=0时，选择包含s [ 0 ] s[0]s[0]的子串一共有5个串：

｛“a”,“ab”,“aba”,“abab”,“ababc”｝

第一个串f = 1 f=1f=1;

第二个串f = 2 f=2f=2;

第三个串f = 1 f=1f=1;

第四个串f = 0 f=0f=0;

第五个串f = 1 f=1f=1;

选择第三个串重复了′ a ′ 'a'′a′字符，导致i = 0 i=0i=0时′ a ′ 'a'′a′的贡献被抵消了，所以s [ 0 ] s[0]s[0]到下标为2之后这个字符对答案贡献就为0了

(2).所有f [ i . . j ] f[i..j]f[i..j]之和，等于对于每个下标的字符包含这个下标的字符的子串之和，还要加一点限制,选择的子串只能有一个这个下标的字符。

例如样例：

i = 0 i=0i=0,时满足(2)的子串{“ a ” , " a b " “a”,"ab"“a”,"ab"}每个子串a的贡献为1 （+ 2）

i = 1 i=1i=1,时满足(2)的子串 {" b " , " b a " , " a b " , " a b a " "b","ba","ab","aba""b","ba","ab","aba"}每个子串b的贡献为1 （+4）

i = 2 i=2i=2,时满足(2)的子串 {" a " , " a b " , " a b c " , " b a " , " b a b " , " b a b c " "a","ab","abc","ba","bab","babc""a","ab","abc","ba","bab","babc"}每个子串a的贡献为1 （+6）

i = 3 i=3i=3,时满足(2)的子串 {" a " , " a b " , " a b c " , " b a " , " b a b " , " b a b c " "a","ab","abc","ba","bab","babc""a","ab","abc","ba","bab","babc"}每个子串b的贡献为1 (+6)

i = 4 i=4i=4,时满足(2)的子串 {" c " , " b c " , " a b c " , " b a b c " , " a b a b c " "c","bc","abc","babc","ababc""c","bc","abc","babc","ababc"}每个子串c的贡献为1 （+5）

合起来等于ans=21

所以我们观察子串选择规律得到(我写的有规律)，对于每个下标的字符，选择这个字符的左边离相同字符的距离*右边离相同字符的距离，即a n s + = ( i − p r e [ i ] ) ∗ ( n e [ i ] − i ) ans+=(i-pre[i])*(ne[i]-i)ans+=(i−pre[i])∗(ne[i]−i)

具体解释看下方代码注释：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
int pre[N];//pre[i]表示左边和s[i]相同字符最近的下标
int ne[N];//ne[i]表示右边和s[i]相同字符最近的下标
string s;//存入字符串
int t[26];//0-25对应‘a’-'z',这个数组起临时保存这个字符上一次出现的下标
int main()
{
  cin >> s;//读入字符串
  int n = s.size();//得到字符串长度
  /*先求右边的最近的相同字符的下标*/
  for (int i = 0; i < 26; i++)//初始右边没有相同字符，所以置为n
  {
    t[i] = n;
  }
  long long  ans = 0;
  for (int i = n - 1; i >= 0; i--)
  {
    int x = s[i] - 'a';//将'a'-'z'映射为0-25
    ne[i] = t[x];//与i位置相同的右边最近的字符的位置
    t[x] = i;//更新上一个此字符为本身
  }
    /*先求左边的最近的相同字符的下标*/
  for (int i = 0; i < 26; i++)//字符串下标从0开始，所以左边相同字符位置初始置为-1
  {
    t[i] = -1;
  }
  for (int i = 0; i < n; i++)
  {
    int x = s[i] - 'a';//将'a'-'z'映射为0-25
    pre[i] = t[x];//与i位置相同的左边最近的字符的位置
    t[x] = i;//更新上一个此字符为本身
  }
  for (int i = 0; i < n; i++)
  {
    ans += 1LL * (i - pre[i]) * (ne[i] - i);//左边离相同字符的距离*右边离相同字符的距离
  }
  cout << ans << endl;
}

还有一题差不多的建议做做，只有f ff的定义一点不同

子串分值和B组

点个赞呗~