问题描述:

小Z把这N只袜子从1到N编号,然后从编号L到R中抽两只袜子。你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。他可能会询问多个(L,R)以方便自己选择。

输入:

第一行包含两个正整数N和M。N为袜子的数量,M为小Z所提的询问的数量。
接下来一行包含N个正整数Ci,其中Ci表示第i只袜子的颜色,相同的颜色用相同的数字表示。
再接下来M行,每行两个正整数L,R表示一个询问。

输出:

包含M行,对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1,否则输出的A/B必须为最简分数。

思路:

这道题可以说是莫队的模板了。首先考虑如何计算概率,在给定的区间内抽到两只颜色相同的袜子的概率是$ans=(Σ(sum(color[i])^2)−(R−L+1))/((R−L+1)∗(R−L))$。

然后就使用莫队,先将问题离排序,离线操作,写一个update函数进行转移。详细内容可以看代码啦。

最后输出答案时应输出最简分数,记得要分子分母同除GCD。

代码:

#include <bits/stdc++.h>
#define MAXN 50005
#define LL long long
using namespace std;

int n, m, l=1, r, size, col[MAXN], belong[MAXN];
LL ans, sum[MAXN];

struct Q {int l, r, id; LL x, y;} q[MAXN];

bool CMP1(Q x, Q y) 
{
    if(belong[x.l]==belong[y.l]) return x.r<y.r; 
    else return x.l<y.l;
}

bool CMP2(Q x, Q y) {return x.id<y.id;}

void update(int pos, int opt)
{
    ans-=sum[col[pos]]*sum[col[pos]];
    sum[col[pos]]+=opt;
    ans+=sum[col[pos]]*sum[col[pos]];
}

int main()
{
    scanf("%d%d", &n, &m);
    size=sqrt(n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &col[i]);
        belong[i]=i/size+1;
    }
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id=i;
    }
    sort(q+1, q+m+1, CMP1);
    for(int i=1; i<=m; i++)
    {
        while(l<q[i].l) update(l++, -1);
        while(l>q[i].l) update(--l, 1);
        while(r<q[i].r) update(++r, 1);
        while(r>q[i].r) update(r--, -1);
        if(q[i].l==q[i].r)
        {
            q[i].x=0; q[i].y=1;
            continue;
        }
        q[i].x=ans-q[i].r+q[i].l-1;
        q[i].y=(LL)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        LL t=__gcd(q[i].x, q[i].y); 
        q[i].x/=t; q[i].y/=t;
    }
    sort(q+1, q+m+1, CMP2);
    for(int i=1; i<=m; i++) printf("%lld/%lld\n", q[i].x, q[i].y);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注