D - Doubles Atcoder abc392

题意

有 $n$ 个骰子，骰子有不同的骰面数量，骰面数值

问任选两个骰子投出相同数字的最大概率
数据范围：

$2<=n<=100$

$所有骰子的面数<=10^5$

$每个骰子面数>=1$

$骰面数值<=10^5$

一眼 $\color{purple}{概率}$

$\color{red}{举个栗子：}$ ----(概率)

第一个骰子有四面，第二个有5面

1 1 2 2----第一个

1 2 3 4 5----第二个

第一个骰子投出 $1$ 的概率为 $\frac{2}{4}=\frac{1}2=0.5$

投出 $2$ 的概率为 $\frac{2}{4}=\frac{1}2=0.5$

第二个骰子投出 $1$ 的概率为 $\frac{1}{5}=0.2$

投出 $2$ 的概率为 $\frac{1}{5}=0.2$

那么两个骰子一起投出 $1$ 的概率就是 $0.5*0.2=0.1$

两个骰子一起投出 $2$ 的概率就是 $0.5*0.2=0.1$

两个骰子投出相同数字的概率就是 $0.1+0.1=0.2$

$P(投出数字一样)+=P(一起投出x)$

$P(一起投出x)=P(一投出x)*P(二投出x)$

$P(一投出x)=\frac{x的数量}{总面数}=\frac{1}{总面数}*x(x个相加)$

4.贴代码吧

定义p[i][j]为第 $i$ 个个骰子投出 $j$ 的概率

siz[i]为第 $i$ 个骰子有多少面

val[i][j]表示第 $i$ 个骰子第 $j$ 面的数值

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=4e5+110;
const int N=1e2+10;
double P[N][M],m,n,siz[M],top=0,maxx=-1;
int val[N][M];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>siz[i];
		for(int j=1;j<=siz[i];j++){
			cin>>val[i][j];
           //分配律
			P[i][val[i][j]]+=(1/siz[i]);
		}
	}
	for(int i1=1;i1<=n;i1++){//枚举骰子
		for(int i2=i1+1;i2<=n;i2++){
			double ans=0;
			bool vis[M];
			memset(vis,0,sizeof(vis));
			for(int j=1;j<=siz[i1];j++)
				if(!vis[val[i1][j]])
					vis[val[i1][j]]=1,
					ans+=P[i1][val[i1][j]]*P[i2][val[i1][j]];
			maxx=max(maxx,ans);
		}
	}
	printf("%.15lf\n",maxx);
}
/*
3
5 1 1 1 1 1
4 2 2 2 2
3 1 1 2
*/