Luogu P10759

题目描述

你有 \(N\) 个一次性的工作，完成第 \(i\) 个工作可以获得 \(x_i\) 的利润（可能为负）。有些工作依赖于其他工作，第 \(i\) 个工作必须在第 \(p_i\) 个工作完成之后进行。若 \(p_i=0\)，则 \(i\) 没有依赖。

你初始有 \(S\) 元，求你最多能获得多少元。

思路

在一个点的子树内，有一些负的点，使得你不能越过它，除非你的初始金额更高或赚了钱。我们对每个点记录其子树中目前还做不起的工作，记录其至少需要的初始金额和其收益，使得其收益非负。

然后对于每个点，我们对他的儿子按所需初始金额从小到大排序，把能做的都做了。当我们做了一个儿子时，其子树也都能做了，所以我们要把儿子的儿子也放进来，这个可以用 set 和启发式合并解决。

最后，对于根节点，我们用类似的方法求解。我们不断对其儿子需要的初始金额求最大值，直到初始金额 \(>s\)，那么退出。

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

代码

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

const int MAXN = 300001;

struct Node {
  int x, y, u;
};

struct cmp {
  bool operator()(const Node &a, const Node &b) const {
    return a.x < b.x || (a.x == b.x && a.y > b.y) || (a.x == b.x && a.y == b.y && a.u < b.u);
  }
};

int n, f[MAXN];
set<Node, cmp> S[MAXN];
ll s, a[MAXN];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> s;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i] >> f[i];
  }
  for(int i = n; i >= 1; --i) {
    ll X = 0;
    for(; a[i] < 0 && !S[i].empty(); ) {
      auto [x, y, u] = *S[i].begin();
      S[i].erase(S[i].begin());
      if(S[i].size() < S[u].size()) {
        swap(S[i], S[u]);
      }
      for(auto x : S[u]) {
        S[i].insert(x);
      }
      X = max(X, x - a[i]);
      a[i] += y;
    }
    if(a[i] >= 0) {
      S[f[i]].insert({X, a[i], i});
    }
  }
  ll X = 0;
  for(; !S[0].empty(); ) {
    auto [x, y, u] = *S[0].begin();
    S[0].erase(S[0].begin());
    if(S[0].size() < S[u].size()) {
      swap(S[0], S[u]);
    }
    for(auto x : S[u]) {
      S[0].insert(x);
    }
    X = max(X, x - a[0]);
    if(X > s) {
      break;
    }
    a[0] += y;
  }
  cout << a[0];
  return 0;
}

Luogu P10761

题目描述

有 \(N\) 个车站 \(1,2,\dots,N\)，第 \(i\) 个车站能到达 \(i+j\cdot d_i(1\le j\le x_i且i+j\cdot d_i\le N)\)。

求从 \(1\) 到其他站的不同方案数。

思路

使用根号分治。

若 \(d_i> \sqrt N\)，那么最多只有 \(\sqrt N\) 个转移，直接做，

否则，转移可以看作转移到 \(i\equiv j\pmod {d_i}\)，对每个模数，余数记录并转移即可。

空间复杂度 \(O(N)\)，时间复杂度 \(O(N\sqrt N)\)。

代码

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

const int B = 317, MAXN = 1000005, MOD = int(1e9) + 7;

int n, dp[MAXN], cnt[B + 5][B + 5], ans;
vector<tuple<int, int, int>> ve[MAXN];

int main() {
 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
 cin >> n;
 dp[1] = 1;
 for(int i = 1, d, x; i <= n; ++i) {
   cin >> d >> x;
   for(int j = 1; j <= B; ++j) {
     dp[i] = (dp[i] + cnt[j][i % j]) % MOD;
   }
   ans = (ans + dp[i]) % MOD;
   for(auto [val, x, y] : ve[i]) {
     cnt[x][y] = (cnt[x][y] - val + MOD) % MOD;
   }
   if(!d || !x) {
     continue;
   }
   if(d <= B) {
     cnt[d][i % d] = (cnt[d][i % d] + dp[i]) % MOD;
     ve[min(i + 1ll * x * d, 0ll + n)].emplace_back(dp[i], d, i % d);
   }else {
     for(int j = 1; j <= x && i + 1ll * j * d <= n; ++j) {
       dp[i + j * d] = (dp[i + j * d] + dp[i]) % MOD;
     }
   }
 }
 cout << ans;
 return 0;
}