2025.7.25 模拟赛

子段乘积

前缀和 后缀和 枚举

首先，选择两段不相交的非空子区间，并求出两个区间的和的乘积，这两个区间肯定是一个在左边一个在右边的，因此我们很容易想到可以枚举分界点 $i$，限制左区间是 $[1,i]$ 的子区间，右区间是 $[i+1,n]$ 的子区间。

那么一个前缀、后缀区间的子区间的最大和、最小和怎么求出呢？以前缀为例：首先先假设每个前缀区间和最大的子区间的右边界和这个前缀区间一样，都是 $i$，如果 $p_i=\sum _{j=1}^i{a}_j$，那么子区间的最大值就等于 $p_i$ 减去最小的 $p_j$ $(j<i)$，最小的 $p_j$ 在循环时额外维护一个变量就行了。

当然每个前缀区间的最大子区间的右边界肯定不是 $i$，因此我们再进行一个前缀 $\max$ 即可。后缀同理。最后我们枚举 $i$，统计答案就行了。时间复杂度 $\mathcal{O}(n)$。

#include <iostream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
LL a[kMaxN], p[kMaxN], preMax[kMaxN], preMin[kMaxN], sufMax[kMaxN], sufMin[kMaxN], t, n, ans;
vector<LL> v;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    v.clear();
    for (LL i = 1; i <= n; i++) {
      cin >> a[i];
      p[i] = p[i - 1] + a[i];
    }
    preMax[0] = sufMax[n + 1] = -1e18;
    preMin[0] = sufMin[n + 1] = 1e18;
    for (LL i = 1, mx = 0, mn = 0; i < n; i++) {
      preMax[i] = max(preMax[i - 1], p[i] - mn);
      preMin[i] = min(preMin[i - 1], p[i] - mx);
      mn = min(mn, p[i]);
      mx = max(mx, p[i]);
    }
    for (LL i = n, mx = p[n], mn = p[n]; i > 1; i--) {
      mn = min(mn, p[i]);
      mx = max(mx, p[i]);
      sufMax[i] = max(sufMax[i + 1], mx - p[i - 1]);
      sufMin[i] = min(sufMin[i + 1], mn - p[i - 1]);
    }
    ans = -1e18;
    for (LL i = 1; i < n; i++) {
      ans = max(ans, max(max(preMax[i] * sufMax[i + 1], preMax[i] * sufMin[i + 1]),
                         max(preMin[i] * sufMax[i + 1], preMin[i] * sufMin[i + 1])));
    }
    cout << ans << '\n';
  }
  return 0;
}

玩偶

线段树 树状数组 二分 排序 贪心

首先我们丢玩偶的方案肯定和最终留下的所有玩偶中最大的 $h$ 的玩偶的数量有关，因此我们考虑对 $h$ 进行排序，然后枚举最大的 $h$ 是哪一个，比它大的就删掉，比它小的按需删掉。

设删掉比当前枚举的 $h$ 大的所有玩偶后剩下的玩偶数量为 $r$，其中大小正好为 $h$ 的数量之和为 $m$，在比 $h$ 小的玩偶中删掉 $d$ 个，那么需要满足的条件是：$m>\frac{r-d}{2}$，也就是 $2m>r-d$，即 $d>r-2m$。由于都是整数，我们删除 $r-2m+1$ 个比 $h$ 小的玩偶的是最优的。

现在我们的时间复杂度已经是 $\mathcal{O}(n{\log }_{2}n)$ 的了，找出满足条件的删除玩偶方案肯定是不能再 $\mathcal{O}(n)$ 的了。由于我们删除玩偶每次都会选择损失 $c$ 最小的进行删除，因此不妨在最开始时直接对 $c$ 进行排序，然后按照 $c$ 排序的顺序记录一个 id，然后维护一个树状数组，插入新的玩偶类型时用 id 当下标，再套一个二分寻找一个最大的 id，使得 $1$ 到这个 id 的所有玩偶的数量和小于等于 $r-2m$，剩下需要的玩偶再次二分找到下一个存在 id 的玩偶就行了。

我的算法可能有一点绕，但是实现还是挺简单的。时间复杂度高达 $\mathcal{O}(n{\log }^{2}n)$，当然也可以通过按照 $c$ 的权值线段树维护，然后直接在线段树上面二分，这样子就可以做到 $\mathcal{O}(n{\log }_{2}n)$。不过树状数组貌似也可以二分，不过我不会。

#include <iostream>
#include <algorithm>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 5e5 + 5;
 
struct Node {
  LL h, c, p, id;
 
  friend bool operator<(const Node &a, const Node &b) {
    return a.id < b.id;
  }
} a[kMaxN];
 
LL sum[kMaxN], cnt[kMaxN], trp[kMaxN], trc[kMaxN], f[kMaxN], ori[kMaxN], n, ans = 1e18;
 
void modify(LL x, LL p, LL c) {
  for (; x <= n; x += x & -x) {
    trp[x] += p;
    trc[x] += c;
  }
}
 
LL queryP(LL x) {
  LL res = 0;
  for (; x; x -= x & -x) {
    res += trp[x];
  }
  return res;
}
 
LL queryC(LL x) {
  LL res = 0;
  for (; x; x -= x & -x) {
    res += trc[x];
  }
  return res;
}
 
// 目标：找到 c 最小的若干个玩偶，使总数量 >target，返回 c 的和
LL search(LL target) {
  LL ans = 1e18, p = 0;
  if (target < 0) {
    return 0;
  }
  if (queryP(n) <= target) {
    return 1e18;
  }
  for (LL l = 0, r = n; l <= r; ) {
    LL m = (l + r) / 2;
    if (queryP(m) <= target) {
      ans = queryC(m);
      l = m + 1;
      p = m;
    } else {
      r = m - 1;
    }
  }
  if (ans != 1e18) {
    LL now = queryP(p), nxt = 0;
    for (LL l = p + 1, r = n; l <= r; ) {
      LL m = (l + r) / 2;
      if (queryP(m) > now) {
        nxt = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    ans += (target + 1 - now) * a[ori[nxt]].c;
  }
  return ans;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i].h >> a[i].c >> a[i].p;
    f[a[i].h] += a[i].p;
  }
  sort(a + 1, a + n + 1, [](const Node &a, const Node &b) {
    return a.c < b.c;
  });
  for (LL i = 1; i <= n; i++) {
    a[i].id = i;
  }
  sort(a + 1, a + n + 1, [](const Node &a, const Node &b) {
    return a.h < b.h;
  });
  for (LL i = n; i >= 1; i--) {
    sum[i] = sum[i + 1] + a[i].p * a[i].c;
  }
  for (LL i = 1; i <= n; i++) {
    cnt[i] = cnt[i - 1] + a[i].p;
    ori[a[i].id] = i;
  }
  for (LL i = 1, j = 1; i <= n; i++) {
    if (a[i].h == a[i + 1].h) {
      continue;
    }
    for (; j <= n && a[j].h < a[i].h; j++) {
      modify(a[j].id, a[j].p, a[j].p * a[j].c);
    }
    ans = min(ans, search(cnt[i] - 2 * f[a[i].h]) + sum[i + 1]);
  }
  cout << ans << '\n';
  return 0;
}

无人机

最短路 二分

本题我的算法会 TLE。

由于决策方案有很多种：移动、不移动调整高度、边移动边调整高度，bfs 状态是有三次方级别的，即使使用 dijkstra 将第三维耗时，状态也是二维的。精简状态显然不合理，如果将高度压掉就会导致答案错误，毕竟 $a_i$ 会限制它。

易得答案满足单调性，因此我们可以考虑二分答案。假设我们需要判断能否在 $T$ 时间内到达终点，那么设计一个状态 $(u,t)$ 表示无人机到达 $u$ 的最早时刻是 $t$。

转移时，$a_i$ 的限制会令人头疼。但是我们记录了到达 $u$ 的最小时刻是 $t$，在这 $t$ 的时间内我们都是可以上升高度的。假设当前要飞行到 $i$，那么我们在 $t+1$ 到达时高度至少为 $a_i$，如果达不到就必须额外在前面的节点时增加高度。

因此，到了 $i$ 时，我们新的时间是 $\max (t+1,a_i)$。但是我们还需要考虑一点：题目规定到达 $n$ 时高度必须降为 $0$ 才能结束，而我们之前的算法都是使无人机上升的，怎么搞定这个问题呢？

到达 $i$ 时，由于我们之前每个时间都会增加高度，因此我们的高度是 $\max (t+1,a_i)$，而我们需要额外的 $a_i$ 时间下降到 $0$，因此需要额外增加一个条件：$\max (t+1,a_i)+a_i\le T$。最后，如果 $n$ 被我们标记了距离，就返回可行，否则返回不可行。

时间复杂度 $\mathcal{O}((n+m){\log }_2(n+m){\log }_{2}V)$，然后我就 TLE+WA 了。WA 的原因是答案最大是 $2\max a_i+n$，而我的代码中二分的最大值仅有 $2\times 10^8$。TLE 纯属算法不行。

正解是两遍 dijkstra。

#include <iostream>
#include <vector>
#include <queue>
#include <map>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
LL a[kMaxN], d[kMaxN], f[kMaxN], n, m, mx, ans;
priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<pair<LL, LL>>> q;
vector<LL> e[kMaxN];
 
bool check(LL T) {
  fill(d + 2, d + n + 1, 1e18);
  for (; q.size(); q.pop()) { }
  for (q.emplace(d[1] = 0, 1); q.size(); ) {
    LL t = q.top().first, u = q.top().second;
    q.pop();
    if (t > d[u]) {
      continue;
    }
    if (u == n) {
      return 1;
    }
    for (LL i : e[u]) {
      LL x = max(t + 1, a[i]);
      if (x <= T - a[i] && x < d[i]) {
        d[i] = x;
        q.emplace(d[i], i);
      }
    }
  }
  return 0;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
    mx = max(mx, a[i]);
  }
  for (LL i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  for (LL l = 0, r = 2e8; l <= r; ) {
    LL m = (l + r) / 2;
    if (check(m)) {
      ans = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

交集

序列dp 单调队列 集合

本题我的解法是错误的。

首先假如我们是将长度为 $n$ 的序列切成 $k$ 个连续的块，那么我们可以很轻松地使用 $\mathcal{O}(n^3)$ dp 解决。先预处理 $i\sim j$ 的所有区间的交集长度 $w_{i,j}=\underset{p=i}{\overset{j}{\min }}{R}_p-\underset{p=i}{\overset{j}{\max }}{L}_p+1$。设 $d{p}_{i,j}$ 表示为前 $i$ 个区间分成了 $j$ 块的最大值，那么可以枚举最后一块的左端点进行转移：

$$d{p}_{i,j}=\underset{p=0}{\overset{i-1}{\max }}\left(d{p}_{p,j-1}+w_{p+1,i}\right)$$

答案就是 $\mathcal{O}(n^{2}k)$。但是题目要求时间复杂度最多 $\mathcal{O}(nk)$，因此我们可以进行四边形不等式优化。猜测或打表发现 $w$ 运算满足四边形不等式，然后还满足区间包含单调性，因此我们可以使用四边形不等式优化 dp，使其时间复杂度缩至 $\mathcal{O}(nk)$。

那么怎么对区间进行排序呢？我是瞎排的，因此直接 WA。

总结

本次得分：$100+100+45+10=255$

问题：第三题没有注意时间复杂度和答案范围，导致挂 $45$ 分。第二题写代码时不够仔细，导致调代码调了两个小时，使我没有时间想最后一题获得更多分数。

解决方案：减缓写代码速度，减少调试时间，写完检查代码，注意数据范围。