博客

原题叙述

一开始觉得挺简单的，结果做的时候才发现有点坑

不知道为什么，网上查这道题答案时，很多题目给出求分值的定义不一样

分析

针对上述分析可得出

若不考虑重复情况

可得出

s[i] = (len – i) * (i + 1)

一开始没考虑重复三次以上的情况，导致出现了错误

开始的错误答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
string s;
ll ans;
ll len;
ll now[30];//存储该字母之前最后出现该字母的下标
int main(){
    cin >> s;
    len = s.length();
    memset(now, -1, sizeof now);//初始化
    for (int i = 0;i < len;i++) {
        int c = s[i] - 'a' + 1;
        ll pos = now[c];
        now[c] = i;
        //首次出现
        if (pos == -1) {
            ans += (len - i) * (i + 1);
        }
        else{
            //ans += (i + 1) * (len - i) - (pos + 1) * (len - i) * 2;
            ans += (i - pos * 2 - 1) * (len - i);//化简后
        }
    }
    cout << ans;
    return 0;
}

最后的正确答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
string s;
ll ans;
ll len;
ll pre[N];//存储该字母之前最后出现该字母的下标
ll now[30];//存储该字母之前最后出现该字母的下标
int main(){
    cin >> s;
    len = s.length();
    memset(now, -1, sizeof now);//初始化
    memset(pre, -1, sizeof pre);//初始化
    for (int i = 0;i < len;i++) {
        int c = s[i] - 'a' + 1;
        ll pos = now[c];
        now[c] = i;
        pre[i] = pos;
        //首次出现
        if (pos == -1) {
            ans += (len - i) * (i + 1);
        }
        //第一次重复
        else if(pre[pre[i]] == -1){
            //ans += (i + 1) * (len - i) - (pos + 1) * (len - i) * 2;
            //i  - pos * 2 - 1
            ans += (i - pos * 2 - 1) * (len - i);//化简后
        }
        //二次以上的重复情况
        else {
            //ans += (i + 1) * (len - i) - ((pos + 1)) * (len - i) * 2 + (pre[pre[i]] + 1) * (len - i);
            //i  - pos * 2  + pre[pre[i]]
            ans += (i - pos * 2 + pre[pre[i]]) * (len - i);//化简后
        }
    }
    cout << ans;
    return 0;
}