1 条题解

  • 0
    @ 2025-7-15 19:18:21

    方法思路

    1. 对于每个子串,我们需要计算其极长连续段的数量
    2. 暴力枚举所有子串并计算权值会导致O(n³)复杂度,效率太低
    3. 关键优化:考虑每个位置的字符对子串权值的贡献
      • 当字符与前一个字符不同时,会在包含该位置的子串中形成新的连续段
    4. 对于位置i的字符,它在多少个子串中会贡献一个新的连续段:
      • 左侧有i个可能的起点
      • 右侧有(n-i)个可能的终点
      • 总共贡献i*(n-i)个子串
    5. 遍历字符串,找出所有字符变化的位置,累加贡献值

    代码实现

    Java
    import java.io.*;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            
            long result = 0;
            
            // 每个子串至少有一个连续段
            result += (long)n * (n + 1) / 2;
            
            // 计算额外的连续段贡献
            char[] chars = s.toCharArray();
            for (int i = 1; i < n; i++) {
                if (chars[i] != chars[i - 1]) {
                    result += (long)i * (n - i);
                }
            }
            
            System.out.println(result);
        }
    }
    
    
    Python
    n = int(input())
    s = input()
    
    result = 0
    
    # 每个子串至少有一个连续段
    result += n * (n + 1) // 2
    
    # 计算额外的连续段贡献
    for i in range(1, n):
        if s[i] != s[i-1]:
            # 位置i处字符与前一个不同,会形成新的连续段
            result += i * (n - i)
    
    print(result)
    
    
    C++
    #include <iostream>
    #include <string>
    using namespace std;
    
    int main() {
        int n;
        string s;
        cin >> n >> s;
        
        long long result = 0;
        
        // 每个子串至少有一个连续段
        result += (long long)n * (n + 1) / 2;
        
        // 计算额外的连续段贡献
        for (int i = 1; i < n; i++) {
            if (s[i] != s[i - 1]) {
                // 位置i处字符与前一个不同,会形成新的连续段
                result += (long long)i * (n - i);
            }
        }
        
        cout << result << endl;
        return 0;
    }
    
    
    • 1

    信息

    ID
    91
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者