P2612 [ZJOI2012]波浪

    • 125通过
    • 498提交
  • 题目提供者 yyy2015c01 嘤嘤嘤
  • 评测方式 云端评测
  • 标签 Splay 拓扑排序 各省省选 2012 浙江 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 6000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    阿米巴和小强是好朋友。

    阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮,他兴奋地叫个不停。而阿米巴则很淡定,他回想起曾经的那些日子,事业的起伏,情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来,简直什么都不算。

    于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个1到N的排列P[1…N]。定义波动强度等于相邻两项的差的绝对值的和,即:

    L = | P2 – P1 | + | P3 – P2 | + … + | PN – PN-1 | 给你一个N和M,问:随机一个1…N的排列,它的波动强度不小于M的概率有多大?

    答案请保留小数点后K位输出,四舍五入。

    输入输出格式

    输入格式:

    输入文件wavel.in的第一行包含三个整数N, M和K,分别表示排列的长度,波动强度,输出位数。

    输出格式:

    输出文件wavel.out包含一个小数点后K位的实数。

    输入输出样例

    输入样例#1: 复制
    3 3 3
    输出样例#1: 复制
    0.667

    说明

    N = 3的排列有6个:123,132,213,231,312,321;他们的波动强度分别为2,3,3,3,3,2。所以,波动强度不小于3的概率是4/6,即0.667。

    你也可以通过下面的代码来验证这个概率:

    int a[3]={0,1,2},s=0,n=3;
    for (int i=0;i<1000000;i++){
    random_shuffle(a,a+n);
    int t=0;
    for (int j=0;j<n-1;j++) t+=abs(a[j+1]-a[j]); 
    if (t>=3) s++;
    }
    printf("%.3f\n",s/1000000.0);

    【数据规模】 对于30%的数据,N ≤ 10。

    对于另外30%的数据,K ≤ 3。

    对于另外30%的数据,K ≤ 8。

    对于另外10%的数据,N ≤ 50。

    对于100%的数据,N ≤ 100,K ≤ 30,0 ≤ M ≤ 2147483647。

    第 10

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。