nikkei2019 qual F

题目描述

这题很好玩，是一个传统背包模型的变体。每个物品有一种颜色和一个价值。规定如果一个物品放进背包里，那么背包中一定至少有一个同颜色的物品。求问背包里的物品数量为 - 的价值最大值分别为多少。

解题思路

首先我们先将不同颜色的物体分别保存并且从大到小排序。之后我们考虑假如只有一种物品的情况。在这种情况下，答案就是物品价值的前缀和。

接下来考虑，如果我们将两个物品的答案贡献，背包内物品的最大价值可以用动态规划来求，对于价值为 的背包，答案为 。我们注意到，对于奇数位和偶数位的答案，它们是具有单调性的。因为每个我们必定可以找到 。这里的 和 表示任意的合法答案。那么我们考虑上面的式子，相当于在这一过程中， 单调递增， 单调递减。而且容易发现，单增的速度越来越慢，单减的速度越来越快，这个和是一个单峰的函数！因此我们可以利用三分法来优化背包的过程。在合并背包的过程中，我们可以利用类似线段树建树的方法来做。这样的时间复杂度是 的，能够通过本题。

给出本题的代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using std::sort;
using std::min;
using std::max;
using std::vector;
typedef long long ll;
const int N = 2e5 + 5;
const int K = N / 2;
vector <ll> a[N];
ll check(vector <ll> &a, vector <ll> &b, int ia, int ib) {
  if (a[ia] == -1 || b[ib] == -1) return -1ll;
  else return a[ia] + b[ib];
}
ll find_ans(vector <ll> &odd_l, vector <ll> &odd_r, vector <ll> &even_l, vector <ll> &even_r, int L, int R, int x) {
  // even
  ll tmp = -1;
  int l = (L & 1) ? L + 1 : L, r = (R & 1) ? R - 1 : R;
  ll lchk, rchk;
  l = (l - 2) / 2, r = (r - 2) / 2;
  if (l <= r) {
  	while (l < r) {
  	  int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
  	  if (x & 1) lchk = check(even_l, odd_r, lmid, (x - lmid * 2 - 2 - 3) / 2);
  	  else lchk = check(even_l, even_r, lmid, (x - lmid * 2 - 2 - 2) / 2);
  	  if (x & 1) rchk = check(even_l, odd_r, rmid, (x - rmid * 2 - 2 - 3) / 2);
  	  else rchk = check(even_l, even_r, rmid, (x - rmid * 2 - 2 - 2) / 2);
      if (lchk > rchk) r = rmid - 1;
      else l = lmid + 1;
  	}
    if (x & 1) lchk = check(even_l, odd_r, l, (x - l * 2 - 2 - 3) / 2);
    else lchk = check(even_l, even_r, l, (x - l * 2 - 2 - 2) / 2);
    if (x & 1) rchk = check(even_l, odd_r, r, (x - r * 2 - 2 - 3) / 2);
    else rchk = check(even_l, even_r, r, (x - r * 2 - 2 - 2) / 2);
    tmp = max(tmp, max(lchk, rchk));
  }
  // odd
  l = (L & 1) ? L : L + 1, r = (R & 1) ? R : R - 1;
  l = (l - 3) / 2, r = (r - 3) / 2;
  if (l <= r) {
  	while (l < r) {
  	  int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
  	  if (x & 1) lchk = check(odd_l, even_r, lmid, (x - lmid * 2 - 3 - 2) / 2);
  	  else lchk = check(odd_l, odd_r, lmid, (x - lmid * 2 - 3 - 3) / 2);
  	  if (x & 1) rchk = check(odd_l, even_r, rmid, (x - rmid * 2 - 3 - 2) / 2);
  	  else rchk = check(odd_l, odd_r, rmid, (x - rmid * 2 - 3 - 3) / 2);
      if (lchk > rchk) r = rmid - 1;
      else l = lmid + 1;
  	}
    if (x & 1) lchk = check(odd_l, even_r, l, (x - l * 2 - 3 - 2) / 2);
  	else lchk = check(odd_l, odd_r, l, (x - l * 2 - 3 - 3) / 2);
  	if (x & 1) rchk = check(odd_l, even_r, r, (x - r * 2 - 3 - 2) / 2);
  	else rchk = check(odd_l, odd_r, r, (x - r * 2 - 3 - 3) / 2);
    tmp = max(tmp, max(lchk, rchk));
  }
  return tmp;
}
vector <ll> merge(vector <ll> &lans, vector <ll> &rans) {
  int lsz = lans.size(), rsz = rans.size();
  int sz = lsz + rsz;
  vector <ll> ans(sz);
  ans[0] = -1;
  ans[1] = max(lsz >= 2 ? lans[1] : -1, rsz >= 2 ? rans[1] : -1);
  ans[2] = max(lsz >= 3 ? lans[2] : -1, rsz >= 3 ? rans[2] : -1);
  vector <ll> tmp_even_l, tmp_even_r, tmp_odd_l, tmp_odd_r;
  for (int i = 1; i < lsz; ++i) {
    if (i & 1) tmp_even_l.push_back(lans[i]);
    else tmp_odd_l.push_back(lans[i]);
  }
  for (int i = 1; i < rsz; ++i) {
    if (i & 1) tmp_even_r.push_back(rans[i]);
    else tmp_odd_r.push_back(rans[i]);
  }
  for (int i = 4; i <= sz; ++i) {
    // max(2, x - rsz) <= i <= min(x - 2, lsz)
    auto tmp = max(lsz >= i ? lans[i - 1] : -1, rsz >= i ? rans[i - 1] : -1);
    int L = max(2, i - rsz), R = min(i - 2, lsz);
    tmp = max(tmp, find_ans(tmp_odd_l, tmp_odd_r, tmp_even_l, tmp_even_r, L, R, i));
    ans[i - 1] = tmp;
  }
  return ans;
}
vector <ll> query(int l, int r) {
  if (l == r) {
    if (a[l].size() == 0) a[l].push_back(-1);
    a[l][0] = -1;
    return a[l];
  }
  int mid = (l + r) >> 1;
  auto lans = query(l, mid), rans = query(mid + 1, r);
  return merge(lans, rans);
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[x].push_back(y);
  }
  auto cmp = [&](int x, int y) {
    return x > y;
  };
  for (int i = 1; i <= k; ++i) {
    if (a[i].size() > 0) {
      sort(a[i].begin(), a[i].end(), cmp);
    }
    for (int j = 1; j < a[i].size(); ++j) {
      a[i][j] += a[i][j - 1];
    }
  }
  auto ans = query(1, k);
  for (auto x : ans) {
    printf("%lld\n", x);
  }
  return 0;
}