翻牌游戏

NC24904. 翻牌游戏

描述

胡老师最近迷上了一款经典小游戏——翻牌。

桌面上有n个互不相同的对子组成的2n张扑克牌，背面朝上放在桌面上。

每一轮，胡老师会选择两张不同的牌翻开，如果这两张牌相同，则将它们消除；如果不同，则将它们盖回去。需要注意的是：胡老师总是先选择两张牌，再同时将它们翻开。

胡老师有个外号叫人形AI，他拥有超强的记忆力，所以他可以记住任何他曾经翻开过的牌的位置。
他现在想知道，在这种情况下，消除所有牌需要的最少期望轮数是多少。

输入描述

第一行是一个整数，表示数据组数。

接下来T行，每行仅包含一个正整数，表示一共有n个对子（即2n张扑克牌）。

输出描述

输出共T行。

对每组数据，输出一行一个恰有两位小数的浮点数，表示消除所有牌所需最少期望轮数精确到小数点后两位的结果。

示例1

输入:

1
2

输出:

3.00

说明:

以下叙述n=2时的最优策略。

1. 随机选择两张扑克牌。有 $\dfrac{1}{3}$ 概率两张牌相同，直接消除，跳至(4)；有 $\dfrac{2}{3}$ 概率不同，跳至(2)。
2. 选择一张已经选过的扑克牌，和一张没有选过的扑克牌。有 $\dfrac{1}{2}$ 的概率相同，直接消除，跳至(4)；有 $\dfrac{1}{2}$ 的概率不同，跳至(3)。
3. 这时已经知道所有扑克牌的图案，选择一个对子消除，跳至(4)。

4. 消除最后两张扑克牌。

数学期望为： $E = \dfrac{1}{3} \times 2 + \dfrac{1}{3} \times 3 + \dfrac{1}{3} \times 4 = 3.00$ 。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 2808K, 提交时间: 2019-04-13 19:22:24

#include <iostream>
using namespace std;
int main()
{
    int T,n; scanf("%d",&T); while (T--){scanf("%d",&n); printf("%d.00\n",2*n-1);}
return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 179ms, 内存消耗: 2772K, 提交时间: 2019-04-15 13:30:53

#include <cstdio>
int main() {int t; double n;scanf("%d", &t);while(t--){scanf("%lf", &n); printf("%.2lf\n", 2*n-1);}return 0;}

上一题

下一题

详情