首页 > 代码库 > ZOJ - 3872 Beauty of Array

ZOJ - 3872 Beauty of Array

题意:给定一个含有N个数的序列S,定义序列的魅力值为序列中不同数字之和,求出该序列所有子序列的魅力值之和。

分析:每个数乘以它出现的次数,求和即可。

如何求每个数出现的次数?

1、对于一个各数字完全不同的序列,

eg:3 5 2 6 8

对于5来说,确定其存在于的子序列

(1)其右面,可选0个数字---5

        可选1个数字---3 5

(2)其右面,可选0个数字---5

        可选1个数字---5 2

        可选2个数字---5 2 6

            可选3个数字---5 2 6 8

因此,2 * 4 = 8,则5存在于8种子序列中。

2、若序列中出现了重复数字,那么左边直接处理到该重复数字之前出现的位置后即可。

eg:2 3 3 2

对于第二个3,在计算其存在于的子序列时,只需要考虑3(第二个3) 和 3 2 两个子序列即可。

原因:2 3 3 2的子序列有

2

3

2 3

3

3 3

2 3 3

2

3 2

3 3 2

2 3 3 2

我现在只要把这些各序列中不同的数字相加即可。

从左往右开始考虑,2存在于4个子序列中,所以将这4个子序列中的2先加起来,还剩下

2

3

2 3

3

3 3

2 3 3

2

3 2

3 3 2

2 3 3 2

同理,3(序列中第一个3)存在于6个子序列中,还剩下

2

3

2 3

3

3 3

2 3 3

2

3 2

3 3 2

2 3 3 2

现在,来考虑第2个3,按照“若序列中出现了重复数字,那么左边直接处理到该重复数字之前出现的位置后即可”,只需划掉3 和3 2两个序列中的3,还剩下

2

3

2 3

3

3 3

2 3 3

2

3 2

3 3 2

2 3 3 2

最后,划掉最后一个2存在的序列中的这个2,剩下

2

3

2 3

3

3 3

2 3 3

2

3 2

3 3 2

2 3 3 2

其实,求的就是这些划掉数字的和,因为序列中重复的数字不需要研究呀。

因此,对于序列中出现的第二个3,他出现的序列范围为啥不是从最左面开始选数字,而是从该数字最后一次出现的位置后选数字,

因为,从最后一次出现的位置前开始选数字,因为那个之前出现过的数字所包含于的序列,已经把那个之前出现过的数字加上了,没必要再加这个数字了,

eg:

技术分享这一段,这第二个3如果从最后一次出现的位置前开始选数字,假设从最左面取吧,那形成的序列是2 3 3,在研究第一个3时,该序列已经加过一个3了,(答案只需要该序列中加一个3就行呀)不需要再加第2个3了,所以没必要从最后一次出现的位置前选数字。

#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<sstream>#include<iterator>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<stack>#include<deque>#include<queue>#include<list>#define lowbit(x) (x & (-x))const double eps = 1e-8;inline int dcmp(double a, double b){    if(fabs(a - b) < eps) return 0;    return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 1000000 + 10;const int MAXT = 10000 + 10;using namespace std;int last[MAXN];int main(){    int T;    scanf("%d", &T);    while(T--){        int n, x;        scanf("%d", &n);        memset(last, -1, sizeof last);        LL ans = 0;        for(int i = 0; i < n; ++i){            scanf("%d", &x);            ans += x * LL(i - last[x]) * (n - i);            last[x] = i;        }        printf("%lld\n", ans);    }    return 0;}

 

ZOJ - 3872 Beauty of Array