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