任务调度与收益最大化问题

本题对应洛谷 P10759。给定 N 个一次性任务，完成第 i 个任务可获得收益 x_i（收益可能为负数）。任务之间存在依赖关系，第 i 个任务必须在第 p_i 个任务完成后才能执行。若 p_i=0，表示该任务无前置依赖。初始资金为 S，求最终能获得的最大资金总额。

解题思路

依赖关系构成了一棵树形结构。对于树中的任意节点，若其子树中存在收益为负的任务，则完成该子树需要一定的初始资金门槛。我们需要维护每个节点子树内的任务需求集合，记录完成这些任务所需的最小初始资金以及完成后的净收益。

处理策略采用自底向上的方式。对于每个节点，将其子节点的需求集合进行合并。为了优化合并效率，采用启发式合并（Heuristic Merge），即总是将较小的集合合并到较大的集合中。合并后，若当前节点的总收益仍为负，则继续从集合中选取所需资金最小的任务进行"预支"，直到当前节点收益非负或集合为空。

最终处理根节点时，同样按照所需资金从小到大尝试执行任务，直到初始资金不足以支持下一个任务为止。

算法空间复杂度为 O(N)，时间复杂度为 O(N \log^2 N)。

参考代码

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

const int LIMIT = 300005;

struct Requirement {
    int need;
    int gain;
    int id;
};

struct ReqComparator {
    bool operator()(const Requirement& a, const Requirement& b) const {
        if (a.need != b.need) return a.need < b.need;
        if (a.gain != b.gain) return a.gain > b.gain;
        return a.id < b.id;
    }
};

int n, parent[LIMIT];
int64 capital, profit[LIMIT];
set<Requirement, ReqComparator> pool[LIMIT];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> capital;
    for (int i = 1; i <= n; ++i) {
        cin >> profit[i] >> parent[i];
    }

    for (int i = n; i >= 1; --i) {
        int64 minInit = 0;
        while (profit[i] < 0 && !pool[i].empty()) {
            Requirement current = *pool[i].begin();
            pool[i].erase(pool[i].begin());
            
            int target = current.id;
            if (pool[i].size() < pool[target].size()) {
                swap(pool[i], pool[target]);
            }
            
            for (const auto& item : pool[target]) {
                pool[i].insert(item);
            }
            
            minInit = max(minInit, (int64)current.need - profit[i]);
            profit[i] += current.gain;
        }
        
        if (profit[i] >= 0) {
            pool[parent[i]].insert({(int)minInit, (int)profit[i], i});
        }
    }

    int64 extraNeed = 0;
    while (!pool[0].empty()) {
        Requirement current = *pool[0].begin();
        pool[0].erase(pool[0].begin());
        
        int target = current.id;
        if (pool[0].size() < pool[target].size()) {
            swap(pool[0], pool[target]);
        }
        
        for (const auto& item : pool[target]) {
            pool[0].insert(item);
        }
        
        extraNeed = max(extraNeed, (int64)current.need - profit[0]);
        if (extraNeed > capital) break;
        
        profit[0] += current.gain;
    }
    
    cout << profit[0] << endl;
    return 0;
}

车站转移方案计数问题

本题对应洛谷 P10761。共有 N 个车站，编号为 1 到 N。从第 i 个车站出发，可以到达 i + j \cdot d_i 号车站，其中 1 \le j \le x_i 且目标车站编号不超过 N。求从车站 1 出发到达其他所有车站的不同路径方案总数。

解题思路

该问题可以通过根号分治（Square Root Decomposition）的思想来解决。设定一个阈值 B（通常取 \sqrt{N}）。

当步长 d_i > B 时，由于每次跳跃距离较大，从任意点出发最多只能跳跃 \sqrt{N} 次，因此可以直接模拟转移过程，更新后续站点的方案数。

当步长 d_i \le B 时，跳跃次数可能很多。此时利用模数性质，将转移看作是在模 d_i 同余的类中进行。对于每个可能的步长 k \le B 和余数 r，维护一个计数器，记录当前模 k 余 r 的位置累积的方案数。当处理到位置 i 时，直接查询所有模数下的计数值即可。同时需要记录何时该贡献失效，以便及时移除。

算法空间复杂度为 O(N)，时间复杂度为 O(N \sqrt{N})。

参考代码

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

const int BLOCK_SIZE = 320;
const int MAX_N = 1000005;
const int MOD = 1e9 + 7;

int n, ways[MAX_N], modCache[BLOCK_SIZE + 5][BLOCK_SIZE + 5], totalAns;
vector<tuple<int, int, int>> expireList[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    ways[1] = 1;
    
    for (int i = 1; i <= n; ++i) {
        int d, x;
        // 累加来自小步长的贡献
        for (int k = 1; k <= BLOCK_SIZE; ++k) {
            ways[i] = (ways[i] + modCache[k][i % k]) % MOD;
        }
        
        totalAns = (totalAns + ways[i]) % MOD;
        
        // 移除过期的贡献
        for (auto& [val, k, r] : expireList[i]) {
            modCache[k][r] = (modCache[k][r] - val + MOD) % MOD;
        }
        
        if (d == 0 || x == 0) continue;
        
        if (d <= BLOCK_SIZE) {
            // 小步长：更新模数缓存
            int remainder = i % d;
            modCache[d][remainder] = (modCache[d][remainder] + ways[i]) % MOD;
            // 记录失效位置
            int endPos = min((long long)n, i + 1LL * x * d);
            expireList[endPos].emplace_back(ways[i], d, remainder);
        } else {
            // 大步长：直接模拟跳转
            for (int j = 1; j <= x && i + 1LL * j * d <= n; ++j) {
                int nextPos = i + j * d;
                ways[nextPos] = (ways[nextPos] + ways[i]) % MOD;
            }
        }
    }
    
    cout << totalAns << endl;
    return 0;
}