2024.10.10 题目

题解：2024.10.10 模拟赛

植物收集

二分 函数 ST表

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

美丽子区间

树状数组 单调栈

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

字符序列

矩阵 序列dp

有函数 $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$ 为空串。

网络攻防

随机化 生成树 桥

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