子串分值和
子串分值和
题目
解题思路
对于案例：
1 a
2 ab
2 aba
2 abab
3 ababc
1 b
2 ba
2 bab
3 babc
1 a
2 ab
3 abc
1 b
2 bc
1 c
遍历，从0开始遍历，向当前字母拼接后面的字母，逐个拼接
对于第一次出现的字母
1 a
2 ab
2 aba
2 abab
3 ababc
第一个a贡献了4次
1 b
2 ba
2 bab
3 babc
第一个b贡献了4+4=8次
对于第一次出现的字母，除了对后面逐个拼接每个字母直到字符串最后 所形成的子字符串有贡献度，如果前面还有别的字母,则贡献 多 k(前面其他字母的个数)倍
所以对于第一次出现的字母
贡献度 = (当前数组下标[字符串字符从0开始]+1) * (字符串的长度-当前字符串下标[即从当前字符到结束有多长])
对于不是第一次出现的字符
1 a
2 ab
3 abc
1 b
2 bc
向后拼接剩余的字母，贡献度为(字符串的长度-当前字符串下标[即从当前字符到结束有多长])
向前的贡献度为(当前下标[下标为从1开始，字符串下标从0开始]-上一次出现的下标)
直到上一次出现，中间有几个字母多几倍
所以对于不是第一次出现的字母
贡献度 = （当前下标-上一次出现的下标）*（字符串剩余的长度(包含当前字母)）
解题代码
注意
由于数据较大，相加可能会爆int
package 蓝桥杯.真题2020; import java.util.Scanner; public class 子串分值和 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[] str = sc.next().toCharArray();//输入的字符串 long len = str.length; int[] preIndex = new int[26];//字符上一次出现的位置 long ans = 0; for ( int i=0; i<len; i++ ) { //未出现过 //出现过记录上一次出现的下标 //从1开始 //贡献为（当前下标+1） * （后面字符串剩余长度(包含当前)） if ( preIndex[str[i]-'a']==0 ) { long gx = (i+1)*(len-i); ans += gx; preIndex[str[i]-'a'] = i+1; } else { //出现 //（当前下标-上一次出现的下标）*（字符串剩余的长度） long gx = (i+1-preIndex[str[i]-'a'])*(len-i); ans += gx; preIndex[str[i]-'a'] = i+1; } } System.out.println(ans); } }
