hdu5419-Victor and Toys（枚举）

hdu5419--Victor and Toys（枚举）

题目链接：点击打开链接

题目大意：有n个值a[i]，排成一排，编号为1到n，现在有m个区间[lj,rj]，任意从m个区间里挑选出三个i,j,k，统计编号在[ max(li,lj,lk) , min(ri,rj,rk) ]内的数的和，问最终和的期望是多少。

和的期望 = (∑任意一种挑选方式的和)/(总的挑选方式) = x / y ;

首先y = m*(m-1)*(m-2)/6 ;

至于x，我们可以统计对于一个数a[i]来说，如果有num个区间包含它，这样a[i]出现在x中的次数就是num*(num-1)*(num-2)/6次。所以我们可以计算出每个数的可能的出现次数，然后累加和。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
LL dp[50100] ;
int a[50100] ;
LL gcd(LL a,LL b) {
    return b == 0 ? a : gcd(b,a%b) ;
}
int main() {
    int t , n , m ;
    int i , l , r ;
    LL x , y , temp ;
    scanf("%d", &t) ;
    while( t-- ) {
        scanf("%d %d", &n, &m) ;
        memset(dp,0,sizeof(dp)) ;
        for(i = 1 ; i <= n ; i++)
            scanf("%d", &a[i]) ;
        while( m-- ) {
            scanf("%d %d", &l, &r) ;
            dp[l]++ ;
            dp[r+1]-- ;
        }
        x = 0 ;
        y = (LL)n*(n-1)*(n-2)/6 ;
        for(i = 1 ; i <= n ; i++) {
            dp[i] += dp[i-1] ;
            if( dp[i] > 2 )
                x += dp[i]*(dp[i]-1)*(dp[i]-2)/6*a[i] ;
        }
        if( x == 0 || y == 0 ) {
            printf("0\n") ;
            continue ;
        }
        temp = gcd(x,y) ;
        x /= temp ;
        y /= temp ;
        if( y == 1 )
            printf("%I64d\n", x ) ;
        else
            printf("%I64d/%I64d\n", x, y) ;
    }
    return 0 ;
}