ZOJ 3872 Beauty of Array（数学） - c++编程基础

TOP

ZOJ 3872 Beauty of Array（数学）

2015-11-21 01:03:54 来源: 作者: 【大中小】浏览:2次

Beauty of Array

Time Limit: 2 Seconds Memory Limit: 65536 KB

Edward has an array A with N integers. He defines the beauty of an array as the summation of all distinct integers in the array. Now Edward wants to know the summation of the beauty of all contiguous subarray of the array A.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains an integer N (1 <= N <= 100000), which indicates the size of the array. The next line contains N positive integers separated by spaces. Every integer is no larger than 1000000.

Output

For each case, print the answer in one line.

Sample Input

Sample Output

105
21
38

题意：定义一个序列的美丽值为序列中不同数的和，求一个序列的所有子序列的美丽值的和

思路：在代码中，关键是理解我C(x,2)代表取得区间是左开右闭的

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 typedef long long ll; #define fre(i,a,b) for(i = a; i 
            
             = a;i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define ssf(n) scanf("%s", n) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi\n") using namespace std; #define INF 0x3f3f3f3f #define N 1000005 int ha[N],hato[N]; int a[N],b[N]; vector
             
              g[N]; int n; int k; void solve() { int i,j; ll ans=0; ll temp; fre(i,0,k) { ans+=(long long)(n)*(n+1)/2*hato[i]; //根据德保大神点拨， temp=0; //例如一个区间有3的位置为(这里用真实位置，不是从0开始) // 3 .. 5... 8 假设在0位置有一个3 //那么有3的位置 0 3 5 8 //因为加了0，所以序列一共n+1个数，假设n+1个数都是3 //，现在任取两个数s,e作为 //有效区间为[s+1，e]时,那么就会加一个3，此时是上面那一步 //现在因为两个3之间并不都是3 //所以要去重，假设两个3之间的数的数目，设为x，那么应该x++, //因为下面的C(x,2)代表取得区间的有效值是做开右闭的 //去掉的个数应该是C(x,2),当然减去的东西应该 再 * 3（这里的3代表原序列相同的数） fre(j,0,g[i].size()) { ll tt=g[i][j]+1-temp; ans-=(tt)*(tt-1)/2*hato[i]; temp=g[i][j]+1; } ll tt=n+1-temp; ans-=(tt)*(tt-1)/2*hato[i]; } pf("%lld\n",ans); } int main() { int i,j,t; sf(t); while(t--) { sf(n); fre(i,0,n) { sf(a[i]); b[i]=a[i]; } sort(b,b+n); k=unique(b,b+n)-b; //担心数据太大，哈希预处理 for(i=0;i
              
               ?
               ?
               ?
               ?
               ?
               ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：How to launche powershell scrip..	下一篇：hdu 1204 糖果大战 (Markov Chain..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: