HYSBZ - 2038 小Z的袜子(hose) (莫队入门)_hysbz 1217-程序员宅基地

技术标签: 暴力  

题目:

作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

Input

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

Output

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

Sample Input

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

Sample Output

2/5

0/1

1/1

4/15

【样例解释】 询问1:共C(5,2)=10种可能,其中抽出两个2有1种可能,抽出两个3有3种可能,概率为(1+3)/10=4/10=2/5。 询问2:共C(3,2)=3种可能,无法抽到颜色相同的袜子,概率为0/3=0/1。 询问3:共C(3,2)=3种可能,均为抽出两个3,概率为3/3=1/1。 注:上述C(a, b)表示组合数,组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。 【数据规模和约定】 30%的数据中 N,M ≤ 5000; 60%的数据中 N,M ≤ 25000; 100%的数据中 N,M ≤ 50000,1 ≤ L < R ≤ N,Ci ≤ N。

分析:莫队入门 https://www.cnblogs.com/Paul-Guderian/p/6933799.html

代码:

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define LIST_INIT_SIZE 100000
#define LISTINCREMENT 10
#define mod 256
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define FRER() freopen("in.txt","r",stdin);
#define FREW() freopen("out.txt","w",stdout);
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
const int maxn = 50000 + 7;
ll color[maxn];
ll cnt[maxn];
ll resl[maxn],resr[maxn];
int pos[maxn];
int n,m,bas;
struct query{
    int l,r,id;
    bool operator < (const query& rhs) const {
        return pos[l] == pos[rhs.l] ? pos[r] < pos[rhs.r] : pos[l] < pos[rhs.l];
    }
}q[maxn];
ll gcd(ll a,ll b){
    return b == 0 ? a : gcd(b,a%b);
}
ll ans;
void Add(int pos){
    ans -= cnt[color[pos]]*(cnt[color[pos]]-1);
    cnt[color[pos]]++;
    ans += cnt[color[pos]]*(cnt[color[pos]]-1);
}
void Del(int pos){
    ans -= cnt[color[pos]]*(cnt[color[pos]]-1);
    cnt[color[pos]]--;
    ans += cnt[color[pos]]*(cnt[color[pos]]-1);
}
int main(){
//    freopen("i.txt","r",stdin);
    while(~scanf("%d%d",&n,&m)){
        bas = sqrt(n);
        memset(color, -1, sizeof(color));
        for(int i=1;i<=n;i++){
            scanf("%lld",&color[i]);
            pos[i] = i / bas;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id = i;
        }
        memset(cnt,0,sizeof cnt);
        sort(q+1,q+m+1);
        int l = 1 , r = 0;
        ans = 0;
        for(int i=1;i<=m;i++){
            while(l>q[i].l) Add(--l);
            while(l<q[i].l) Del(l++);
            while(r<q[i].r) Add(++r);
            while(r>q[i].r) Del(r--);
            resl[q[i].id] = ans;
            resr[q[i].id] = (ll)(r-l+1)*(r-l);
        }
        for(int i=1;i<=m;i++){
            ll g = gcd(resl[i], resr[i]);
            printf("%lld/%lld\n",resl[i]/g,resr[i]/g);
        }
    }
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/insist_77/article/details/82934698

智能推荐

UA MATH523A 实分析1 集合论基础1 基本概念复习_实分析复习-程序员宅基地

文章浏览阅读212次。UA MATH523A 实分析1 集合论基础先复习几个概念:ϕ\phiϕ(空集)、N\mathbb{N}N(自然数集,不含0)、Z\mathbb{Z}Z(整数集)、Q\mathbb{Q}Q(有理数集)、R\mathbb{R}R(实数集)、C\mathbb{C}C(复数集)集合的关系:A⊂BA \subset BA⊂B(subset of)、A=BA=BA=B(A⊂BA \subset BA⊂B and B⊂AB \subset AB⊂A)P(A)\mathcal{P}(A)P(A)是AAA的幂集(_实分析复习

第一篇博客——我的日记_臧诗哲-程序员宅基地

文章浏览阅读233次。今日日记四级出来了,620分,尚且满意,但是我很担心我的六级,我还想考专八,我还想考N2,時間はない!!!!我竟然今天还咸鱼了一下午,蛤。嗯,还有30天就要考计算机二级了,我报的是C++。虽然我最熟悉亲切的应该是C语言,但是光学一点自己已经会的没什么意思不是吗?至少刚才我是这么想的。可是面向对象好难啊!虽然和struct有一定的相似之处,但是各种乱七八糟的名词还是搞得我晕晕的,解构函数,对象..._臧诗哲

为什么使用非线性激活函数?常见的非线性激活函数及优缺点对比_为什么隐层要使用非线性激活函数‘’-程序员宅基地

文章浏览阅读3.6k次,点赞2次,收藏25次。为何使用非线性激活函数? ​如上图的神经网络,在正向传播过程中,若使用线性激活函数(恒等激励函数),即令,则隐藏层的输出为即可以看到使用线性激活函数神经网络只是把输入线性组合再输出,所以当有很多隐藏层时,在隐藏层使用线性激活函数的训练效果和不使用影藏层即标准的Logistic回归是一样的。故我们要在隐藏层使用非线性激活函数而非线性的。通常只有一个地方..._为什么隐层要使用非线性激活函数‘’

使用TLC2543来读取电压_yh=25ea42cf43dce3e-程序员宅基地

文章浏览阅读4.6k次,点赞12次,收藏53次。这个星期,我使用TLC2543这款芯片来读取输入的电压值,显示模块则是使用的LCD1602,程序不难,很适合初学者。#include<reg51.h>#include <stdio.h>#include <math.h>#include <string.h>#define uint8_t unsigned char //0-255#define uint16_t unsigned int //0-65535#define uint32_t un_yh=25ea42cf43dce3e

vue中使用原生JS框架 例如 JTopo (vue-cli 3.0)_vue cli 加载jtopo-程序员宅基地

文章浏览阅读4.4k次。参考 : https://cli.vuejs.org/zh/guide/html-and-static-assets.html#htmlHTML#Index 文件public/index.html 文件是一个会被 html-webpack-plugin 处理的模板。在构建过程中,资源链接会被自动注入。另外,Vue CLI 也会自动注入 resource hint (preload/pr..._vue cli 加载jtopo

WIndows的CMD\PowerShell命令行启动程序后台运行类似Linux系统的nohup命令_windows nohup-程序员宅基地

文章浏览阅读3.9k次,点赞3次,收藏3次。cmd或者powershell实现类似Linux中的nohup命令,进行后台启动程序_windows nohup

随便推点

smartforms 调用代码-程序员宅基地

文章浏览阅读91次。1 REPORT zscm_taobaoso_ptint.2 INCLUDE zscm_taobaoso_ptint_d01.3 INCLUDE zscm_taobaoso_ptint_s01.4 INCLUDE zscm_taobaoso_ptint_e01.5 INCLUDE zscm_taobaoso_ptint_f01. 1 TABLES: VBAK..._alv 連接smartforms 實例

ADI锁相环LTC6946-2使用(1-环路滤波器设计)-程序员宅基地

文章浏览阅读1.1k次,点赞4次,收藏7次。嵌入式软件开发List item_adi锁相环

2022最新阿里Java面经,转疯了-程序员宅基地

文章浏览阅读2k次。写在前面最近,很多小伙伴出去面试都被问到了Spring问题,关于Spring,细节点很多,面试官也非常喜欢问一些很细节的技术点。所以,在 Spring 专题中,我们尽量把Spring的每个技术细节说清楚,将透彻。概述自定义组件要想使用Spring容器底层的一些组件(比如:ApplicationContext、BeanFactory等),此时,只需要让自定义组件实现XxxAware接口即可。此时,Spring在创建对象的时候,会调用XxxAware接口定义的方法,注入相关的组件。Java并发编程3、_java面经

使用Fiddler抓取夜神模拟器Android7.1版本中的app的包_fiddler手机抓包/模拟器抓包 android 7.1-程序员宅基地

文章浏览阅读3.3k次,点赞7次,收藏20次。1.Fiddler下载https://www.telerik.com/download/fiddler然后傻瓜下一步2.夜神模拟器下载https://www.yeshen.com/我下的是最新版的安卓7.1内核的,所有的坑也出在这3.配置Fiddler打开tools -> options勾选后之后,点击那个Actions选择Export Root Certificate To Desktop(不方便截图) 导出证书到桌面。然后再设置一下这个地方:之后重启Fiddler4._fiddler手机抓包/模拟器抓包 android 7.1

Au 音频效果参考:延迟与回声-程序员宅基地

文章浏览阅读4.4k次。Au菜单:效果/延迟与回声Delay and Echo延迟 Delay,是指在数毫秒之内相继重新出现的单独的原始信号副本。回声 Echo,是在时间上延迟得足够长的声音,以便每个回声听起来都..._au中的phase invert

unityui炫酷动画_Unity_Animation实现UI星星闪耀效果①-程序员宅基地

文章浏览阅读1.3k次。RT.用于做UI布局。1.canvas内新建image,把星星的素材图拖入到源图里。顺便给面板内的图片一个star的命名。2.新建prefab文件夹把星星做成预制体。3.新建animator文件夹,里面创建关于星星的动画和动画控制器,动画勾选looptime,让它循环播放,然后点击即开始。4.星星预制体内添加一个animator,控制器选中刚刚做的星星控制器。5.设置animation。 这里期待..._u3d ui动画