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

153 阅读 1 评论 0 点赞

原题链接：蓝桥杯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 人评分

本文分类：题解列表
浏览次数：153 次浏览
发布日期：2023-03-20 14:46:01
本文链接：https://blog.dotcpp.com/a/95064

上一篇 > vector解决报数问题
下一篇 > 题解 1031: [编程入门]自定义函数之字符串反转

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 1 条评论

恋风吹雪 1年前回复TA

我草大佬牛逼
太他妈详细了，我的理解是这样滴
对于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

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复