Problem 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

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

Hint

【樣例解釋】
詢問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。

思路：

對于每一個區間詢問 [l,r]，要求的?

即：

其中，?是第 i 種顏色在 [l,r] 中出現的次數

因此，只要求出各詢問區間中??的值，即可得出答案

此外，n*m 最大為?50000*50000，注意使用 long long

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=10007; const int N=1000000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std;struct Node{int l,r;//詢問的左右端點int id;//詢的編號 }q[N]; int n,m; LL color[N]; int block;//分塊 LL ans,cnt[N*2]; LL nume[N],deno[N];//分子、分母bool cmp(Node a,Node b){//奇偶性排序return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r); } LL GCD(LL x,LL y){return y==0?x:GCD(y,x%y); } void change(int pos,int num){ans+=2*cnt[color[pos]]*num+1;cnt[color[pos]]+=num; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%lld",&color[i]);for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}block=n/sqrt(m*2/3);//分塊sort(q+1,q+m+1,cmp);//對詢問進行排序LL l=1,r=0;ans=0;for(int i=1;i<=m;i++){int ql=q[i].l,qr=q[i].r;while(l<ql) change(l++,-1);while(r>qr) change(r--,-1);while(l>ql) change(--l,1);while(r<qr) change(++r,1);LL a=ans-(qr-ql+1);LL b=(LL)(qr-ql+1)*(qr-ql);LL gcd=GCD(a,b);nume[q[i].id]=a/gcd;deno[q[i].id]=b/gcd;}for(int i=1;i<=m;i++)printf("%lld/%lld\n",nume[i],deno[i]);return 0; }

?

總結

以上是生活随笔為你收集整理的小Z的袜子（BZOJ-2038）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。