「ROI 2021 Day1」投资报告 题解

题目理解

我们有一个树形结构，根节点是创始人（经理），叶子节点是顾问，中间节点是经理。每个顾问有多个改进可选，但只能报告一个。每个经理需要将下属的报告按某种顺序拼接。最终根节点的报告必须是严格递增的序列。

关键观察

1. 问题转化

每个节点（无论是经理还是顾问）都可以看作产生一个改进序列。最终要求根节点的序列严格递增。

2. 区间表示法

对于每个节点，我们可以用区间 $[L, R]$ 来表示该节点能产生的改进范围：

• 对于顾问：$L$ 和 $R$ 分别是可选改进的最小值和最大值
• 对于经理：$L$ 和 $R$ 取决于下属报告的顺序选择

3. 经理节点的处理

经理节点需要将下属的报告序列拼接。关键性质：如果经理节点的报告要形成连续区间 $[L, R]$，那么下属的区间必须能够按某种顺序拼接成这个区间。

算法思路

方法：树形DP + 区间合并

步骤1：数据结构定义

#include <bits/stdc++.h>
using namespace std;

struct Node {
    bool is_manager;
    vector<int> children;  // 下属编号
    vector<int> improvements; // 仅顾问有：可选的改进
    int L, R; // 该节点能产生的最小和最大改进
    vector<int> order; // 方案：经理存储下属顺序，顾问存储选择的改进
};

步骤2：DFS处理

// 返回是否可行，并填充节点的L,R和方案
bool dfs(int u, vector<Node>& tree) {
    if (!tree[u].is_manager) {
        // 顾问节点：选择能形成最小区间的改进
        if (tree[u].improvements.empty()) return false;
        
        // 选择最小的改进（贪心：为上级提供更多灵活性）
        int chosen = *min_element(tree[u].improvements.begin(), 
                                tree[u].improvements.end());
        tree[u].L = tree[u].R = chosen;
        tree[u].order = {chosen};
        return true;
    }
    
    // 经理节点：收集下属信息
    vector<pair<int, int>> ranges; // 存储下属的[L,R]
    for (int v : tree[u].children) {
        if (!dfs(v, tree)) return false;
        ranges.emplace_back(tree[v].L, tree[v].R);
    }
    
    // 尝试所有排列，找到可行的最小L和最大R
    vector<int> perm(tree[u].children.size());
    iota(perm.begin(), perm.end(), 0);
    
    int best_L = INT_MAX, best_R = INT_MIN;
    vector<int> best_order;
    
    do {
        // 检查当前排列是否可行
        int current_L = INT_MAX, current_R = INT_MIN;
        bool valid = true;
        
        for (int i = 0; i < perm.size(); i++) {
            int idx = perm[i];
            int child_L = ranges[idx].first;
            int child_R = ranges[idx].second;
            
            if (i == 0) {
                current_L = child_L;
                current_R = child_R;
            } else {
                // 检查是否能拼接：当前区间必须在之前区间的右边
                if (child_L <= current_R) {
                    valid = false;
                    break;
                }
                current_R = child_R;
            }
        }
        
        if (valid) {
            if (current_L < best_L || (current_L == best_L && current_R > best_R)) {
                best_L = current_L;
                best_R = current_R;
                best_order = perm;
            }
        }
    } while (next_permutation(perm.begin(), perm.end()));
    
    if (best_L == INT_MAX) return false; // 没有可行排列
    
    tree[u].L = best_L;
    tree[u].R = best_R;
    tree[u].order = best_order;
    return true;
}

步骤3：输出方案

void output_solution(int u, vector<Node>& tree) {
    if (!tree[u].is_manager) {
        // 顾问：输出选择的改进
        cout << tree[u].order[0] << "\n";
        return;
    }
    
    // 经理：输出下属顺序
    for (int i = 0; i < tree[u].order.size(); i++) {
        if (i > 0) cout << " ";
        cout << tree[u].children[tree[u].order[i]];
    }
    cout << "\n";
    
    // 递归输出下属
    for (int idx : tree[u].order) {
        output_solution(tree[u].children[idx], tree);
    }
}

完整代码实现

#include <bits/stdc++.h>
using namespace std;

struct Node {
    bool is_manager;
    vector<int> children;
    vector<int> improvements;
    int L, R;
    vector<int> order; // 对于经理：下属的排列顺序；对于顾问：选择的改进
};

bool dfs(int u, vector<Node>& tree) {
    if (!tree[u].is_manager) {
        // 顾问节点
        if (tree[u].improvements.empty()) 
            return false;
        
        // 选择能形成最小区间的改进（选择最小值）
        int chosen = *min_element(tree[u].improvements.begin(), 
                                tree[u].improvements.end());
        tree[u].L = tree[u].R = chosen;
        tree[u].order = {chosen};
        return true;
    }
    
    // 经理节点
    vector<pair<int, int>> child_ranges;
    for (int v : tree[u].children) {
        if (!dfs(v, tree)) 
            return false;
        child_ranges.emplace_back(tree[v].L, tree[v].R);
    }
    
    int k = tree[u].children.size();
    vector<int> perm(k);
    iota(perm.begin(), perm.end(), 0);
    
    int best_L = INT_MAX, best_R = INT_MIN;
    vector<int> best_perm;
    
    do {
        int current_L = INT_MAX, current_R = INT_MIN;
        bool valid = true;
        
        for (int i = 0; i < k; i++) {
            int idx = perm[i];
            auto [L, R] = child_ranges[idx];
            
            if (i == 0) {
                current_L = L;
                current_R = R;
            } else {
                if (L <= current_R) {
                    valid = false;
                    break;
                }
                current_R = R;
            }
        }
        
        if (valid) {
            if (current_L < best_L || (current_L == best_L && current_R > best_R)) {
                best_L = current_L;
                best_R = current_R;
                best_perm = perm;
            }
        }
    } while (next_permutation(perm.begin(), perm.end()));
    
    if (best_L == INT_MAX) 
        return false;
    
    tree[u].L = best_L;
    tree[u].R = best_R;
    tree[u].order = best_perm;
    return true;
}

void output_solution(int u, vector<Node>& tree) {
    if (!tree[u].is_manager) {
        cout << tree[u].order[0] << "\n";
        return;
    }
    
    for (int i = 0; i < tree[u].order.size(); i++) {
        if (i > 0) cout << " ";
        cout << tree[u].children[tree[u].order[i]];
    }
    cout << "\n";
    
    for (int idx : tree[u].order) {
        output_solution(tree[u].children[idx], tree);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Node> tree(n + 1);
    
    // 读取输入
    for (int i = 1; i <= n; i++) {
        int type;
        cin >> type;
        tree[i].is_manager = (type == 1);
        
        if (tree[i].is_manager) {
            int k;
            cin >> k;
            tree[i].children.resize(k);
            for (int j = 0; j < k; j++) {
                cin >> tree[i].children[j];
            }
        } else {
            int m;
            cin >> m;
            tree[i].improvements.resize(m);
            for (int j = 0; j < m; j++) {
                cin >> tree[i].improvements[j];
            }
        }
    }
    
    // 检查可行性
    if (!dfs(1, tree)) {
        cout << "No\n";
        return 0;
    }
    
    cout << "Yes\n";
    output_solution(1, tree);
    
    return 0;
}

优化策略

1. 减少排列枚举

由于 $k \leq 8$，$8! = 40320$ 在可接受范围内。但对于大数据，可以优化：

// 按L排序后贪心选择
sort(perm.begin(), perm.end(), [&](int a, int b) {
    return child_ranges[a].first < child_ranges[b].first;
});

// 然后检查这个自然顺序是否可行

2. 区间合并的剪枝

如果发现某个排列已经不可能产生更好的结果，提前终止。

复杂度分析

• 时间复杂度：$O(n \cdot k!)$，其中 $k \leq 8$
• 空间复杂度：$O(n + \sum m_i)$

样例验证

样例1

树结构：

• 节点1（经理）：下属5,4,6
• 节点5（顾问）：改进10,61,60
• 节点4（顾问）：改进80,20
• 节点6（经理）：下属3,2
• 节点3（顾问）：改进40,70
• 节点2（顾问）：改进30,90,91,92

算法会找到可行的改进选择和报告顺序。

样例3

树结构导致无法形成递增序列，输出"No"。

总结

本题的关键在于：

1. 使用区间表示每个节点的改进范围
2. 经理节点通过枚举排列来合并下属区间
3. 贪心选择改进以获得最大灵活性

这种"树形DP + 排列枚举"的方法能够有效解决此类约束满足问题。