骰子游戲

題目描述:

在某個游戲中有一個骰子游戲。

在游戲中，你需要投擲 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?6+C_5^2?6^2+.....+C_5^4?6^4+C_5^5?6^5\approx \text{1}0,251$$
$102510<10^8$基本可以在一秒以內跑完的

這個題當做感嘆吧!!!