/*
 
2013腾讯马拉松初赛第0场
 
1004 湫湫系列故事——植树节
 
Time Limit: 0.5 Seconds   Memory Limit: 32768K
 
 
今天是一年一度的植树节，腾讯幼儿园要求每个老师在班里选出几个小朋友一起去野外种植小树苗，根据学校的整体安排，湫湫老师的班里要选出3个小朋友。
        已知湫湫的班里共有n个孩子，每个孩子有Bi个朋友(i从1到n)，且朋友关系是相互的，如果a小朋友和b小朋友是朋友，那么b小朋友和a小朋友也一定是好朋友。为了选择的公平性，湫湫老师会随机抽取3个小朋友出来(每个人被抽到的概率相同)，但是她很希望这3个小朋友之间的关系完全相同，湫湫老师想请你帮她算算抽到的3个小朋友正好关系相同的概率是多少？
PS. 关系相同就是指要么3个人互相是好朋友，要么3个人互相都不是好朋友。
 
Input
 
输入数据第一行是一个整数T(1<=T<=1000)，表示输入数据的组数；
每组数据的第一行是一正整数n表示孩子的总数(2<n<=1000)，第二行有n个数Bi (i从1到n)，分别代表每个小朋友的朋友的个数。
 
Output
对于每组数据，请输出抽到的3个小朋友关系相同的概率，结果保留3位小数。
 
Sample Input
1
5
3 3 3 3 4
 
Sample Output
0.400
 
*/
 
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
 
using namespace std;
int a[1005];
int main()
{
    int T;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ans=0;
        int tol=n*(n-1)*(n-2)/6;
        for(int i=0;i<n;i++)ans+=a[i]*(n-a[i]-1);
        ans/=2;
        ans=tol-ans;
        printf("%.3lf\n",(double)ans/tol);
 
 
    }
    return 0;
}

回复 "ACM题目：湫湫系列故事——植树节"

这儿你可以回复上面这条便签

作者你的名字是？

标题给你的便签一个标题。

语言你的便签是以

你的便签在这儿输入便签内容

2013腾讯马拉松初赛第0场

1004 湫湫系列故事——植树节
 
Time Limit: 0.5 Seconds   Memory Limit: 32768K

今天是一年一度的植树节，腾讯幼儿园要求每个老师在班里选出几个小朋友一起去野外种植小树苗，根据学校的整体安排，湫湫老师的班里要选出3个小朋友。
	已知湫湫的班里共有n个孩子，每个孩子有Bi个朋友(i从1到n)，且朋友关系是相互的，如果a小朋友和b小朋友是朋友，那么b小朋友和a小朋友也一定是好朋友。为了选择的公平性，湫湫老师会随机抽取3个小朋友出来(每个人被抽到的概率相同)，但是她很希望这3个小朋友之间的关系完全相同，湫湫老师想请你帮她算算抽到的3个小朋友正好关系相同的概率是多少？
PS. 关系相同就是指要么3个人互相是好朋友，要么3个人互相都不是好朋友。

Input

输入数据第一行是一个整数T(1<=T<=1000)，表示输入数据的组数；
每组数据的第一行是一正整数n表示孩子的总数(2<n<=1000)，第二行有n个数Bi (i从1到n)，分别代表每个小朋友的朋友的个数。

Output
对于每组数据，请输出抽到的3个小朋友关系相同的概率，结果保留3位小数。

Sample Input
1
5
3 3 3 3 4

Sample Output
0.400

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>

using namespace std;
int a[1005];
int main()
{
    int T;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ans=0;
        int tol=n*(n-1)*(n-2)/6;
        for(int i=0;i<n;i++)ans+=a[i]*(n-a[i]-1);
        ans/=2;
        ans=tol-ans;
        printf("%.3lf\n",(double)ans/tol);

}
    return 0;
}

创建短链接创建一个较短的URL，连接到这个便签

私人私人便签不会显示在最近列表中

保存期限我们应该什么时候删除这张便签？

防滥用键入这些字符

Code666 (代码贴、代码片段)

[C] ACM题目：湫湫系列故事——植树节 →→→→→进入此内容的聊天室

回复 "ACM题目：湫湫系列故事——植树节"