AcWing 2872. 超级好理解 使用贡献法求解Java
原题链接
中等
作者:
苦苣Java
,
2024-03-24 18:09:04
,
所有人可见
,
阅读 2
import java.util.*;
public class Main{
static int N = 100010;
static char []c = new char[N];
static int []last = new int[N];
static int []f = new int[N];
/*
f[i] 表示以c[i]结尾的所有子串的总分值
用last[c[i]] = i表示上一次c[i]出现的索引
使用贡献法 考虑当加入c[i]时 对前i个子串的贡献度为多少?
1:当前i个字符串中不包含c[i], 则对应[1,i-1]中的每个子串的贡献值都+1 即+(i - 1)
2: 当前i个字符串中包含c[i],若上一个c[i]的索引值为last[c[i]],
则第i个字符只能对[last[c[i]]+1,i - 1]中的每个子串的贡献值都+1 即+(i - 1 - last[c[i]])
最后答案统计所有以c[i]结尾的子串的总分值
*/
public static void main(String []args){
Scanner in = new Scanner(System.in);
char []s = in.next().toCharArray();
int n = s.length;
for(int i = 0;i < n;i ++)
c[i + 1] = s[i];
long ans = 0;
for(int i = 1;i <= n;i ++){
f[i] = f[i - 1] + i - last[c[i]];
ans += f[i];
last[c[i]] = i;
}
System.out.println(ans);
}
}