传送门:BZOJ 2038
题意很明确,是在给定的区间内任意选取两个数,求选到两个相同的数的概率。
所以我们得首先统计在给定的区间内,相同的数对有多少对,那么这里就使用到了莫队算法。如果对莫队算法还不够了解,请百度一下,会有比较详细的解释,(虽然有一些也在瞎扯蛋),然后套模版就行了。其次这道题还需要用到一点组合数学知识,即C(n,r)=n!/[r! * (n-r)!]。设每次询问的区间长度为l,那么我们可以很快的计算出从l个数中任取两个的组合数为C(l,2)=l*(l-1)/2,套用公式即可。题目要求的概率也就是:区间内 相同的数对数/任取两个的组合数,再进行约分即可。
另外,因为n,m的最大值是50000,所以组合数可能会超过整型范围,所以本题需要开long long
代码如下:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <string>
#include <map>
typedef long long ll;
using namespace std;
const int MAXN = ;
ll n, m;
ll L, R;
ll block;
ll c[MAXN];
ll cnt[MAXN];
ll ans;
ll s1[MAXN], s2[MAXN]; struct like {
ll l, r;
ll No;
} qry[MAXN]; inline ll gi() {
char c;
ll sum = , f = ;
c = getchar();
while (c < '' || c > '') {
if (c == '-')
f = -;
c = getchar();
}
while (c >= '' && c <= '') {
sum = sum * + c - '';
c = getchar();
}
return sum * f;
} inline bool cmp(like a, like b) {
if (a.l / block != b.l / block)
return a.l < b.l;
return a.r < b.r;
} inline void add(ll p) {
ans += cnt[c[p]];
cnt[c[p]]++;
} inline void remove(ll p) {
cnt[c[p]]--;
ans -= cnt[c[p]];
} inline void save(ll p, ll a, ll b) {
if (a == ) {
s1[qry[p].No] = ;
s2[qry[p].No] = ;
return;
}
ll tpa = a, tpb = b;
if (tpa < tpb)
swap(tpa, tpb);
while (tpb) {
ll r = tpa % tpb;
tpa = tpb;
tpb = r;
}
s1[qry[p].No] = a / tpa;
s2[qry[p].No] = b / tpa;
} int main() {
n = gi();
m = gi();
for (ll i = ; i <= n; i++)
c[i] = gi();
for (ll i = ; i <= m; i++) {
qry[i].l = gi();
qry[i].r = gi();
qry[i].No = i;
}
block = sqrt(n);
sort(qry + , qry + m + , cmp);
L = ;
R = ;
cnt[c[]] = ;
for (ll i = ; i <= m; i++) {
while (L < qry[i].l) {
remove(L);
L++;
}
while (L > qry[i].l) {
L--;
add(L);
}
while (R > qry[i].r) {
remove(R);
R--;
}
while (R < qry[i].r) {
R++;
add(R);
}
ll l = qry[i].r - qry[i].l + ;
save(i, ans, l * (l - ) / );
}
for (ll i = ; i <= m; i++)
printf("%lld/%lld\n", s1[i], s2[i]);
return ;
}
[BZOJ 2038]小Z的袜子的更多相关文章
-
bzoj 2038 小Z的袜子(hose)(莫队算法)
2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 11542 Solved: 5166[Sub ...
-
(原创)BZOJ 2038 小Z的袜子(hose) 莫队入门题+分块
I - 小Z的袜子(hose) 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z ...
-
BZOJ - 2038 小Z的袜子(普通莫队)
题目链接:小Z的袜子 题意:$n$只袜子,$m$个询问,每次回答有多大概率在$[L,R]$区间内抽到两只颜色相同的袜子 思路:普通莫队,如果两个询问左端点在一个块内,则按询问右端点排序,否则按照所在块 ...
-
BZOJ 2038 小z的袜子 &; 莫队算法(不就是个暴力么..)
题意: 给一段序列,询问一个区间,求出区间中.....woc! 贴原题! 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天,小Z再也无法忍受这恼人的找袜子过 ...
-
BZOJ 2038 小Z的袜子(hose) 莫队算法模板题
题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=2038 题目大意: 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中 ...
-
BZOJ 2038 小z的袜子(莫队)
Description 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……具体来说,小Z把这N只袜 ...
-
BZOJ 2038 小Z的袜子(hose)(分组)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2038 题意:给出n个袜子.m个询问,每个询问一个区间[L,R],询问这个区间中任意拿出两 ...
-
bzoj 2038 小z的袜子 莫队例题
莫队,利用可以快速地通过一个问题的答案得到另一问题的答案这一特性,合理地组织问题的求解顺序,将已解决的问题帮助解决当前问题,来优化时间复杂度. 典型用法:处理静态(无修改)离线区间查询问题. 线段树也 ...
-
[bzoj] 2038 小Z的袜子(hose) || 莫队
原题 给出一个序列,求给定[l,r]内有任意取两个数,有多大概率是一样的 简单的莫队,每次+-当前区间里有的这个颜色的袜子的个数,最后除以(r-l+1)*(r-l)/2即可. 记得约分. #inclu ...
随机推荐
-
NYOJ:题目529 flip
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=529 由于此题槽点太多,所以没忍住...吐槽Time: 看到这题通过率出奇的高然后愉快的进 ...
-
python实现微信打飞机游戏
环境:Ubuntu 16.04 LTS Python 2.7.11 + Pygame + Pycharm 代码: # -*- coding: UTF-8 -*- import pygame, ran ...
-
启动BPM的5个步骤
在大部分业务中,我们通常认为:一个主要的业务流程管理项目从设计时间开始会比较好.我们知道很多方式来提高效率,增加生产力以及简化我们员工的工 作 - 这正是业务流程管理所做的.不幸的是,不管我们意图多好 ...
-
Java关键字介绍之this与super
1.什么是super?什么是this? super关键字表示超(父)类的意思.this变量代表对象本身. 2.使用super&this调用成员变量和方法 可以使用super访问父类被子类隐藏的 ...
-
PHP输出缓冲控制- Output Control 函数应用详解
说到输出缓冲,首先要说的是一个叫做缓冲器(buffer)的东西.举个简单的例子说明他的作用:我们在编辑一篇文档时,在我们没有保存之前,系统是不会向磁盘写入的,而是写到buffer中,当buffer写满 ...
-
Android ViewPager的每个页面的显示与销毁的时机
大家在用viewPager的时候要创建一个pagerAdapter对象,用于给viewPager设置页面的. viewPager里面有一个container容器. viewPager的容器缓存3个显示 ...
-
Android Studio中JNI -- 1 -- 配置方法
1.配置NDK 1.1 下载NDK Android Studio 1.2 配 android-ndk-r10e,不同版本的Studio需要配置不同的ndk,下载完成后,随便解压放至某个文件目录下 1. ...
-
你应该掌握的C++ RAII手法:Scopegaurd
C++作为一门Native Langueages,在C++98/03时代,资源管理是个大问题.而内存管理又是其中最大的问题.申请的堆内存需要手动分配和释放,为了确保内存正确释放,一般原则是" ...
-
matplotlib极坐标方法详解
一.极坐标 在平面内取一个定点O,叫极点,引一条射线Ox,叫做极轴,再选定一个长度单位和角度的正方向(通常取逆时针方向).对于平面内任何一点M,用ρ表示线段OM的长度(有时也用r表示),θ表示从Ox到 ...
-
Delphi Math单元函数
本文转至http://blog.sina.com.cn/s/blog_976ba8a501010vvf.html 这个单元包含高性能的算术.三角.对数.统计和金融方面的计算及FPU程序函数用于补充De ...