题解：[[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)=cs_1cs_2\cdots cs_{|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$ 条边，使图不再连通。求删除的方案数。