[牛客暑期多校第八场][思维]B-Beauty Values

发布于 2019-08-12  166 次阅读


https://ac.nowcoder.com/acm/contest/888/B

题意 给一个长度为n的数列 一个区间内不同数字的个数被称作这个区间的贡献值 求所有区间的贡献值之和
这个题我们卡了2个多小时 最后云写代码居然AC了 这个题题解给的思路说的也是很不清晰 到今天网上也没有一篇把道理说明白的题解 但是过的人就是很多。。。大家可能都是半猜的?
做法 :记录一个数字上一次出现的位置
当前位置i 的贡献就是(n-i+1)*(i-las[i])
我也不知道道理是什么道理。。。不同的数字肯定比相同的数字贡献值要多。。。
但是我还是不能理解这么做的道理。。。

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;

int a[maxn], lst[maxn];
int n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ans += 1ll * (i - lst[a[i]]) * (n - i + 1);
		lst[a[i]] = i;
	}
    cout<<ans<<endl;
	return 0;
}
//1 1 2 3 1+1+1+1+1+2+2+2+3+3 
//1 2 1 3 1+1+1+1+2+2+2+2+3+3

愿风指引你的道路,愿你的刀刃永远锋利。