【HDOJ 5419】 Victor and Toys

n个玩具 m个区间

每一个玩具有一个beauty值 问任选三个区间 三区间的MINleft~MAXright的和的期望值

预处理一个数组 存放每一个位置被几个区间囊括 这样该位置被选择的概率为c(x,3)/c(m,3)

若beauty数组为w 预处理数组a

期望值即为 w[i]*c(a[i],3)/c(m,3) i∈[1,n]

注意防止乘法爆long long

代码例如以下:

#include <iostream>

#include <cstdio>

#include <cstring>

#define ll long long

using namespace std;

int w[50001];

int ad[50002];

ll C(ll n)//c(n,3)

{

    if(n < 3) return 0;

    ll ans = 1;

    for(int i = 2; i >= 0; --i)//防爆long long

        ans = ans*(n-i)/(3-i);

    return ans;

}

ll gcd(ll a,ll b)//约分

{

    ll tmp;

    while(b)

    {

        tmp = b;

        b = a%b;

        a = tmp;

    }

    return a;

}

int main()

{

    int t,n,m,i,l,r;

    ll fz,fm,gd,lst;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d %d",&n,&m);

        for(i = 1; i <= n; ++i)

            scanf("%d",&w[i]);

        memset(ad,0,sizeof(ad));

        for(i = 0; i < m; ++i)

        {

            scanf("%d %d",&l,&r);

            ad[l]++;

            ad[r+1]--;

        }

        if(m < 3)//不这样做会越界。

。血的教训

        {

            puts("0");

            continue;

        }

        fm = C(m);

        fz = lst = 0;

        for(i = 1; i <= n; ++i)//预处理被选次数顺带把期望求了。。

        {

            lst += ad[i];

            fz += w[i]*C(lst);

        }

        gd = gcd(fz,fm);

        fz /= gd;

        fm /= gd;

        if(fm == 1) printf("%I64d\n",fz);

        else printf("%I64d/%I64d\n",fz,fm);

    }

    return 0;

}