本文主要是介绍B-Beauty Values，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://ac.nowcoder.com/acm/contest/888/B
Gromah and LZR have entered the second level. There is a sequence a[1], a[2], ……a[n]on the wall.
There is also a note board saying “the beauty value of a sequence is the number of different elements in the sequence”.
LZR soon comes up with the password of this level, which is the sum of the beauty values of all successive subintervals of the sequence on the wall.
Please help them determine the password!
**题意：给你一个序列，让你求出 所有子区间的不同数字的个数 总和
思路：找每个数字对总和的贡献，对于一个位置pos的数字x 找到pos前面第一个x出现的位置i，x数字的贡献是
（ pos - i + 1） * （n - pos + 1）
可能这个公式可以这样理解，左面的个数乘上右边的个数（包括他自己的）
记录一下每个数字出现时的的位置
**
1 2 1 3
对于第一个1就是 1 * 4 个 包括他自己，左1右4
对于第二个就是2 * 3 = 6
对于第三个1之前出现过了，然后前面一个1已经算过这个1的区间了 就是 2 * 2 = 4左2右2
最后一个就是4 * 1 左4右1
综合就是4 + 6 + 4 + 4 是18
也就是对于每个数字查找它所在的区间有多少个，相加之和。
#include <iostream>
using namespace std;
typedef long long ll ;
int vis[100010];
int a[110000] ;
int main()
{int n ;cin >> n ;for(int i = 1;i <= n;i ++)scanf("%d",&a[i]) ;ll ans = 0 ;for(int i = 1;i <= n;i ++){if(vis[a[i]]){ans += 1ll * (n - i + 1) * (i - vis[a[i]]) ;// cout << ans << endl ;}else ans += 1ll * (n - i + 1) * i ;// , cout << ans << endl ;vis[a[i]] = i ; }cout << ans << endl ;return 0 ;
}
这篇关于B-Beauty Values的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
