题目
【问题描述】
小明和小亮在玩一个石子游戏。
刚开始,小明有n堆石子,小亮有m堆石子。且两人每一堆石子所包含的石子个数均不超过6。
现在,小明需要执行d次魔法操作。每次魔法操作会从当前还剩余的几堆石子中随机选择一堆(选择每一堆的概率相同),并从这一堆中去掉一个石子。
如果某一堆经过一次魔法操作后不再有任何石子,那么在下次魔法操作执行时则不会再考虑这一堆。
现在小明想知道,在经过d次魔法操作之后,小亮一堆石子都不剩的概率是多少?
【输入形式】
输入的第一行包含三个整数n,m和d(1 ≤ n, m ≤ 5; 1 ≤ d ≤ 100)。
接下来一行包含n个整数,表示小明每堆石子的初始石子数。
第三行包含m个整数,表示小亮每堆石子的初始石子数。所有石子数都在1到6之间(包括1和6)。
【输出形式】
输出经过d次魔法操作后,小亮一堆石子都不剩的概率。结果保留四位小数。
【样例输入1】
1 2 2 2 1 1
【样例输出1】
0.3333
【样例输入2】
5 5 15 2 2 2 2 3 2 3 3 2 2
【样例输出2】
0.0014
分析
针对这道题,首先想到的可能就是直接DFS,进行深搜,尝试找出所有的情况,算出每一种情况的概率没然后求和。函数设计如下:int cur即现在正在进行第cur次操作,double r即向下传递当前节点情况发生的概率;子节点获取父节点的概率之后,再求出当前子节点的概率。当前节点的概率就等于父亲的概率除以当前节点的兄弟个数,而当前节点的的兄弟个数就等于当前还剩下的非空堆数。
这是理论上可行的做法,但实际上这样的方法是指数级复杂度,经过尝试,大约在d=12左右时就已经没法算出结果了。
用DFS实现这一初步的想法如下:(虽然时间复杂度太高)
#include#include #include using namespace std; const int MAXN = 10; int a[MAXN] = { 0 }; //明 int b[MAXN] = { 0 }; //亮 int cnt_a, cnt_b; //明和亮总石头数 int n, m; //明:n,亮:m int d; vector Vr; int n_sibling; void dfs(int cur, double r) { //新的概率等于上一代的概率处于这一代的兄弟个数,这一代的兄弟个数就等于当前还剩下的非空堆数 double new_r = r * 1.0 / n_sibling; if (cnt_b == 0) { Vr.push_back(r); return; } //两个特判 if (d - (cur - 1) >= cnt_a + cnt_b) { Vr.push_back(r); return; } if (d - (cur - 1) < cnt_b) { return; } //另一种递归出口 if (cur > d && cnt_b != 0) { return; } for (int i = 1; i <= n; i++) { if (a[i] > 0) { a[i]--; cnt_a--; if (a[i] == 0) n_sibling--; dfs(cur + 1, new_r); if (a[i] == 0) n_sibling++; a[i]++; cnt_a++; } } for (int i = 1; i <= m; i++) { if (b[i] > 0) { b[i]--; cnt_b--; if (b[i] == 0) n_sibling--; dfs(cur + 1, new_r); if (b[i] == 0) n_sibling++; b[i]++; cnt_b++; } } } int main() { double ans = 0; cin >> n >> m >> d; for (int i = 1; i <= n; i++) { cin >> a[i]; cnt_a += a[i]; } for (int i = 1; i <= m; i++) { cin >> b[i]; cnt_b += b[i]; } if (d > cnt_b + cnt_a) { ans = 1; cout.setf(ios::fixed); cout << setprecision(4) << ans << endl; return 0; } if (d < cnt_b) { ans = 0; cout.setf(ios::fixed); cout << setprecision(4) << ans << endl; return 0; } n_sibling = n + m; dfs(1, 1.0); for (int i = 0; i < Vr.size(); i++) { ans += Vr[i]; } cout.setf(ios::fixed); cout << setprecision(4) << ans << endl; }
一般利用剪枝法可以简化DFS的计算,但想来想去,似乎这一题不具备普遍的可以剪枝的情况,可以剪掉的一些情况过于稀少,对整体复杂度其实没有什么影响。那DFS真的就不行吗?
算法思路
其实这一题巧就巧在隐藏了一种非常普遍的重复情况,如果发现了就可以剪掉绝大多数的计算。下面介绍这种普遍的重复情况。
设小明,小亮一开始分别为1堆,2堆,石子数分别为2 | 2,1。d=3.那么我们开始进行操作。
有一部分节点没有往下画,可以不用管。关注图中标红的三个框,思考它们是不是同一种情况呢?我们用字符串来表示一个节点,用逗号分割小明和小亮的石子,对于同一个人的石头堆,我们不关心先后顺序,那么这三个情况都可以表示成:"2,01"。然后用哈希表将这些状态和一个概率值对应起来。在后面的代码中,我借鉴了桶排序的思想来存储节点状态,也就是给小明和小亮各设置7个状态位表示0-6个石子,例如str[3]=5即表示石子个数为3的堆有5个。为什么选择桶排序的思想呢,因为这样在生成字符串时,不用对每个人的各堆进行排序,减小了时间复杂度。根据这种方式,那么图中红框的三个情况可以表示为字符串"0010000,1100000"。但是为了直观理解,在解释原理的时候还是采用"2,01"这种表示方式。
那么我们尝试把“2,01”的情况归一:无论从根节点怎样一步一步选择到达“2,10”节点,对于三种“2,01”节点,它们之下的节点一定是相同的,即都是“1,01”和“2,00”。也就是不管出现“2,01”的概率为多少,在“2,01”已经出现的条件下,它的所有子节点的概率都可以归为同一个“2,01”的子节点概率。那么我们就找到了这三个“2,01”的共性,它们终于可以被统一成一种情况了。我们直接把“2,01”与概率1/2对应起来,也就是“2,01”的子节点们中能够出现小亮全为零的情况概率之和。
类似地,我们将“2,11”与概率1/3对应起来。怎么算的呢?也就是对于其子节点(1|21)->0, (2|01)->1/2,(2|10)->1/2,计算概率:(0+1/2+1/2)/3,这里的3就是"2,11"的子节点个数。
可以这么理解:每一个节点有两个任务:一是从它的所有子节点收到子节点的概率,将它们加和,存储为自己的概率值p(生成哈希表);二是把p除以自己兄弟节点的个数并进行回传,也就是p/n_sibling即函数的返回值(回传概率)。通过这种方式,每遍历树的一支,就可以为哈希表添加很多记录。在每次进入新节点时,先从哈希表中寻找有无这个节点的记录,如果有则直接用哈希表中的概率而无需继续向下深搜。这样也就可以剪掉很多“枝”了。
以上是基本原理。代码上还有不少实现时的细节,非常易错。代码如下:
#include#include #include #include using namespace std; const int MAXN = 10; int a[MAXN] = { 0 }; //明 int b[MAXN] = { 0 }; //亮 int cnt_a, cnt_b; //明和亮总石头数 int n, m; //明:n,亮:m int d; unordered_map map; //哈希表 //生成状态压缩字符串 string getList(int seta[], int setb[]) { string tmp = "000000000000000"; for (int i = 0; i <= 6; i++) { char ch1 = seta[i] + 48; char ch2 = setb[i] + 48; tmp[i] = ch1; tmp[i + 8] = ch2; } tmp[7] = ','; return tmp; } double dfs(int cur, int this_sibling) { //记录概率:子树概率之和 //回传概率:子树概率之和/本层兄弟结点个数 int next_sib = 0; //获得状态压缩字符串,并计算子树个数next_sib: int set_a[7] = { 0 }; int set_b[7] = { 0 }; for (int i = 1; i <= n; i++) { set_a[a[i]]++; if (a[i] != 0)next_sib++; } for (int i = 1; i <= m; i++) { set_b[b[i]]++; if (b[i] != 0)next_sib++; } string cur_str = getList(set_a, set_b); //利用哈希表的记录剪枝: bool flag = map.count(cur_str); if (flag) { double rate = map.at(cur_str); return rate/this_sibling; } //递归出口1:找到满足要求的叶子结点 if (cnt_b == 0) { string tmp = cur_str; return 1.0/this_sibling; } //特判剪枝 if (d - cur >= cnt_a + cnt_b) { string tmp = cur_str; return 1.0/this_sibling; } //递归出口2:未找到满足要求的叶子结点 if (cur == d && cnt_b != 0) { string tmp = cur_str; return 0; } //dfs部分:遍历各堆,进入各个子树 double rate = 0; for (int i = 1; i <= n; i++) { if (a[i] > 0) { a[i]--; cnt_a--; rate += dfs(cur + 1, next_sib); a[i]++; cnt_a++; } } for (int i = 1; i <= m; i++) { if (b[i] > 0) { b[i]--; cnt_b--; rate += dfs(cur + 1,next_sib); b[i]++; cnt_b++; } } //记录概率、回传概率 map.insert({ cur_str,rate }); return rate*1.0/this_sibling; } int main() { double ans = 0; cin >> n >> m >> d; for (int i = 1; i <= n; i++) { cin >> a[i]; cnt_a += a[i]; } for (int i = 1; i <= m; i++) { cin >> b[i]; cnt_b += b[i]; } if (d > cnt_b + cnt_a) { ans = 1; cout.setf(ios::fixed); cout << setprecision(4) << ans << endl; return 0; } if (d < cnt_b) { ans = 0; cout.setf(ios::fixed); cout << setprecision(4) << ans << endl; return 0; } ans=dfs(0, 1); cout.setf(ios::fixed); cout << setprecision(4) << ans << endl; return 0; }
总结
总的来说,这道题的难度对我这个菜鸡来说太高!反复推倒重来+打磨代码经过了三天,头发想必掉了不少,呜呜。
有人觉得DP可能也可以做出来,但我尝试了很多次也没能构建出合适的递推数组和状态转移方程。我觉得可能还是DFS+剪枝才是这道题的解法吧。但是这题的剪枝真的非常独特,现在再想起来也觉得很有意思,特此写一篇blog记录一下。