程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj2038【2009國家集訓隊】小Z的襪子(hose)

bzoj2038【2009國家集訓隊】小Z的襪子(hose)

編輯:關於C++

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

這道題方法是莫隊算法,一種用於處理不帶修改的區間查詢問題的離線算法。

如果我們已知[l,r]的答案,並且左(右)端點移動一個單位後的答案能在O(1)時間內求得,就可以使用莫隊算法。時間復雜度為O(n^1.5)。

對於這道題而言,我們用s[1]表示當前區間每種顏色襪子的個數,t表示當前區間襪子的總數。

則最終答案ans=∑(s[i]*(s[i]-1))/(t*(t-1))=(∑(s[i]^2-)-∑(s[i]))/(t^2-t)=(∑(s[i]^2)-t)/(t^2-t)。

這樣我們只需要維護s數組和s[i]的平方和,就可以O(1)時間內進行轉移了。

莫隊算法其實就是一種暴力算法,只是與普通暴力算法不同,它將不同的詢問進行了合理的排序,從而最小化了操作次數。

那如何排序才是最合理的呢?

我們將整個大區間分塊,分成sqrt(n)塊,每塊sqrt(n)個數。再將所有詢問排序,以左端點所在塊為第一關鍵字,以右端點為第二關鍵字。排序之後計算每個區間答案,區間端點移動就暴力計算新的答案。

以下是時間復雜度的分析:

左端點所在塊最多sqrt(n)種情況,而同一個塊內右端點最多移動n的范圍,所以右端點移動的總復雜度為O(n^1.5)。左端點每次移動范圍為O(sqrt(n)),一共移動n次,所以左端點移動復雜度也為O(n^1.5)。加起來總復雜度為O(n^1.5)。

這樣,這道題就可以完美解決了。

這裡有一個關於曼哈頓距離最小生成樹和莫隊算法的鏈接:

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 50005
using namespace std;
int n,m;
int pos[maxn],c[maxn];
ll s[maxn],sum;
struct data{int l,r,id;ll x,y;}a[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline bool cmp(data a,data b)
{
	return pos[a.l]==pos[b.l]?a.ra[i].r;r--) update(r,-1);
		for(;la[i].l;l--) update(l-1,1);
		if (a[i].l==a[i].r)
		{
			a[i].x=0;a[i].y=1;
			continue;
		}
		a[i].x=sum-(a[i].r-a[i].l+1);
		a[i].y=(ll)(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
		ll tmp=gcd(a[i].y,a[i].x);
		a[i].x/=tmp;a[i].y/=tmp;
	}
	sort(a+1,a+m+1,cmpid);
	F(i,1,m) printf("%lld/%lld\n",a[i].x,a[i].y);
	return 0;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved