1 条题解
-
0
方法思路
- 对于每个子串,我们需要计算其极长连续段的数量
- 暴力枚举所有子串并计算权值会导致O(n³)复杂度,效率太低
- 关键优化:考虑每个位置的字符对子串权值的贡献
- 当字符与前一个字符不同时,会在包含该位置的子串中形成新的连续段
- 对于位置i的字符,它在多少个子串中会贡献一个新的连续段:
- 左侧有i个可能的起点
- 右侧有(n-i)个可能的终点
- 总共贡献i*(n-i)个子串
- 遍历字符串,找出所有字符变化的位置,累加贡献值
代码实现
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
- 上传者