骰子游戏(2023睿抗省赛)

骰子游戏

题目描述:

在某个游戏中有一个骰子游戏。

在游戏中，你需要投掷 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并不比当前的获胜等级更好。

输入格式

输入第一行是一个正整数 TT，表示接下来有多少组数据。

每组数据只有一行 5 个数字，表示第一次投出的 5个骰子的点数。

输出格式

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

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

数据范围

$$1\le T\le 10$$

输入样例：

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

输出样例：

3 4 9
3 13 18
2 4 9

思路:

1. 枚举所有 2^5 子集：选择哪些骰子重投。
2. 对每个子集，暴力枚举 6^k 种可能的重投结果（dfs），计算严格优于当前等级的次数 win。
3. 记录并更新 最大概率 以及对应的最小重投骰子数 k。
4. 最后将 win/6^k 化简为最简分数输出。

枚举“要重投的骰子子集”
用一个 5 位二进制掩码 mask，从 0 到 31 共 32 种可能。掩码的第 i 位是 1 就表示“第 i 个骰子要重投”，否则保留原值。

模拟重投结果
对于选中要重投的那 k 个骰子，共有 6^k 种可能的新点数组合。我们用一次深度优先搜索（DFS）把所有可能枚举出来，统计其中“等级 > 原等级”的次数 win。

计算概率并挑最优

• 这 win 次成功中，“赢”的概率就是 win / 6^k。
• 在所有 32 种 mask 中，挑出概率最大的一个；若有并列，就挑 k（重投骰子个数）最小的。

化简分数输出
最后把分子 win、分母 6^k 作最大公约数约分，输出最简分数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;// Rank levels
// 0: nothing
// 1: one pair
// 2: two pair
// 3: three of a kind
// 4: 5-high straight (1-5)
// 5: 6-high straight (2-6)
// 6: full house
// 7: four of a kind
// 8: five of a kind
//给定序列返回等级.
int rank_of(const array<int,5> &dice) {int cnt[7]={0};for(int x:dice) cnt[x]++;vector<int> freqs;for(int v=1;v<=6;v++) if(cnt[v]>0) freqs.push_back(cnt[v]);sort(freqs.begin(), freqs.end(), greater<int>());// fiveif(freqs[0]==5) return 8;// fourif(freqs[0]==4) return 7;// full houseif(freqs[0]==3 && freqs.size()==2 && freqs[1]==2) return 6;// straights// check 2-6bool ok=true;for(int v=2;v<=6;v++) if(cnt[v]!=1) ok=false;if(ok) return 5;ok=true;for(int v=1;v<=5;v++) if(cnt[v]!=1) ok=false;if(ok) return 4;// threeif(freqs[0]==3) return 3;// two pairif(freqs[0]==2 && freqs.size()==3 && freqs[1]==2) return 2;// one pairif(freqs[0]==2) return 1;return 0;
}// gcd
ll gcdll(ll a, ll b){ return b?gcdll(b,a%b):a; }int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){array<int,5> init;for(int i=0;i<5;i++) cin>>init[i];int cur_rank = rank_of(init);double best_prob = -1;int best_k = 0;ll best_num=0, best_den=1;for(int mask=0;mask<32;mask++){//mask使用二进制表示,其中位为1的表示这个位要重新骰.要遍历32次哦vector<int> idx;//idx存储要骰的是第几个骰子.(取值表示下标:1-5)for(int i=0;i<5;i++) if(mask & (1<<i)) idx.push_back(i);//放的i!!!int k = idx.size();//要重新骰的数量ll total = 1;//一共会有多少种可能.for(int i=0;i<k;i++) total *= 6;ll win = 0;//这些可能中,会有多少比原来的等级严格高array<int,5> dice = init;//dice记录原来的骰子情况,在搜索时要修改function<void(int)> dfs = [&](int pos){if(pos==k){// 如果搜索到要骰的最后一个位置就要判断,相当于index==n时结束递归int r = rank_of(dice);if(r > cur_rank) win++;return;}//如果还没有到头就开始遍历这个位置上的数字.从1-6int i = idx[pos];//第i个位置要重新骰for(int d=1;d<=6;d++){dice[i]=d;dfs(pos+1);//这个位置已经重置完成了,继续遍历下一个位置.}};dfs(0);// 计算比原来好的可能性double prob = (double)win / (double)total;if(prob > best_prob + 1e-15 ||(abs(prob - best_prob)<1e-15 && k < best_k)) {best_prob = prob;best_k = k;best_num = win;//分子best_den = total;//分母}}// 化简if(best_num==0) best_den=1;else {ll g = gcdll(best_num, best_den);best_num/=g; best_den/=g;}cout<<best_k<<" "<<best_num<<" "<<best_den<<"\n";}return 0;
}

这个题目怎么说呢,根据那个给出的$T$的范围,可以估计一下会使用暴力搜索,所以估计的复杂度为:
$$C_5^1\ast 6+C_5^2\ast 6^2+.....+C_5^4\ast 6^4+C_5^5\ast 6^5\approx \text{1}0,251$$
$102510<10^8$基本可以在一秒以内跑完的

这个题当做感叹吧!!!