2025省赛预选赛补题 • santisify Site

(cf补题链接)[https://codeforces.com/gym/606649 ↗]

H#

题目描述#

给定三个数组 $A$ , $B$ , $C$ ,长度分别为 $n$ , $m$ , $p$ ,每个数组取一个数求和，输出前 $k$ 个最大值。

数据范围： $l \le n,m,p \le 1000$ , $1 \le k \le min(3000, n \times m \times p)$ , $0 \le A_{i}, B_{i}, C_{i} \le 10000000000$

解题思路#

首先想到的最简单的思路是暴力求解，这样的时间复杂度将会是 $1e^{9} \log_{2} ^{1e^{9}}$ ，如何优化呢？
我们可以将其中两个数组合并，这里我们选择将 $A, B$ 两个数组合并，然后进行排序，这里复杂度为 $1e^{6}\log_{2}^{1e^{6}}$ , 我么选择合并后的前 $k$ 个最大值和数组 $C$ 合并，这里的复杂度为 $3e^{3} \times 1e^{3}$ , 可以用堆维护 $k$ 个数。

参考代码#

#include<bits/stdc++.h>

using i128 = __int128;
#define endl '\n'
#define int long long
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, m, p, k;
  std::cin >> n >> m >> p >> k;
  std::vector<int> a(n), b(m), c(p);
  for(int i = 0; i < n; i++) std::cin >> a[i];
  for(int i = 0; i < m; i++) std::cin >> b[i];
  for(int i = 0; i < p; i++) std::cin >> c[i];
  std::vector<int> ab;
  for(int i = 0; i < n; i++) {
   for(int j = 0; j < m; j++) {
    ab.push_back(a[i] + b[j]);
   }
  }
  std::sort(ab.begin(), ab.end(), std::greater<>());
  std::sort(c.begin(), c.end(), std::greater<>());
  std::priority_queue<int, std::vector<int>, std::greater<> > pq;
  for(int i = 0; i < std::min(k, (int) ab.size()); i++) {
   for(int j = 0; j < p; j++) {
    int t = ab[i] + c[j];
    if (pq.size() == k) {
     auto w = pq.top();
     if (w < t) {
      pq.pop();
      pq.push(t);
     }
    } else {
     pq.push(t);
    }
   }
  }
  std::vector<int> res;
  while (!pq.empty()) {
   res.push_back(pq.top());
   pq.pop();
  }
  std::reverse(res.begin(), res.end());
  for(auto i : res) {
   std::cout << i << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

cpp

E#

题目描述#

给定一个长度为 $n$ 的数组 $A$ , 有 $q$ 次询问,每次给出 $l, r, start, end$ , 对于每次询问，我们要输出 $A$ 中在区间段 $[l,r]$ 中, $start \le A_{i} \le end$ 的数的个数。

数据范围： $1 \le N, q \le 10^{5}, -10^{12} \le A_{i} \le 10^{12}$

解题思路#

赛时，我想的是对区间内的数排序,然后二分查找边界,计算数量,奈何TLE,tql,显然是排序超时了。
正解是树状数组或者线段树

参考代码#

#include<bits/stdc++.h>

using i128 = __int128;
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
std::vector<int> a(MAX_N);
struct Node {
  int l{}, r{};
  std::vector<int> sorted;
};

Node tr[4 * MAX_N];

void build(int u, int l, int r) {
  tr[u].l = l;
  tr[u].r = r;
  tr[u].sorted.clear();
  if (l == r) {
   tr[u].sorted.push_back(a[l]);
   return;
  }
  int mid = (l + r) / 2;
  build(u << 1, l, mid);
  build(u << 1 | 1, mid + 1, r);
  auto &left = tr[u << 1].sorted;
  auto &right = tr[u << 1 | 1].sorted;
  tr[u].sorted.resize(left.size() + right.size());
  merge(left.begin(), left.end(), right.begin(), right.end(), tr[u].sorted.begin());
}

int query(int u, int l, int r, int start, int end) {
  if (tr[u].r < l || tr[u].l > r) {
   return 0;
  }
  if (l <= tr[u].l && tr[u].r <= r) {
   auto &v = tr[u].sorted;
   int left_pos = lower_bound(v.begin(), v.end(), start) - v.begin();
   int right_pos = upper_bound(v.begin(), v.end(), end) - v.begin();
   return right_pos - left_pos;
  }
  return query(u << 1, l, r, start, end) + query(u << 1 | 1, l, r, start, end);
}

void solve() {
  int N, Q;
  std::cin >> N >> Q;
  for(int i = 1; i <= N; ++i) {
   std::cin >> a[i];
  }
  build(1, 1, N);
  while (Q--) {
   int l, r, s, e;
   std::cin >> l >> r >> s >> e;
   std::cout << query(1, l, r, s, e) << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

cpp