题解：AT_abc392_d [ABC392D] Doubles

xyx4042025-02-092025-02-19

思路：

考虑到题目要求我们求的是出现相同数字的概率，所以我们可以使用 unordered_map 把每一个骰子中出现的数字的数量存下来。

然后进行循环枚举我们使用的两个骰子，注意到使用编号为 $1$ 和 $2$ 的骰子和使用编号为 $2$ 和 $1$ 的骰子的出现相同数字的概率其实是一样的，所以我们枚举使用骰子的时候可以通过让第二个骰子的编号 $j$ 大于我们第一个骰子的编号 $i$ 来减少循环。

在枚举两个 unordered_map 中是否有相同的数时，也可以进行优化，我们可以枚举 unordered_map 中数字少的 unordered_map 中的数字，判断另外一个有没有相同的数字。

注意要开 long long。
浮点数用 double 就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn LL
#define ull unsigned long long
LL n,k[110];
vector<unordered_map<LL,LL> >a(1);
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	cin>>n;
	for(LL i=1;i<=n;i++){
		cin>>k[i];
		unordered_map<LL,LL>temp;
		for(LL j=1;j<=k[i];j++){
			LL x;cin>>x;
			temp[x]++;
		}
		a.push_back(temp);
	}
	double ans=0.0;
	for(LL i=1;i<=n;i++){
		for(LL j=i+1;j<=n;j++){
			auto mp1=a[i],mp2=a[j];
			long long sum=0;
			if(mp1.size()<=mp2.size()){
				for(auto x:mp1){
					auto it=mp2.find(x.first);
					if(it!=mp2.end()){
						sum+=x.second*it->second;
					}
				}
			}
			else{
				for(auto x:mp2){
					auto it=mp1.find(x.first);
					if(it!=mp1.end()){
						sum+=x.second*it->second;
					}
				}
			}
			double tamp=((double)(sum))/(k[i]*k[j]);
			if(tamp>ans)ans=tamp;
		}
	}
	cout<<fixed<<setprecision(15)<<ans;
	return 0;
}