2025.9.22 模拟赛

夺宝奇猫

首先我们需要构建一条 $1 \sim n$ 和一条 $n \sim 1$ 的路径，这两个路径涵盖了所有的点组并且不重复。很显然后面 $n \sim 1$ 也等同于 $1 \sim n$ ，因此我们需要构建两条 $1 \sim n$ 的路径。

考虑相邻编号点 $i$ 和 $i + 1$ 之间的路径方式，只有两种 $(i_{0}, (i + 1)_{0})$ $(i_{1}, (i + 1)_{1})$ 和 $(i_{0}, (i + 1)_{1})$ $(i_{1}, (i + 1)_{0})$ 。因此我们只需要选择距离和最小的那一种，累加起来再额外加上第 $n$ 组点的贡献就行了。

时间复杂度 $O (n)$ 。

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("treacat.in");
ofstream cout("treacat.out");
 
LL x[kMaxN][2], y[kMaxN][2], n, m, ans;
 
LL dis(LL x1, LL y1, LL x2, LL y2) {
  return abs(x1 - x2) + abs(y1 - y2);
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL i = 1; i <= n; i++) {
    for (LL j = 0; j <= 1; j++) {
      cin >> x[i][j] >> y[i][j];
    }
  }
  for (LL i = 1; i < n; i++) {
    ans += min(dis(x[i][0], y[i][0], x[i + 1][0], y[i + 1][0]) + dis(x[i][1], y[i][1], x[i + 1][1], y[i + 1][1]),
               dis(x[i][0], y[i][0], x[i + 1][1], y[i + 1][1]) + dis(x[i][1], y[i][1], x[i + 1][0], y[i + 1][0]));
  }
  cout << ans + dis(x[n][0], y[n][0], x[n][1], y[n][1]) << '\n';
  return 0;
}

爬山

最短路优先队列

海拔上升会减少体力，海拔下降会增加体力，但是任意时刻体力不能为负，而 $h_{1}$ 不能改变（且改变了也不优），因此实际上可以走的海拔区间为 $(- \infty, h_{1} + k]$ 。对于路径上所有在区间之外的海拔，需要额外增加 $(h - h_{1} - k)^{2}$ 的代价。因此直接跑 dijkstra 额外增加贡献就行了。

时间复杂度 $O (m lo g_{2} m)$ 。

#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
ifstream cin("climb.in");
ofstream cout("climb.out");
 
struct Node {
  LL to, v;
 
  Node(LL to, LL v):
    to(to), v(v) { }
 
  friend bool operator<(const Node &a, const Node &b) {
    return a.v > b.v;
  }
};
 
LL a[kMaxN], f[kMaxN], d[kMaxN], n, m, k;
vector<Node> e[kMaxN];
priority_queue<Node> q;
 
LL sqr(LL x) {
  return x * x;
}
 
void bfs() {
  fill(d + 2, d + n + 1, 1e18);
  for (q.emplace(1, 0); q.size(); q.pop()) {
    auto t = q.top();
    if (f[t.to]) {
      continue;
    }
    f[t.to] = 1;
    for (auto i : e[t.to]) {
      LL v = d[t.to] + i.v + sqr(max(0LL, a[i.to] - a[1] - k));
      if (v < d[i.to]) {
        d[i.to] = v;
        q.emplace(i.to, d[i.to]);
      }
    }
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (LL i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    e[u].emplace_back(v, w);
    e[v].emplace_back(u, w);
  }
  bfs();
  cout << d[n] << '\n';
  return 0;
}

排列

序列dp 前缀和

首先很容易想到简单的动态规划，设 $d p_{i, j}$ 表示为对于长度为 $i$ 的已构建排列，最后一个元素是 $j$ 的方案数。但是选择下一个数的时候无法判断是否已经被选过，为了避免这种情况我们将 $j$ 改为在已选排列中的排名。

设 $d p_{i, j}$ 表示最后一个元素的排名为 $j$ ，那么转移和之前是一样的进行，也是非常的简单。增加前缀和优化把时间复杂度 $O (n^{3})$ 变成 $O (n^{2})$ ，并加上滚动数组优化防止炸空间。

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e4 + 5, kMod = 1e9 + 7;
 
ifstream cin("perm.in");
ofstream cout("perm.out");
 
LL dp[kMaxN], prv[kMaxN], sum[kMaxN], n, ans;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  prv[1] = sum[1] = 1;
  for (LL i = 2; i <= n; i++) {
    for (LL j = 1; j <= i; j++) {
      if (i % 2 == 0) {
        dp[j] = (sum[i - 1] - sum[j - 1] + kMod) % kMod;
      } else {
        dp[j] = sum[j - 1];
      }
    }
    for (LL j = 1; j <= i; j++) {
      sum[j] = (sum[j - 1] + dp[j]) % kMod;
    }
    copy(dp + 1, dp + i + 1, prv);
  }
  for (LL i = 1; i <= n; i++) {
    ans = (ans + dp[i]) % kMod;
  }
  cout << ans << '\n';
  return 0;
}

夺宝奇鱼

线段树排序贪心

首先由于限制对于所有怪兽都是启用的，因此可以枚举这个限制。枚举 $i$ 表示所有怪兽手上剩余的物品数量都小于 $i$ ，此时我们购买的物品数量就需要大于等于 $i$ 。从大到小枚举 $i$ ，这样每次都会把一些怪物手上的已有的物品删除。

现在我们让所有怪物都满足了 $i$ 的限制，但是自己手上可能还不到 $i$ 个物品。此时需要在怪物手上继续购买剩余的物品，肯定是优先购买便宜的，然而怪物手上的物品是越删越少的，因此可以使用权值线段树维护怪物手上的剩余物品，补充剩余的就在权值线段树上面二分就行了。

时间复杂度 $O (m lo g_{2} m)$ 。注意需要进行离散化否则会 MLE。

#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e6 + 5;
 
ifstream cin("treasure.in");
ofstream cout("treasure.out");
 
struct Node {
  LL cnt, sum;
} tr[4 * kMaxN];
 
LL val[kMaxN], n, m, q, cnt, use, buy, ans = 1e18;
vector<LL> v[kMaxN], id[kMaxN], rm;
multiset<LL> s;
 
void modify(LL p, LL l, LL r, LL x, LL d) {
  tr[p].cnt += d;
  tr[p].sum += val[x] * d;
  if (l == r) {
    return;
  }
  LL m = (l + r) / 2;
  if (x <= m) {
    modify(2 * p, l, m, x, d);
  } else {
    modify(2 * p + 1, m + 1, r, x, d);
  }
}
 
LL query(LL p, LL l, LL r, LL k) {
  if (l == r) {
    return val[l] * k;
  }
  LL m = (l + r) / 2, cnt = tr[2 * p].cnt;
  if (k <= cnt) {
    return query(2 * p, l, m, k);
  }
  return tr[2 * p].sum + query(2 * p + 1, m + 1, r, k - cnt);
}
 
LL getHash(LL x) {
  return lower_bound(val + 1, val + q + 1, x) - val;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL i = 1, a, c; i <= m; i++) {
    cin >> a >> c;
    v[c].push_back(a);
    val[++q] = a;
  }
  sort(val + 1, val + q + 1);
  q = unique(val + 1, val + q + 1) - val - 1;
  for (LL i = 1; i <= n; i++) {
    if (v[i].empty()) {
      continue;
    }
    for (LL &j : v[i]) {
      j = getHash(j);
      modify(1, 1, q, j, 1);
    }
    sort(v[i].begin(), v[i].end(), greater<>());
    id[v[i].size()].push_back(i);
  }
  // 所有怪物剩余物品数小于 i，购买数大于等于 i
  for (LL i = m; i >= 1; i--) {
    for (LL j : id[i]) {
      rm.push_back(j);
    }
    for (LL j : rm) {
      buy += val[v[j].back()];
      modify(1, 1, q, v[j].back(), -1);
      v[j].pop_back();
      use++;
    }
    ans = min(ans, buy + query(1, 1, q, max(0LL, i - use)));
  }
  cout << ans << '\n';
  return 0;
}

总结

总分： $100 + 100 + 100 + 100 = 400$ 。

第一、二、四题都做得很快，思路也不难想，就是第三题太糖了一个多小时才做出来。

Haokee Note

Explorer

2025.9.22 模拟赛

夺宝奇猫

爬山

排列

夺宝奇鱼

总结

Graph View

Table of Contents