思路：数学优化

暴力做法

一个最朴素的方法：枚举每个区间（$C(n,2)$个 ），计算区间中极长段的个数。 时间复杂度$O(n^2)$ ， $n = 1e5 , n^2 = 1e10 > 1e8$ , 超时。

数学优化:贡献法

考虑原串其中的某一个极长段对总体答案的贡献:

这$C(n,2)$个区间中，所有跨过了这个极长子段的区间，答案计数 + 1。所以我们可以考虑枚举每个极长段(最多$O(n)$个极长段)，然后统计跨过他的区间个数即可。

进一步的，正难则反：跨过它的区间个数 等价于 所有区间（$C(n,2)$个 ） 减去 不跨过它的区间。

而显然不跨过它的区间个数就是该极长段左边所有子区间个数 以及 该极长段右边所有子区间个数。假设这个极长段的左右端点为$[l,r]$ , 那么答案为: $C(n,2)- (l-1,2) - C(n - r , 2)$

时间复杂度$O(n)$

代码

python

# 计算长度为len的连续子段的个数
def C2(len):
    return len * (len + 1) // 2
n = int(input())  # 输入字符串的长度
s = "$" + input()  # 输入字符串 , 在字符串末尾添加一个特殊字符，以确保最后一个极长段被处理
l = 0  # 记录当前极长段的起始位置
ans = 0  # 记录总体答案
tot = C2(n) 
for i in range(n + 1):
    if i != 0 and s[i] != s[i - 1]: # 如果断开，则找到一个新的极长段[l , i]
        ans += tot - C2(l) - C2(n - i) # 根据上述公式进行计算即可.
        l = i  # 更新极长段的起始位置
print(ans)  # 输出最终答案

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 输入字符串的长度
        String s = sc.next() + "$";  // 输入字符串，在字符串末尾添加一个特殊字符，以确保最后一个极长段被处理
        long l = 0;  // 记录当前极长段的起始位置
        long ans = 0;  // 记录总体答案
        long tot = C2(n);
        for (int i = 0; i <= n; i++) {
            if (i != 0 && s.charAt(i) != s.charAt(i - 1)) { // 如果断开，则找到一个新的极长段[l, i]
                ans += tot - C2(l) - C2(n - i); // 根据上述公式进行计算即可
                l = i; // 更新极长段的起始位置
            }
        }
        System.out.println(ans); // 输出最终答案
    }
    // 计算长度为len的连续子段的个数
    public static long C2(long len) {
        return len * (len + 1) / 2;
    }
}

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
// 计算长度为len的连续子段的个数
ll C2(ll len) {
    return len * (len + 1) / 2;
}
int main() {
    int n;
    cin >> n;  // 输入字符串的长度
    string s;
    cin >> s;  // 输入字符串，在字符串末尾添加一个特殊字符，以确保最后一个极长段被处理
    s = s + "$";
    ll l = 0;  // 记录当前极长段的起始位置
    ll ans = 0;  // 记录总体答案
    ll tot = C2(n);
    for (int i = 0; i <= n; i++) {
        if (i != 0 && s[i] != s[i - 1]) { // 如果断开，则找到一个新的极长段[l, i]
            ans += tot - C2(l) - C2(n - i); // 根据上述公式进行计算即可
            l = i; // 更新极长段的起始位置
        }
    }
    cout << ans << endl; // 输出最终答案
    return 0;
}

题目内容

小红最近迷上了字符串，并且认为一个字符串的美好值为字符串内，连续相同子串的数量。例如“aabbccddef”的美好值为6。

小红的朋友给了他一个01串，已经迷恋上字符串的小红想知道，这个01串所有子串的美好值之和是多少？

注：一共有$C^{2}_{n+1}$个子串

输入描述

第一行输入一个正整数$n$，代表字符串的长度。

第二行为$n$长的01串。

$1\le n\le2*10^5$

输出描述

一个整数

样例

输入

4
0011

输出

14

说明

子串分别为：0，0，1，1，00，01，11，001，011，0011

美好值分别为：1，1，1，1，1，2，1，2，2，2

总美好值为：14