【洛谷4581】[BJOI2014] 想法（随机算法）

点此看题面

• 给定(n,m)和(a_i,b_i)，定义(S_i=egin{cases}{i}&1le ile m,\S_{a_i}cup S_{b_i}&m<ile nend{cases})。
• 对所有(iin(m,n])求(|S_i|)，要求只要有(95\%)的答案满足与正确答案误差不超过(25\%)即可。
• (mle10^5,nle10^6)

(MinHash)算法

这道题想了半天没思路，一看题解发现这做法有点眼熟，然后突然记忆复苏，想起去年WC讲课的时候提到过一个叫(MinHash)算法的玩意，似乎是专门用来估算集合大小的。

我们给(1sim m)的每个数随机一个([1,S])的点权，对于每个集合(s_i)我们维护出其中前(K)小的点权。

对于第(K)小的点权(s_{i,k})，根据概率公式有：

[frac K{|s_i|}=frac{s_{i,k}}S ]

也就是说：

[|s_i|=frac{K imes S}{s_{i,k}} ]

只要随机(T)次给算出的答案取个平均值就好了。

代码：(O(nTK))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000000
#define K 50
#define S 456789001
using namespace std;
int n,m,a[N+5],b[N+5],c[N+5],s[N+5][K+5];double ans[N+5];
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('
');}
}using namespace FastIO;
int main()
{
	RI i;for(read(n,m),i=m+1;i<=n;++i) read(a[i],b[i]);
	for(RI T=1;T<=5;++T)//随机T次
	{
		for(i=1;i<=m;++i) s[i][c[i]=1]=1ull*rand()*rand()*rand()*rand()%S+1;//随机一个[1,S]的点权
		for(i=m+1;i<=n;++i)
		{
			RI c1=c[a[i]],c2=c[b[i]],c3=0;RI *s1=s[a[i]],*s2=s[b[i]],*s3=s[i];
			RI p=1,q=1;W(p<=c1&&q<=c2&&c3<=K) s1[p]==s2[q]?++q:s3[++c3]=s1[p]<s2[q]?s1[p++]:s2[q++];//归并，注意去重
			W(p<=c1&&c3<=K) s3[++c3]=s1[p++];W(q<=c2&&c3<=K) s3[++c3]=s2[q++];
			ans[i]+=(c[i]=c3)<K?c[i]:1.0*K*S/s[i][K];//若个数达到k个就根据概率公式计算，否则直接记录
		}
	}
	for(i=m+1;i<=n;++i) printf("%d
",(int)(ans[i]/5));return 0;//取平均值
}