zzuli-1728-社交网络 (组合数，期望)

2019-04-15 14:53发布

站内文章 / PIC单片机
11929 0 1523

点击打开链接

题目描述

 

输入

输出

样例输入

2 2 1 0 1 1 0 3 1 0 1 1 1 0 1 1 1 0

样例输出

0.500 1.125


是要求出社交花 数量 的期望。与 >= k个男人有关系的女性是交际花。
思路是：求出每个人 是 社交花的期望，加起来，就是ans。
用一个 pic[][]  存图，pic[i] 是第 i 个人的关系情况。比如：pic[i]  与 m 个人有关系 ，当 m >= k,这个人才有可能是 交际花。
这个人的关系中（包括这个人），性别的总种类数是 2^(m + 1).    ----分母。分子----m个人中有 k 个那人的种类 + m 中有 （k+1）个男人的种类.......+ （k + j）。。。。(k + j) <=n....学到了组合数打表
#include #include #include #include #include using namespace std; int dp[50][50]; void Init() { for(int i = 0;i < 40;i ++) { dp[i][1] = i; dp[i][0] = 1; } for(int i = 2;i < 40;i ++) { for(int j = 2;j <= i;j ++) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } } } int pic[40][40]; int friden_i[40]; //记录与第 i 个人有关系的人数 int main() { int t; cin>>t; Init(); while(t --) { int n,k; double ans = 0; memset(friden_i,0,sizeof(friden_i)); //别忘了每次初始化 cin>>n>>k; //存图 for(int i = 1;i <= n;i ++) { for(int j = 1;j <= n;j ++) { cin>>pic[i][j]; if(pic[i][j]) friden_i[i] ++; } } for(int i = 1;i <= n;i ++) { for(int j = k;j <= n;j ++) { ans += (double)dp[friden_i[i]][j] / pow(2,friden_i[i] + 1); } } printf("%.3lf ",ans); } return 0; }

热门文章