CUG算法题：魔法操作深藏的剪枝！

CUG上机的一道难题，利用了DFS+剪枝的思想，但是这个剪枝的情况藏得很深，很有意思。

Steve_Jobless

1665人浏览 · 2023-03-08 01:26:15

Steve_Jobless · 2023-03-08 01:26:15 发布

题目

【问题描述】

小明和小亮在玩一个石子游戏。

刚开始，小明有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<iostream>
#include<iomanip>
#include<vector>
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<double>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<iostream>
#include<iomanip>
#include<unordered_map>
#include<string.h>
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<string, double> 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;

}