AT_abc392_d 题解

getchar_unlocked · 2025-02-09 21:42:37 · 题解

题目传送门

思路

可以使用枚举解决此题。

先将每一个骰子记在 C 中，其中 C_{i,j} 代表第 i 个骰子的第 j 面所代表的数字。

然后枚举每一对骰子，i 枚举从 1 到 N，j 从 i+1 枚举到 N（需保证 i\ne j）。对于每一对骰子，枚举其可能的数字 x，从 1 到 10^5（或者 \max\{A_{i,j}\}）。只要满足两个筛子都有面，即 C_{i,x} 和 C_{j,x} 都有数字，就将该骰子的概率之积加入总和 S，即 S\gets S+\frac{C_{i,x}}{K_i}\times\frac{C_{j,x}}{K_j}。

最终将所有的概率和 S 取最大值输出即可。

时间复杂度 \mathcal{O}(N^2\times\max\{A_{i,j}\})，大概在 10^9 级别。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,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;}
const int N=105,E=1e5;
vector<int>vc[N];
int k[N],cnt[N][E+10];
signed main(){
    int n=read();
    for(int i=0;i<n;++i){
        k[i]=read();
        for(int j=0;j<k[i];++j){
            int x=read();
            vc[i].push_back(x);
            ++cnt[i][x];
        }
    }
    double ans=0;
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j){
            double sum=0;
            for(int x=1;x<=E;++x)
                if(cnt[i][x]>0&&cnt[j][x]>0)
                    sum+=cnt[i][x]*1.0/k[i]*cnt[j][x]/k[j];
            ans=max(ans,sum);
        }
    printf("%.12lf\n",ans);
    return 0;
}