蓝桥杯子串分值（算贡献）

太过爱你忘了你带给我的痛 2021-07-17 01:14 406阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70 1]

## 思路 ##

一开始看到数据范围，n=1e5，那么只可以遍历一次，那么如何在一次之内算出全部贡献？细心一些可以发现对于字母来说只有26个，这便是本题的突破口，我们只需在这一次遍历内算出每个字母的贡献即可。  
首先将子串分为n类—以第i号元素为结尾的子串（1<=i<=n）  
a对于以第i号元素为结尾类子串的贡献  
=0（第i号元素之前没出现过a）  
=a出现时的位置（在第i号元素之前a只出现过一次）  
=最近两次a出现过的位置之差（在第i号元素出现之前a出现两次以上）  
由上知道我们所需记录的信息就是在当前第i号元素之前最近两次各元素出现的位置。  
最后全部的贡献就是所有26个子母贡献相加即可。

## Code ##

#include<iostream>
    using namespace std;
    const int Max = 1e6 + 5;
    
    int b[30][2];//b[30]是26个字母，b[x][1]是x字母最近出现的位置，b[i][0]是x字母第二个最近出现的位置
    
    int value()
    { 
    	int sum = 0;
    	for (int i = 1;i <= 26;i++)
    	{ 
    		if (b[i][0] != 0 && b[i][1] == 0)sum += b[i][0];
    		else if (b[i][0] != 0 && b[i][1] != 0)sum += b[i][1] - b[i][0];
    	}
    	return sum;
    }
    
    int main()
    { 
    	string str;cin >> str;
    	str.insert(str.begin(), '#');//只是为了凑个位置令个元素位置+1
    	long long ans = 0;
    	for (int i = 1;i < str.size();i++)
    	{ 
    		int t = str[i] - 'a' + 1;
    		if (b[t][0] == 0)b[t][0] = i;
    		else if (b[t][0] != 0 && b[t][1] == 0)b[t][1] = i;
    		else b[t][0] = b[t][1], b[t][1] = i;
    		ans += value();
    	}
    	cout << ans;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210415192929745.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70 1]: /images/20210716/c209f1c258564ce094ec30308355902e.png