代码注释

// UVa1354 Mobile Computing
// Rujia Liu
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

struct Tree {
    double L, R;  // distance from the root to the leftmost/rightmost point
    Tree() : L(0), R(0) {}
};

const int maxn = 6;

int n, vis[1 << maxn];
double r, w[maxn], sum[1 << maxn];
vector<Tree> tree[1 << maxn];

int mycnt = 0;

void dfs(int subset) {
    // cout << ++mycnt << ". subset => " << subset << '\\n';
    if (vis[subset]) return;
    vis[subset] = true;

    bool have_children = false;
    // 遍历 left，从 6 到 1，这里是假设 n 为 3，然后 root 是 2^3 - 1 = 7，也就是说，
    // 第一次传入的 subset 为 7
    // 然后，这里的 left 就是从 6 一直递减到 1 了，不对，这里还需要重新思量一下，并不是这个样子的！步长不是都是 1 的
    // 不错，这里的循环的作用就是以一种递减的顺序遍历 subset 的子集
    for (int left = (subset - 1) & subset; left; left = (left - 1) & subset) {
        have_children = true;
        // 求补集，因为是使用了位标记，所以，left 这个数字中取 1 的二进制位的砝码是都被
        // 左边取了的，然后用 subset 的 left 进行取补运算之后，就是天平右边该有的标记
        // 了
        int right = subset ^ left;             // 求补集
        double d1 = sum[right] / sum[subset];  // 右边的距离
        double d2 = sum[left] / sum[subset];   // 左边的距离

        // 递归到最里层是什么地方呢？
        // 其实就是 left 为 1 的时候，如果 left 为 1，那么进入这个 dfs 之后，
        // subset 就为 1，然后相应的 left 就为 0，就直接不会进入这个循环里面来，
        // 然后就直接走出这个循环了，下接本函数最后一行的注释
        // 然后，理解的顺序就来到了 left 的上一层，left 为 2 的时候，而，如果 subset 为 2 的话，那么，其对应的 left 和 right 必然都是
        // 1，那么，这个循环就可以继续往下走了
        // cout << "left => " << left << '\\n';  // left 到 2 的时候，这里的 dfs(left) 方可以跨过去 10 & 01 = 00
        dfs(left);
        // cout << "left => " << left << '\\n';
        dfs(right);

        // 第一次走到这里的时候，tree[left].size() 和 tree[right].size() 必然都是 1
        // cout << "subset => " << subset << " " << bitset<3>(subset) << " left => " << left << " " << bitset<3>(left) << " right => " << right << " "
        //      << bitset<3>(right) << " tree[left].size() => " << tree[left].size() << " tree[right].size() => " << tree[right].size() << endl;
        for (int i = 0; i < tree[left].size(); i++)
            for (int j = 0; j < tree[right].size(); j++) {
                Tree t;
                t.L = max(tree[left][i].L + d1,
                          tree[right][j].L - d2);  // 以 right 为根结点的树，如果其有一种情况的左子树的左端的长度比 d2 还要长的话，那么，就取这个为左端点
                t.R = max(tree[right][j].R + d2, tree[left][i].R - d1);  // 同理
                if (t.L + t.R < r) tree[subset].push_back(t);  // 符合条件就加进去，这是以 subset 为根结点的所有的左右子树的排布情况中符合条件的部分
            }
    }

    // 此处接 dfs(left) 上面的注释：在 subset 为 1 的时候，会 push 进去一个一个树到 tree[1] 中去，这个树就是结构体默认构造的树，其 L 和 R 都为 0
    if (!have_children) tree[subset].push_back(Tree());
}

int main() {
    freopen("./test_cases/draft1354.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lf%d", &r, &n);
        for (int i = 0; i < n; i++) scanf("%lf", &w[i]);
        for (int i = 0; i < (1 << n); i++) {
            sum[i] = 0;
            tree[i].clear();
            for (int j = 0; j < n; j++)
                if (i & (1 << j)) sum[i] += w[j];
        }

        int root = (1 << n) - 1;
        memset(vis, 0, sizeof(vis));
        dfs(root);

        double ans = -1;
        for (int i = 0; i < tree[root].size(); i++) ans = max(ans, tree[root][i].L + tree[root][i].R);
        printf("%.10lf\\n", ans);
    }
    return 0;
}

关键点理解

像下面一样，把每一次递归的内容捋一遍就差不多了，

其实，理解这道题目的关键处呢，我反而是认为在于对那个求子集的循环的理解。

而那个对于二进制操作集合的做法的理解，可以看这篇笔记，