题解：abc392_d Doubles

xyx404 · 2025-02-09 08:33:07 · 题解

思路：

考虑到题目要求我们求的是出现相同数字的概率，所以我们可以使用 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;
}