小Z的袜子

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

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

C++ 解法, 执行用时: 115ms, 内存消耗: 4032K, 提交时间: 2021-09-18 19:31:27

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1e5+10;
const int block=200;
int vis[maxn],a[maxn],ans[maxn],fenmu[maxn];
int cnt,n,u,v;
struct point
{
	int u,v,id;
}t[maxn];
bool cmp(point x,point y)
{
	if(x.u/block==y.u/block) return x.v<y.v;
	else return x.u<y.u;
}
int gcd(int x,int y)
{
	if(y==0) return x;
	else return gcd(y,x%y);
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&t[i].u,&t[i].v);
		t[i].id=i;
		fenmu[i]=(t[i].v-t[i].u)*(t[i].v-t[i].u+1);
	}
	sort(t,t+m,cmp);
	int l=1,r=0,ans1=0;
	for(int i=0;i<m;i++)
	{
		//cout<<t[i].u<<" "<<t[i].v<<endl;;
		while(l<t[i].u) ans1-=--vis[a[l]],l++;
		while(l>t[i].u) l--,ans1+=vis[a[l]]++;
		while(r<t[i].v) r++,ans1+=vis[a[r]]++;
		while(r>t[i].v) ans1-=--vis[a[r]],r--;
		//cout<<ans1<<endl;
		ans[t[i].id]=ans1*2;
	}
	for(int i=0;i<m;i++) 
	{
		int r=gcd(ans[i],fenmu[i]);
		cout<<ans[i]/r<<"/"<<fenmu[i]/r<<endl;
	}
}

C 解法, 执行用时: 730ms, 内存消耗: 1580K, 提交时间: 2021-09-15 16:38:35

#include <stdio.h>
#include <string.h>
typedef long long ll;
ll N, M;

void print(ll n, ll m)
{
    ll r=1;
    ll a=n,b=m;
    while (r!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    m=m/a;
    n=n/a;
    printf("%lld/%lld\n", n, m);
}

int main()
{
    scanf("%lld%lld", &N, &M);
    int a[N], g[N + 10];
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &a[i]);
    }
    ll L, R;
    ll m, n;
    for (int i = 0; i < M; i++)
    {
        m = 0, n = 0;
        memset(g, 0, sizeof(g));
        scanf("%lld%lld", &L, &R);
        for (int j = L - 1; j < R; j++)
        {
            n += g[a[j]];
            g[a[j]]++;
        }
        m = (R - L + 1) * (R - L) / 2;
        if (n == 0)
        {
            m=1;
            printf("%lld/%lld\n", n, m);
        }
        else
        {
            print(n, m);
        }
    }
}

详情