Atcoder ABC 457

2026-05-092026-05-09

Info

2026.04.25 第十周 周六 链接

这把ab做完C写了一堆很丑的上去，wa了一发以后就摆了（，把CD补一下吧

A 签到

B 签到

void solve() {
  int n;
  cin >> n;
  auto a = vector(n, deque<int>());
  for (int i = 0; i < n; i ++) {
    int l;
    cin >> l;
    for (int j = 0; j < l; j ++) {
      int xx;
      cin >> xx;
      a[i].push_back(xx);
    }
  }
  int x, y;
  cin >> x >> y;
  x --, y --;
  cout << a[x][y] << endl;
}

C

题目：创造出一个新数组\(B\)，就是把\(A\)的第\(i\)个数组重复\(C_i\)次，然后找到\(B\)的第\(k\)个元素

input

\(n\ k\)

\(l_1\ A_{1,1} \cdots\ A_{1,L_1}\)

\(.\)

\(.\)

\(l_N\ A_{N,1} \cdots\ A_{N,L_N}\)

\(C_1\ C_2\ \cdots \ C_N\)

Tip

首先，把\(B\)给构造出来一定是没必要的

唉就是一个个块查过去就好了

void solve2() {
  int n;
  i64 k;
  cin >> n >> k;
  vector<vector<int>> a(n + 1);
  vector<int> len(n + 1);
  for (int i = 1; i <= n; i ++) {
    cin >> len[i];
    a[i].resize(len[i] + 1);
    for (int j = 1; j <= len[i]; j ++) {
      cin >> a[i][j];
    }
  }

  vector<int> c(n + 1);
  for (int i = 1; i <= n; i ++) cin >> c[i];
  for (int i = 1; i <= n; i ++) {
    i64 block = (i64)c[i] * len[i];
    if (k > block) {
      k -= block;
    } else {
      k = (k - 1) % len[i];
      cout << a[i][k + 1];
      return;
    }
  }
}

D 二分

最大值最小

二分信号，考试的时候一开始想的是贪心（

k的范围也是到了\(10^{18}\)，确实应该想到二分，太久没遇到二分了

二分答案啊

单独验证一个答案稍微有点复杂的时候就容易想不到

其实这个答案验证就是\(O(n)\)的

呃呃啊啊

void solve() {
  int n;
  i64 k;
  cin >> n >> k;
  vector<i64> a(n + 1);
  for (int i = 1; i <= n; i ++) cin >> a[i];

  auto check = [&](i64 x) {
    i64 need = 0;
    for (int i = 1; i <= n; i ++) {
      if (a[i] < x) {
        i64 diff = x - a[i];
        need += (diff + i - 1)  / i;
        if (need > k) return false;
      }
    }
    return true;
  };

  i64 lo = 0, hi = 4e18;
  while (lo <= hi) {
    i64 mid = (lo + hi) / 2;
    if (check(mid)) lo = mid + 1;
    else hi = mid - 1;
  }
  cout << hi << endl;
}