题目 2572: 蓝桥杯2020年第十一届省赛真题-子串分值

时间限制: 1s 内存限制: 128MB 提交: 1387 解决: 396

题目描述

对于一个字符串S，我们定义S 的分值 f(S) 为S中恰好出现一次的字符个数。例如f (”aba”) = 1，f (”abc”) = 3, f (”aaa”) = 0。

现在给定一个字符串S[0…n-1]（长度为n），请你计算对于所有S的非空子串S[i…j](0 ≤ i ≤ j < n)， f (S[i… j]) 的和是多少。

输入格式

输入一行包含一个由小写字母组成的字符串S。

输出格式

输出一个整数表示答案。

样例输入

复制

ababc

样例输出

复制

21

提示

样例说明：

子串f值：

a     1

ab    2

aba   1

abab  0

ababc 1

b    1

ba   2

bab  1

babc 2

 a   1

 ab  2

 abc 3

  b  1

  bc 2

   c 1

对于20% 的评测用例，1 ≤ n ≤ 10；

对于40% 的评测用例，1 ≤ n ≤ 100；

对于50% 的评测用例，1 ≤ n ≤ 1000；

对于60% 的评测用例，1 ≤ n ≤ 10000；

对于所有评测用例，1 ≤ n ≤ 100000。

从C语言网学来的方法，思路十分巧妙。

#include <bits/stdc++.h>
using namespace std;
int m[27][3];//存值，0，1，2三个下标分别代表现在所处位置和前两个所处位置
string s;
int main()
{
    cin>>s;
    int i;
    long long sum=0;
    long long qian=0;
    for(i=0;i<s.length();i++)
    {
        int x=s[i]-'a';
        m[x][0]=i+1;//存位置
        qian=qian+(m[x][0]-m[x][1])-(m[x][1]-m[x][2]);//可能出现在的字串数
        sum=sum+qian;
        m[x][2]=m[x][1];//更新状态
        m[x][1]=m[x][0];//更新状态
    }
    printf("%d\n",sum);
    return 0;
}

还有一种是我自己写的，但会超时，思路也比较简单，使用set直接遍历，可以快速拿分。

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
  string s;
  set<char> s1;
  int cnt = 0;
  int t = 0;
  cin >> s;
  int size = s.size();
  for (int i = 0; i < size; i++) {
    s1 = {};
    for (int j = i; j < size; j++) {
      s1.insert(s[j]);
      cnt += s1.size();
      t++;
    }
  }
  cout << cnt;
  return 0;
}