首页 > ACM题库 > 九度OJ > 九度-1421-Abor[概率计算]
2014
01-16

九度-1421-Abor[概率计算]

题目来自九度:第四届ACM_DIY群程序设计竞赛

题目1421:Abor

题目描述:
As we all known, AbOr has a lots of girls in a palace called “Hou” (About 30 millions).Now you are given n people without knowing their gender(Male and Female are equally likely for anyone). You also know the relationship between them! You want to know what is the expecting number of “abor” that could be found , where “abor” is defined as:(1) Only Male might be considered;(2) The Male who has at least m Females friends is called “abor”.

输入:
        The first line is one integer T indicates the number of the test cases. (T <= 10000)Then for every case, the first line has only two integers n and m, indicating the number of people and the value of m.(0≤m≤n≤20)Then one n by n symmetric matrix A, where A[i][j] is 1 if j is a friend of i(vice versa) and 0 otherwise;(A[i][i] is always 0)
输出:
        Output the expecting number of “abor” in the given case. The answer must round to two digital after the decimal point.
样例输入:
3
2 1
01
10
2 0
01
10
3 2
011
101
110
样例输出:
0.50
1.00
0.38

分析:

男女出现的概率是相同的。只有男生才能叫做abor

以第三个例子:

011
101
110

3个人期望值是相同的都为 0.5 * 0.5 * 0.5 ,结果即为 0.5 * 0.5 * 0.5 * 3 = 0.38

对于任意的n,需要分别计算再相加。

#include<cstdio>
#include<cstring>
#include<cmath>
char ch[30];
long double po[30];
long long C(int a,int b)
{
    long long u=1,d=1; 
    if(b-a<a)
    a = b-a;
    int bb = b,aa = a;
    for(int i=0;i<a;i++)
    {
        u*=bb--;
        d*=aa--;
        //aa--;
        //bb--;
    }
    long long sum = u/d;
    return sum;
}
void Init()
{
    po[0] = 1.0;
    for(int i=1;i<=21;i++)
    po[i] = po[i-1]*0.5;
}    
int main()
{
    int t,j;
    Init();
    scanf("%d",&t);
    while(t--)
    {
        int n,m,f;
        long double p = 0.0;
        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++)
        {
            f = 0;
            scanf("%s",ch);
            for( j=0;j<n;j++)
                if(ch[j]=='1')
                    f++;    
                if(f<m)
                    continue;

                for(j=m;j<=f;j++)
                    p+=C(j,f)*po[f+1];
        }
        if(m==0)
        {
            printf("1.00\n");
            continue;
        }
        if(m==n)
        {
            printf("0.00\n");
            continue;
        }
        printf("%0.2lf\n",(double)p);

    }
    return 0;
}
/**************************************************************
    Problem: 1421
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:10 ms
    Memory:1020 kb
****************************************************************/

  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }