RC-u3 骰子游戏（raicom睿抗机器人CAIP编程技能赛）_睿抗编程赛练习

RC-u3 骰子游戏

题目描述

在某个游戏中有一个骰子游戏。在游戏中，你需要投掷 5 个标准六面骰子（骰子为一个正方体，6 个面上分别有1、2、3、4、5、6中的一个数字，骰子的质量均匀），投出的点数根据组合会获得一个“获胜等级”。获胜等级从高到低如下：

• 五个同点数 - 五个骰子显示相同的点数
• 四个同点数 - 四个骰子显示相同的点数
• 葫芦 - 一对和一个三个同点数（如1、1、3、3、3）
• 六高顺子 - 投出的点数为 2、3、4、5、6
• 五高顺子 - 投出的点数为 1、2、3、4、5
• 三个同点数 - 三个骰子显示相同的点数（如1、1、1、2、3）
• 两对 - 投出的点数中有两对是相同的（如 1、1、2、2、3）
• 一对 - 投出的点数有一对是相同的（如 1、1、2、3、4）
• 无 - 除去以上的其他情况

给定你已经投出的一次结果，现在假设你可以选择任意个骰子重投一次，请问怎么样操作，才能最大化在重骰后获得更好的获胜等级的概率呢？

注意：更好的获胜等级需要严格地比当前的获胜等级更好，例如 1、1、2、2、3 如果重骰后变为 1、1、3、3、4 并不比当前的获胜等级更好。

输入格式:
输入第一行是一个正整数 T (1≤T≤10)，表示接下来有多少组数据。
每组数据只有一行 5 个数字，表示第一次投出的 5 个骰子的点数。

输出格式:
对于每组数据输出三个整数，其中第一个整数为为了获得最大的概率需要重新骰几个骰子，后面的两个整数为重骰骰子后概率的最简分数，其中第二个整数为分子，第三个整数为分母。如果分子为 0，分母为 1。

如果有多种获得最大概率的情况，取重骰的骰子数最少的方案。

输入样例:

3
1 1 2 2 3
1 1 2 3 4
1 1 1 2 3
1
2
3
4

输出样例:

3 4 9
3 13 18
2 4 9
1
2
3

样例说明:
样例的第一组数据中，一种方案是：重骰最后三个骰子以获得最大的概率（只要重骰的有一个“1”或者三个均相等即可）。

题目解析

这个骰子游戏问题是一个概率与策略问题。玩家需要决定在给定的情况下，重新投掷多少个骰子可以最大化获得更高获胜等级的概率。题目给出了获胜等级的排序，从最好的"五个同点数"到最差的"无"。

输入格式描述了将要处理的数据组数T，以及每组数据的五个骰子点数。

输出格式要求输出三个整数：

1. 需要重骰的骰子数量。
2. 重骰后获得更好获胜等级的概率的分子。
3. 重骰后获得更好获胜等级的概率的分母。

样例说明给出了具体的数据样例及其对应的输出解释。样例的输出是基于最优策略来计算获得更好获胜等级概率的。

例如第一个样例1 1 2 2 3，目前的获胜等级是“两对”。为了最大化获得更高等级的概率，玩家可以选择重骰后三个骰子（2, 2和3），因为假如这三个骰子中有一个是1，就能形成“三个同点数”，取得更高的等级。而如果三个骰子都是相同的点数，则可以形成“葫芦”或者“四个同点数”，这也是一个更高的等级。

输出结果3 4 9意味着：

• 玩家需要重骰3个骰子。
• 获得更好获胜等级的概率为4/9，即有4种情况会使得等级提高，总共9种可能的情况（因为一个骰子有6面，重骰三个就是(6^3 = 216)种可能，但是分子和分母已经被约分了）。

分析这个问题通常需要考虑当前的点数组合，计算不同选择下提升获胜等级的概率，并比较哪种方案的概率更高。同时，如果多个方案有相同的最大概率，则选择重骰骰子数最少的方案。

模拟

这段代码是一个用来解决特定骰子游戏问题的程序。现在我将逐行对其进行详细注释，以便你更好地理解其工作原理。

// 包含C++标准库，用于各种通用功能，如输入输出和排序
#include<bits/stdc++.h>
using namespace std;

// 全局变量声明
int n,k[6],level1,level2,t[6],f[32],r[32];

// 函数get_level：根据五个骰子的点数，返回当前获胜等级
int get_level(int s[])
{
    // 首先对骰子点数进行排序，以便于后续判断
    sort(s+1,s+1+5);
    // 下面的条件判断对应于题目中给出的获胜等级判断逻辑
    // 注意数组是从1开始索引的，符合题目输入习惯
    if(s[1]==s[2]&&s[2]==s[3]&&s[3]==s[4]&&s[4]==s[5])
        return 9; // 五个同点数
    if(s[1]==s[2]&&s[2]==s[3]&&s[3]==s[4]||s[2]==s[3]&&s[3]==s[4]&&s[4]==s[5])
        return 8; // 四个同点数
    if(s[1]==s[2]&&s[2]!=s[3]&&s[3]==s[4]&&s[4]==s[5]||s[1]==s[2]&&s[2]==s[3]&&s[3]!=s[4]&&s[4]==s[5])
        return 7; // 葫芦
    if(s[1]==2&&s[2]==3&&s[3]==4&&s[4]==5&&s[5]==6)
        return 6; // 六高顺子
    if(s[1]==1&&s[2]==2&&s[3]==3&&s[4]==4&&s[5]==5)
        return 5; // 五高顺子
    if(s[1]==s[2]&&s[2]==s[3]||s[2]&&s[2]==s[3]&&s[3]==s[4]||s[3]==s[4]&&s[4]==s[5])
        return 4; // 三个同点数
    if(s[1]==s[2]&&s[3]==s[4]||s[1]==s[2]&&s[4]==s[5]||s[2]==s[3]&&s[4]==s[5])
        return 3; // 两对
    for(int i=2;i<=5;i++)
        if(s[i]==s[i-1])
            return 2; // 一对
    return 1; // 无
}

// 函数get_1：计算一个整数的二进制表示中1的个数
int get_1(int a)
{
    int sum=0;
    while(a)
    {
        if(a%2==1) sum++;
        a/=2;
    }
    return sum;
}

// 主函数
int main()
{
    // 读入测试数据组数
    cin>>n;
    while(n--)
    {
        // 读入每组数据，即五个骰子的点数
        for(int i=1;i<=5;i++)
            cin>>k[i];
        // 获取初始获胜等级
        level1=get_level(k);
        // 初始化数组f和r
        memset(f,0,sizeof f);
        memset(r,0,sizeof r);
        // 初始化结果变量
        int res=0;
        int zi=0;
        int mu=1;
        double gv=-1;
        // 遍历所有可能的骰子点数组合
        for(int a=1;a<=6;a++)
            for(int b=1;b<=6;b++)
                for(int c=1;c<=6;c++)
                    for(int d=1;d<=6;d++)
                        for(int e=1;e<=6;e++)
                        {
                            // 计算每种点数组合
                            t[1]=a,t[2]=b,t[3]=c,t[4]=d,t[5]=e;
                            int cnt=0;
                            // 标记与原点数不同的骰子位置
                            for(int i=1;i<=5;i++)
                                if(k[i]!=t[i])
                                    cnt|=1<<(i-1);
                            // 计算所有包含该点数变化的组合，并更新频次和成功次数
                            for(int i=1;i<=31;i++)
                                if((i&cnt)==cnt)
                                {
                                    f[i]++;
                                    level2=get_level(t);
                                    if(level2>level1)
                                        r[i]++;
                                }
                        }
        // 寻找使得获胜等级提高的最佳操作方案
        for(int i=1;i<=31;i++)
        {
            if(r[i]==0) continue;
            double g=(double)r[i]/f[i];
            int c=get_1(i);
            // 如果发现更好的操作方案，则更新结果变量
            if(g>gv||(g==gv&&c<res))
                gv=g,res=c,zi=r[i],mu=f[i];
        }
        // 简化结果分数
        if(zi>0&&mu>0)
        {
            int z=__gcd(zi,mu);
            zi/=z;
            mu/=z;
        }
        // 输出结果
        printf("%d %d %d\n",res,zi,mu);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

这段代码的核心功能是模拟所有可能的重投方案，计算每种方案提高获胜等级的概率，并找到重投骰子数最少且提高概率最大的方案。通过遍历、统计、并比较不同重投策略后的获胜等级，来确定最终的最优重投策略。