P3706 [SDOI2017]硬币游戏

    • 128通过
    • 300提交
  • 题目提供者 ElevenDimensions
  • 评测方式 云端评测
  • 标签 字符串 构造 枚举,暴力 各省省选 2017 山东 Special Judge
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    周末同学们非常无聊,有人提议,咱们扔硬币玩吧,谁扔的硬币正面次数多谁胜利。

    大家纷纷觉得这个游戏非常符合同学们的特色,但只是扔硬币实在是太单调了。

    同学们觉得要加强趣味性,所以要找一个同学扔很多很多次硬币,其他同学记录下正反面情况。

    用H表示正面朝上,用T表示反面朝上,扔很多次硬币后,会得到一个硬币序列。比如HTT表示第一次正面朝上,后两次反面朝上。

    但扔到什么时候停止呢?大家提议,选出n个同学,每个同学猜一个长度为m的序列,当某一个同学猜的序列在硬币序列中出现时,就不再扔硬币了,并且这个同学胜利,为了保证只有一个同学胜利,同学们猜的n个序列两两不同。

    很快,n个同学猜好序列,然后进入了紧张而又刺激的扔硬币环节。你想知道,如果硬币正反面朝上的概率相同,每个同学胜利的概率是多少。

    输入输出格式

    输入格式:

    第一行两个整数n,m。

    接下里n行,每行一个长度为m的字符串,表示第i个同学猜的序列。

    输出格式:

    输出n行,第i行表示第i个同学胜利的概率。选手输出与标准输出的绝对误差不超过10^-6即视为正确。

    输入输出样例

    输入样例#1: 复制
    3 3
    THT
    TTH
    HTT
    输出样例#1: 复制
    0.3333333333
    0.2500000000
    0.4166666667

    说明

    对于10%的数据,$1\le n,m\le 3$

    对于40%的数据,$1\le n,m\le 18$

    另有20%的数据,$n=2$

    对于100%的数据,$1\le n,m\le 300$

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