[国家集训队]小Z的袜子(莫队)

[国家集训队]小Z的袜子

题目描述

作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……

具体来说,小Z把这N只袜子从1到N编号,然后从编号LR(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

然而数据中有L=R的情况,请特判这种情况,输出0/1。

输入格式:

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

输出格式:

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

输入样例#1

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

输出样例#1

2/5
0/1
1/1
4/15






解:

这是一道莫队的板子题,所以我们来学波莫队。要是你当时就会莫队,那你就可以把这道数据结构套数据结构啥的题水过去了(不过好像当时没有莫队)。
其实莫队很暴力,不过它要满足几个条件:
1.离线,在线就滚粗(不过可以支持修改)
2.询问在[lr]到[l+1,r]、[l,r+1]等比较好转移

那么为什么满足这个条件就可以过么,我们画个图理解一下:

这里写图片描述

看到这个魔性的图没?这就是奇奇怪怪的莫队算法
我们可以先想象把所有询问放到一个平面里,然后依次回答询问。然后我们证明一下复杂度。假设我们以n分块,如上图,先把块相同的分到一起,然后相同块呢?我们按照从小到大排序。然后我们可以发现横着走点到点的长度不超过n。然后竖着走了(块的个数*2*n的长度)。块的个数也是n
所以我们最坏走的长度是nn
然后怎么走?
要知道我们只有一步一步走,最好让每走一步的复杂度最小。O(1)啥的最好。

然后我们开始看这道题:
同样的,我们把所有询问放进一个平面里。然后考虑加一个点进去。某一种袜子的颜色加一,假设它现在颜色的个数为n

所以我们可以做到O(1)转移咯(去掉一个同理),贴一波代码:

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
long long n,m;  
long long col[50005],data[50005],k=300,l=1,r=1;//k为块大小  
long long ans;//只用计算分子,分母为  区间个数*(区间个数-1)  
long long mu[50005],zi[50005];  
struct lxy{  
    long long id,l,r;  
    long long ans;  
    bool operator < (const lxy &a)const//按块编号从小到大为第一关键字,按l从小到大为第二关键字  
    {  
        if(l/k==a.l/k) return r<a.r;  
        return l/k<a.l/k;  
    }  
}b[50005];  

long long gcd(long long x,long long y)//求个gcd约分  
{  
    if(x==0) return y;  
    return gcd(y%x,x);  
}  

void w()//上走  
{     
    col[data[l]]--;  
    ans-=col[data[l]]*2;l++;  
}  
void a()//左走  
{  
    col[data[r]]--;  
    ans-=col[data[r]]*2;r--;  
}  
void s()//下走  
{  
    l--;ans+=col[data[l]]*2;  
    col[data[l]]++;  
}  
void d()//右走  
{  
    r++;ans+=col[data[r]]*2;  
    col[data[r]]++;  
}  

int main()  
{  
    scanf("%lld%lld",&n,&m);  
    for(int i=1;i<=n;i++) scanf("%lld",&data[i]);  
    for(int i=1;i<=m;i++) scanf("%lld%lld",&b[i].l,&b[i].r),b[i].id=i;  
    sort(b+1,b+1+m);  
    col[data[1]]++;  
    for(int i=1;i<=m;i++)  
    {  
        while(r<b[i].r) d();  
        while(l>b[i].l) s();  
        while(r>b[i].r) a();  
        while(l<b[i].l) w();  
        b[i].ans=ans;  
    }  
    for(int i=1;i<=m;i++)  
    {  
        if(b[i].ans==0||b[i].l==b[i].r)//特殊情况特判  
        {  
          mu[b[i].id]=1;  
          zi[b[i].id]=0;  
        }  
        else//算算gcd,约约分  
        {  
          long long p;  
          p=gcd(b[i].ans,(b[i].r-b[i].l+1)*(b[i].r-b[i].l));  
          zi[b[i].id]=b[i].ans/p;  
          mu[b[i].id]=(b[i].r-b[i].l+1)*(b[i].r-b[i].l)/p;  
        }  
    }  
    for(int i=1;i<=m;i++) printf("%lld/%lld\n",zi[i],mu[i]);  
}  
版权声明:本文为lvmaooi原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lvmaooi/article/details/79727368

智能推荐

26_Python基础_继承

面向对象三大特性: 封装 根据 职责 将 属性 和 方法 封装 到一个抽象的 类 中 继承 实现代码的重用, 相同的代码不需要重复的编写 多态 不同的对象调用相同的方法,  产生不同的执行结果,  增加代码的灵活度 1.  单继承 1.1 概念 继承的概念:&...

循环

与任何程序设计语言一样Java利用条件语句与循环结构确定流程控制,一下总结一下Java中的循环语句: while do while for switch 对于golang来说: switch非常灵活。从第一个expr为true的case开始执行,如果case带有fallthrough,程序会继续执行下一条case,不会再判断下一条case的expr,如果之后的case都有fallthrough,d...

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

猜你喜欢

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...