abc369

E

floyd 之后 $2^k \times k!$ 枚举方向和排列。

F

直接类似扫描线，并且输出方案即可。

const int N=1<<18;
using info = array<int,2>;

info c[N];
void upd(int x, info v){
  while (x < N) {
    cmax(c[x], v);
    x += x & -x;
  }
}
info query(int x) {
  info res{};
  while (x) {
    res = max(res, c[x]);
    x -= x & -x;
  }
  return res;
}

pii a[N];
vector<int> pt[N];
int dp[N], pre[N];
void solve() {
  int h, w, n;
  cin >> h >> w >> n;
  for (int i = 1; i <= n; i++) {
    int r, c;
    cin >> r >> c;
    a[i] = {r, c};
    pt[r].push_back(i);
  }

  for (int r = 1; r <= h; r++) {
    sort(all(pt[r]), [&](int i, int j) {
      return a[i] < a[j];
    });
    for (auto i : pt[r]) {
      auto [_, c] = a[i];
      auto [v, j] = query(c);
      dp[i] = dp[j] + 1;
      pre[i] = j;
      upd(c, {dp[i], i});
    }
  }

  auto [res, cur] = query(N - 1);
  vector<int> path;
  while (cur > 0) {
    path.push_back(cur);
    cur = pre[cur];
  }

  // debug(res, path);
  string ans = "";

  reverse(all(path));
  a[n + 1] = {h, w};
  path.push_back(n + 1);
  int x = 1, y = 1;

  for (auto id : path) {
    while (x < a[id].first) x++, ans += "D";
    while (y < a[id].second) y++, ans += "R";
  }

  cout << res << "\n";
  cout << ans << "\n";
}

G

长链剖分模板题。

void solve() {
  int N;
  cin >> N;

  vc<vc<pii>> g(N);

  rep(N - 1) {
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    g[a].pb(b, c);
    g[b].pb(a, c);
  }

  vl mx(N);
  vl all_chain;
  auto dfs = [&](auto &dfs, int u, int p) -> void {
    for (auto [v, w] : g[u]) {
      if (v == p) continue;
      dfs(dfs, v, u);
      if (mx[v] + w >= mx[u]) {
        if (mx[u] > 0)
          all_chain.pb(mx[u]);
        mx[u] = mx[v] + w;
      } else {
        all_chain.pb(mx[v] + w);
      }
    }
  };
  dfs(dfs, 0, -1);
  all_chain.pb(mx[0]);
  sort(all(all_chain), greater<>());

  ll ans = 0;
  int k = 0;
  rep(N) {
    if (k < sz(all_chain)) {
      ans += all_chain[k];
      k++;
    }
    cout << ans * 2 << "\n";
  }
}