2024.10.10 模拟赛

题目：2024.10.10 题目

植物收集

一种植物有 $n$ 种生长阶段，你需要集齐所有生长阶段。第 $i$ 个生长阶段可以花费 $a_i$ 的钱购买，但是直接购买不一定是最便宜的。有神奇骨粉 $k$ 元撒一次，可以让已经购买的所有植物的生长阶段都向上一截，第 $n$ 阶段变成第 $1$ 阶段。

---

首先，假设我们已经知道了每种植物需要从什么基准植物购买开始撒骨粉后得到，我们又该如何安排撒骨粉的方案？很显然，我们先购买需要撒骨粉次数较多的植物，先把它们的骨粉撒完，使得它们剩余需要撒骨粉的次数一样，再把其它的植物买过来一起撒。所以，我们总结得到：撒骨粉的次数取决于需要撒最多次数骨粉的植物的撒骨粉次数。

但是我们很显然是不知道每种植物需要从什么开始成长，我们只需要最终答案最小即可。答案=购买植物的钱+撒骨粉的钱，我们不难想出将撒骨粉的最大次数 $t$ 单独提出来，快速得到撒骨粉的钱，然后令购买的每种植物在不超过撒 $t$ 次骨粉的情况下购买的价格尽量低。可以设计函数 $f(t)$ 表示最多撒 $t$ 次骨粉，所需要的最小钱数。总结得到 $f(t)=\sum _{i=1}^n\underset{j=i-t}{\overset{i}{\min }}{a}_j+t\times k$，其中求最小值部分可以使用 ST 表优化至 $\mathcal{O}(n{\log }_{2}n)$ 预处理，$\mathcal{O}(1)$ 询问，因此该函数的计算时间复杂度为 $\mathcal{O}(n)$。我们需要枚举 $t$，以求出最小的 $f(t)$，枚举的时间复杂度为 $\mathcal{O}(n)$，总时间复杂度为 $\mathcal{O}(n^2)$，可以通过 $80$ 分。

接下来我们考虑正解。对于这种给定限制求最值的问题，我们很容易想到答案可能会具有某些性质，如单调递增、递减，呈凹/凸函数……将 $f(t)$ 逐一输出，可通过大眼观察法得到 $f(t)$ 是一个凹函数，也就是有一个 $t$，任意 $t_0\le t$ 时 $f(t_0)$ 单调递减，任意 $t_1\ge t$ 时 $f(t_1)$ 单调递增，我们就需要找到 $f(t_0)\ge f(t)\le f(t_1)$ 的这个点，可以使用二分。每次我们对范围取中间的点 $m$，特判位于边界或已经满足条件，然后取它两边的点 $m-1$ 和 $m+1$，分别计算出 $f(m-1)$、$f(m)$、$f(m+1)$，以此来判断 $m$ 在最小值的左边还是右边，并移动左右指针即可。时间复杂度为 $\mathcal{O}(n{\log }_{2}n)$，可以获得 $100$ 分。

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5, kLog = 21;
 
ifstream cin("collect.in");
ofstream cout("collect.out");
 
LL dp[kMaxN][kLog], lg[kMaxN], n, k, ans = 1e18;
 
LL query(LL l, LL r) {
  LL k = lg[r - l + 1];
  return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
 
LL solve(LL x) {
  LL res = 0;
  for (LL i = 1; i <= n; i++) {
    LL val = query(max(1LL, i - x + 1), i);
    i < x && (val = min(val, query(n - (x - i) + 1, n)));
    res += val;
  }
  return res + (x - 1) * k;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  for (LL i = 1; i <= n; i++) {  
    cin >> dp[i][0];
  }
  for (LL j = 1; j < kLog; j++) {
    for (LL i = 1; i + (1 << j) - 1 <= n; i++) {
      dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (LL i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
  }
  for (LL l = 1, r = n; l <= r; ) {
    LL m = (l + r) >> 1;
    if (m == 1 || m == n) {
      ans = solve(m);
      break;
    }
    LL a = solve(m - 1), b = solve(m), c = solve(m + 1);
    if (a > b && b < c) {
      ans = b;
      break;
    } 
    if (a < b && b < c) {
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

美丽子区间

有长度为 $n$ 的序列 $a$，求 $a$ 的子区间 $[l,r]$ 满足 $a_l$ 与 $a_r$ 不是 $a_l\sim a_r$ 的最小值的数量。

---

使用暴力。枚举左端点 $l$，然后从 $l$ 开始逐一往右枚举 $r$，在枚举 $r$ 的过程中同时记录 $\underset{i=l}{\overset{r}{\max }}{a}_i$ 与 $\underset{i=l}{\overset{r}{\min }}{a}_i$，然后判断区间 $[l,r]$ 是否满足条件并累加计数器即可。时间复杂度为 $\mathcal{O}(n^2)$，成功获得 $40$ 分。

字符序列

有函数 $f(c,s)=c{s}_{1}c{s}_2\cdots c{s}_{|s|}c$，给定长度为 $n$ 的字符序列 $c$，求 $f(c_n,f(c_{n-1},f(\cdots ,f(c_2,f(c_1,S)))))$ 本质不同的非空子序列的数量，其中 $S$ 为空串。

---

首先，我们通过暴力求出需要求非空子序列的数量的序列，然后通过暴力 dfs 选择每一种字符该不该选择，最后用 set 记录不相等的子序列数量。时间复杂度 $\mathcal{O}(2^{2^n}\times 2^n)$，可以通过 $20$ 分。

网络攻防

有 $n$ 点 $m$ 边的连通无向图，第 $i$ 条边连接 $u_i$ 与 $v_i$。可以删除最多 $k$ 条边，使图不再连通。求删除的方案数。

---

采用分 $k$ 处理。当 $k=1$ 时，大力用 Tarjan 求桥 $\mathcal{O}(n+m)$ 得 $10$ 分。对于 $k=2$，好渴鹅发现枚举删除的一条边后不能直接通过 Tarjan 求桥，因为图可能不连通，因此好渴鹅启动暴力。暴力枚举哪两条边被删除，对于没有被删除的边就使用并查集合并连通块，最后看一下整个图是否不是一个连通块。时间复杂度 $\mathcal{O}(m^3\alpha (n))$。

总结

• 排名：$8$；
• 比赛分数：$180/400$；
• 情况：相比 2024.10.9 模拟赛，一般；
• 问题：不会熟练使用容斥，集合 dp 水平太菜。