【合集】紫题 20 道

发布于 2023-10-31

开始学文化课了，这个计划会鸽一鸽

放寒假了，这个计划会加快进度

这个计划废弃了，因为有了新计划

刷题！

1. 规划

展开

题意

给定一棵大小为 $n$ 的树。

给定两个长度为 $n$ 的数组 $a$ 与 $b$。在 $1$ 到 $n$ 中选出 $m$ 个点，使得选出的点联通，求选出的点的 $a_i$ 之和除以选出的点的 $b_i$ 之和的最大值。

$1 \leq m < n < 100, 1 \leq a_i, b_i \leq 10000$

题解

01 分数规划。

我们要求出 $\dfrac{\sum a_i}{\sum b_i} = c$ 的最大值，移项后可得 $\sum a_i + c \times \sum b_i$，又得到 $\sum\left(a_i - c \times b_i\right) = 0$，显然 $c$ 有单调性，于是可以二分找 $c$。

现在我们要求出一个大小为 $n - m$ 的连通块，最大化 $a_i - c \times b_i$。树形 DP。

设 $f_{i, j}$ 表示在以 $i$ 为根的子树中，选了 $j$ 个的最大值，其中 $i$ 必选。

代码

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n, m; bin >> n >> m;
  vector<tp> a(n + 1), b(n + 1), s(n + 1, 1);
  vector<vector<tp>> e(n + 1);
  bin.rar(a.begin() + 1, a.end());
  bin.rar(b.begin() + 1, b.end());
  for (tp i = 1; i < n; ++i) {
    tp u, v; bin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  m = n - m;
  auto csize = [&](auto& $, tp x, tp f) -> void {
    for (auto& i : e[x]) {
      if (i == f) continue;
      $($, i, x);
      s[x] += s[i];
    }
  };
  auto dp = [&](auto& $, tp x, tp fa, auto& r, auto& f) -> void {
    f[x][0] = 0;
    for (auto& i : e[x]) {
      if (i == fa) continue;
      $($, i, x, r, f);
      for (tp j = min(s[x], m); j >= 0; --j) {
        for (tp k = 0; k <= min(j, s[i]); ++k)
          f[x][j] = max(f[x][j], f[i][k] + f[x][j - k]);
      }
    }
    for (tp i = min(s[x], m); i >= 1; --i) f[x][i] = f[x][i - 1] + r[x];
  };
  auto check = [&](double c) -> bool {
    vector f(n + 1, vector<double>(m + 1, -INF));
    vector<double> r(n + 1);
    for (tp i = 1; i <= n; ++i) r[i] = a[i] - c * b[i];
    dp(dp, 1, 1, r, f);
    for (tp i = 1; i <= n; ++i) {
      if (f[i][m] >= 0) return true;
    }
    return false;
  };
  auto TAR = [&]() -> double {
    double l = 0, r = 10000;
    while (r - l > 0.0001) {
      double mid = (l + r) / 2;
      if (check(mid)) l = mid;
      else r = mid;
    }
    return l;
  };
  csize(csize, 1, 1);
  bin.precision(1);
  bin << TAR() + 0.05 << '\n';
}

3. Rmq Problem / mex

展开

题意

区间 mex。

题解

其实如果这题值域多大没影响，如果有大于 $n$ 的数就当成 $n + 1$ 看即可。

分块做法

首先对所有询问做一个莫队。
然后搞一个值域分块，对于每个块维护此块是否是满的（所有值都出现过）即可。
在添加某个点的时候，只需要看当前这个值域块里有没有相同值，如果没有就计数加一。显然操作时可逆的。
对于查询，只需要依次遍历每个块，找到第一个不满的块，然后在这个块内找到没有出现过的数即可。
时间复杂度：$\mathcal O\left(n \sqrt n\right)$

4. CEOI2017 Building Bridges

展开

题意

有 $n$ 个桥墩。连接 $i$ 和 $j$ 消耗代价 $\left(h_i - h_j\right)^2$，用不到的桥墩会被拆除，代价为 $w_i$。求使 $1$ 与 $n$ 联通的最小代价。

题解

设 $f_i$ 表示链接 $1$ 到 $i$ 的最小代价，$s_i$ 表示 $\sum\limits_{j = 1}^iw_i$。

$$ \begin{aligned} f_i &= \min\limits_{j = 1}^i\left\{f_j + \left(h_i - h_j\right)^2 + s_{i - 1} - s_j\right\}\\ f_i &= \min\limits_{j = 1}^i\left\{f_j + {h_i}^2 - 2h_ih_j + {h_j}^2 + s_{i - 1} - s_j\right\}\\ f_i &= {h_i}^2 + s_{i - 1} + \min\limits_{j = 1}^i\left\{f_j - 2h_ih_j + {h_j}^2 - s_j\right\} \end{aligned} $$

到此已经可以接着用各种重量级方法维护凸包开始斜率优化了，但是其实可以用李超线段树来优化。

直线的式子很显然就是 $g\left(x\right) = -2h_jx + f_j + {h_j}^2 - s_j$，在 $x = h_i$ 时找最小值即可。

代码

constexpr tp VRange = 1e6 + 3;

struct Line {
  tp k, b;
  
  Line() : k(0), b(INF) {};
  Line(tp _k, tp _b) : k(_k), b(_b) {}
  tp operator()(tp x) { return k * x + b; }
};

tp intersection(Line a, Line b) { return (b.b - a.b) / (a.k - b.k); }

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n = bin, f = 0;
  vector<tp> h(n), w(n), s(n, 0);
  vector<Line> t(VRange * 4, Line(0, INF));
  for (tp i = 0; i < n; ++i) bin >> h[i];
  for (tp i = 0; i < n; ++i) bin >> w[i];
  for (tp i = 0; i < n; ++i) s[i] = (i ? s[i - 1] : ZERO) + w[i];
  auto modify = [&](auto $, tp x, tp l, tp r, Line e) -> void {
    if (e(l) >= t[x](l) && e(r) >= t[x](r)) return;
    if (e(l) <= t[x](l) && e(r) <= t[x](r)) { t[x] = e; return; }
    tp p = intersection(e, t[x]), mid = (l + r) / 2;
    if (e(l) <= t[x](l)) {
      if (p <= mid) CALL($, x * 2, l, mid, e);
      else CALL($, x * 2 + 1, mid + 1, r, exchange(t[x], e));
    } else {
      if (p > mid) CALL($, x * 2 + 1, mid + 1, r, e);
      else CALL($, x * 2, l, mid, exchange(t[x], e));
    }
  };
  auto query = [&](auto $, tp x, tp l, tp r, tp k) -> tp {
    dbg(t[x](k));
    if (l == r) return t[x](k);
    tp mid = (l + r) / 2;
    if (mid >= k) return min(t[x](k), CALL($, x * 2, l, mid, k));
    else return min(t[x](k), CALL($, x * 2 + 1, mid + 1, r, k));
  };
  CALL(modify, 1, 0, VRange, Line(-2 * h[0], h[0] * h[0] - s[0]));
  for (tp i = 1; i < n; ++i) {
    f = h[i] * h[i] + s[i - 1] + CALL(query, 1, 0, VRange, h[i]);
    CALL(modify, 1, 0, VRange, Line(-2 * h[i], f + h[i] * h[i] - s[i]));
  }
  bin << f << '\n';
}

void MIST() {
}

5. POI2011 Lightning Conductor

展开

题意

给定整数 $n$，和一个长度为 $n$ 的数组 $a$，求 $p_i = \left\lceil\max\left\{a_j - a_i + \sqrt{\left\lvert i - j\right\rvert}\right\}\right\rceil$

$n = 5 \times 10^5, 0 \leq a_i \leq 10^9$

题解

首先可以发现决策点单调递增，于是可以分治减少一部分无用计算。但是注意这个分治是可以被卡的，但是好写好想。

代码

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n = bin;
  vector<tp> a(n);
  vector<double> p(n, 0);
  bin.rar(FULL(a));
  auto dvd = [&](auto& $, tp l, tp r, tp L, tp R) -> void {
    if (l > r) return;
    tp mid = (l + r) / 2, c;
    double tar = 0;
    for (tp i = L; i <= min(mid, R); ++i) {
      if (a[i] + sqrt(mid - i) > tar) { c = i; tar = a[i] + sqrt(mid - i); }
    }
    p[mid] = max(p[mid], tar);
    $($, l, mid - 1, L, c);
    $($, mid + 1, r, c, R);
  };
  CALL(dvd, 0, n - 1, 0, n - 1);
  reverse(FULL(a)); reverse(FULL(p));
  CALL(dvd, 0, n - 1, 0, n - 1);
  reverse(FULL(a)); reverse(FULL(p));
  for (tp i = 0; i < n; ++i) bin << tp(ceil(p[i] - a[i])) << '\n';
}

void MIST() {
}

6. CF739E Gosha is hunting

展开

题意

你要抓神奇宝贝！现在一共有 $n$ 只神奇宝贝。你有 $a$ 个『宝贝球』和 $b$ 个『超级球』。『宝贝球』抓到第 $i$ 只神奇宝贝的概率是 $p_i$，『超级球』抓到的概率则是 $u_i$。不能往同一只神奇宝贝上使用超过一个同种的『球』，但是可以往同一只上既使用『宝贝球』又使用『超级球』（都抓到算一个）。请合理分配每个球抓谁，使得你抓到神奇宝贝的总个数期望最大，并输出这个值。

题解

直接跑费用流，虽然是 $\mathcal O\left(n^3\right)$，但是卡不满。

源点向 $A, B$ 两点分别连流量为 $a, b$，费用为 $0$ 的边。
$A, B$ 分别向每个神奇宝贝连流量为 $1$，费用为 $p_i, u_i$ 的边。
每个神奇宝贝向汇点连流量为 $1$，费用为 $0$ 的边和流量为 $1$，费用为 $-p_iu_i$ 的边（如果两个球都用，抓到的概率为 $p_i + u_i - p_iu_i$）。

代码

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n, a, b; bin >> n >> a >> b;
  vector<vector<tuple<tp, tp, tp>>> e(n + 4);
  vector<tp> p(n), q(n);
  e[n].emplace_back(n + 1, a, 0);
  e[n].emplace_back(n + 2, b, 0);
  for (tp i = 0; i < n; ++i) {
    double x; bin >> x;
    e[n + 1].emplace_back(i, 1, p[i] = round(-x * 1e9));
  }
  for (tp i = 0; i < n; ++i) {
    double x; bin >> x;
    e[n + 2].emplace_back(i, 1, q[i] = round(-x * 1e9));
  }
  for (tp i = 0; i < n; ++i) e[i].emplace_back(n + 3, 1, 0);
  for (tp i = 0; i < n; ++i) e[i].emplace_back(n + 3, 1, round(p[i] * q[i] / 1e9));
  bin.precision(12);
  bin << -lib::MCMF(e, n, n + 3).second / 1e9 << '\n';
}

void MIST() {
}

持续更新中。。。

分类：刷题
最后更新于：2024-04-20 20:13:51^UTC+8
标签：无标签

红黑树的小屋