xr

用户名：dotcpp0639023

访问量：321

签　名：

等　　级
排　　名	2185
经　　验	2338
参赛次数	0
文章发表	5
年　　龄	23
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

完全二叉树的权值最详细注释
浏览：58

后缀表达式公式
浏览：37

子串分值和-贡献值法，详细样例解释
浏览：68

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

子串分值和-贡献值法，详细样例解释

　　作者: xr　　　　发表时间：2023-03-20 14:46:01 浏览：68　|　评论：1　

原题链接：蓝桥杯2020年第十一届省赛真题-子串分值和

先上暴力法，只能50%
```
package B组;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class 第十一届_子串分值和 {
	// 暴力 50%
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		int sum = 0;
		for(int i = 0; i<str.length(); i++) {	// 起点
			for(int j = i; j<str.length(); j++) {	// 终点
				HashSet set = new HashSet();
				for(int k = i; k<=j; k++) {
//					System.out.print(str.charAt(k));
					set.add(str.charAt(k));
				}
//				System.out.println(set + " " + set.size());
				sum += set.size();
			}
		}
		System.out.print(sum);
	}
}
```
贡献值法
原理：只有当字母个数在子串中个数>0才会有贡献度。
从字符左右两边出发
- 往左直到走到第一个，每走一次left++
- 往右走到与自己相同的字符停止，每次right++
贡献度 = (left+1) * (right+1)

拿ababd举例：
1. 从第一个a开始：左边没有，右边走一步，所以 (0+1)*(1+1)=2
2. 到第二个b：左边1个，右边1个，(1+1)*(1+1)=4
3. 左边2个，右边2个，（2+1）*(2+1)=9
4. 左边3个，右边1个，（3+1）*（1+1)=8
5. 左边4个，右边0个，（4+1）*（0+1）=5
最终：28

```
public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		char[] ch = str.toCharArray();
		long res = 0;
		for(int i = 0; i<ch.length; i++) {
			int left = 0;
			int right = 0;
			// 往左
			for(int j = i-1; j>=0 ; j--) {
				left++;
			}
			// 往右
			for(int j = i+1; j<ch.length && ch[j] != ch[i]; j++) {
				right++;
			}
			res += (long)(left+1)*(right+1);
		}
		System.out.print(res);
	}
```

0.0分

3 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

恋风吹雪

我草大佬牛逼
太他妈详细了，我的理解是这样滴
对于ababd来举例

分左右俩边来看，循环5次

1 记录从自己的位置往左走到最左边需要的次数，每走一次加一，次数记作i

2记录从自己的位置往右走到最右边的次数，但是遇到和自己相同的字母时停止，次数记作j

每一次的结果为（i+1）*(j+1)

最后将每一次相加则为答案

第一次a左边没有，右边走1次遇到相同 结果为（0+1）*（1+1）=2

第二次b左边1右边1 结果为2*2=4

第三次a左边2右边2 结果为9

第四次b左边为3右边1 结果为8

第五次d左边为4右边没有 结果为5

答案2+4+9+8+5=28

2023-04-05 15:47:58

xr

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

简洁的代码

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

子串分值和-贡献值法，详细样例解释

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

求圆的面积（C语言代码）

核桃的数量（C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

核桃的数量（C语言代码）

xr

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

简洁的代码

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

子串分值和-贡献值法，详细样例解释

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

求圆的面积 （C语言代码）

核桃的数量 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

核桃的数量 （C语言代码）

　　评论区

求圆的面积（C语言代码）

核桃的数量（C语言代码）

核桃的数量（C语言代码）