BZOJ 2038: [2009国家集训队]小Z的袜子(hose)
2018-06-27 10:06:11来源:未知 阅读 ()
2038: [2009国家集训队]小Z的袜子(hose)
Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 13740 Solved: 6225
[Submit][Status][Discuss]
Description
作为一个生活散漫的人,小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
1 2 3 3 3 2
2 6
1 3
3 5
1 6
Sample Output
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。
HINT
Source
版权所有者:莫涛
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=50005; 5 typedef long long ll; 6 7 inline int read() 8 { 9 int i=0;char c=getchar(); 10 while(c>'9'||c<'0')c=getchar(); 11 while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar(); 12 return i; 13 } 14 15 struct node{ 16 int l,r,pos; 17 }a[maxn]; 18 struct Node{ 19 ll x,y; 20 }ans[maxn]; 21 int b[maxn],sum[maxn],belong[maxn]; 22 int n,m,now,l,r,block; 23 24 inline bool cmp(node x,node y) 25 { 26 return belong[x.l]==belong[y.l]?x.r<y.r:belong[x.l]<belong[y.l]; 27 } 28 29 inline ll gcd(ll x,ll y) 30 { 31 return x==0?y:gcd(y%x,x); 32 } 33 34 int main() 35 { 36 n=read(); 37 m=read(); 38 block=sqrt(n); 39 for(int i=1;i<=n;i++) 40 { 41 b[i]=read(); 42 belong[i]=(i-1)/block+1; 43 } 44 for(int i=1;i<=m;i++) 45 a[i]=(node){read(),read(),i}; 46 sort(a+1,a+1+m,cmp); 47 l=r=a[1].l; 48 sum[b[a[1].l]]=1; 49 for(int i=1;i<=m;i++) 50 { 51 while(l<a[i].l)now-=(--sum[b[l++]]); 52 while(r>a[i].r)now-=(--sum[b[r--]]); 53 while(l>a[i].l)now+=(sum[b[--l]]++); 54 while(r<a[i].r)now+=(sum[b[++r]]++); 55 ans[a[i].pos]=(Node){now,(ll)(r-l+1)*(r-l)/2}; 56 } 57 for(int i=1;i<=m;i++) 58 { 59 if(ans[i].x==0||ans[i].y==0) 60 cout<<"0/1"<<endl; 61 else 62 { 63 ll c=gcd(ans[i].x,ans[i].y); 64 printf("%lld/%lld\n",ans[i].x/c,ans[i].y/c); 65 } 66 } 67 return 0; 68 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 题解 P4850 【[IOI2009]葡萄干raisins】 2020-03-12
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash