Lunch Concert
题面
P9025 CCC2021 S3 Lunch Concert ( 圆身 Genshin )
有 $n$ 个人在一条线上 , 初始位置为 $p_i$ , 移动一个单位长度的代价为 $w_i$ . 选定一个点 $c$ , 产生的代价为 $\sum_i^n w_i \times \max{(\lvert c - p_i \rvert - d_i , 0)}$ . 最小化这个代价 .
解题思路
完全随机算法狂砍 80pts . 出题人大好人 ( 雾 .
把一个人转化为一个线段 $[p_i - d_i,p_i + d_i]$ , 若要移动则 $c < p_i - d_i$ 或 $c > p_i + d_i$ .
于是得到单峰函数 . 二 / 三分或者模拟退火就行 .
MEX vs MED
题面
CF1744F MEX vs MED ( 弄药 Arena )
给定一个序列 $a$ , 值域为 $[0,n - 1]$ , 下标范围为 $[1,n]$ . 求有多少区间 [l,r] 满足 $\operatorname{mex}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r) \le \operatorname{med}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r)$ ( 原题为 ( $\operatorname{mex}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r) > \operatorname{med}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r)$ ) .
$\operatorname{mex}(S)$ 为没有在 $S$ 中出现的最小非负整数 .
$\operatorname{med}(S)$ 为 $S$ 从小到大排序后 $S_{\left\lfloor{\frac{\lvert S \rvert + 1}{2}}\right\rfloor}$ 的值 .
解题思路
定义 $list_i$ 表示 $i$ 出现的位置 , 即 $list_{a_i} = i$ . 若区间 $[l,r]$ 的 $\operatorname{mex} = d$ , 则必有 $l \le \min_{i \le d} list_i $ 并且 $r \geq \max_{i \le d} list_i$ .
对于每个 $\operatorname{mex} = d$ 只需考虑长度为 $d \times 2$ 和 $d \times 2 - 1$ 的区间个数 , 长度为 $d \times 2 - 2$ 的区间一定在 $\operatorname{mex}$ 的值为 $d - 1$ 的时候统计过 .
复杂度 $O(n)$ .
PRE-Prefixuffix
题面
对于两个串 $S$ , $T$ . 将 $S$ 的一个前缀移动到其末尾等于 $T$ , 则 $S$ 和 $T$ 循环相同 .
给定串 $S$ , 求最大的 $L$ ( $L \le \dfrac{n}{2}$ ) , $S$ 的 $L$ 前缀与 $S$ 的 $L$ 后缀是循环相同的 .
解题思路
一般考虑循环相同会复制串 $A$ 两边得到 $AA$ , 从中寻找串 $B$ . 不过这道题这样做复杂度爆炸 .
两个循环相同的串可以表示为 $AB$ , $BA$ . 则题目等价于把原串表示为 $ABSBA$ 的形式下最长的 $AB$ .
令 $B = a B^\prime c$ , 那么原串可写为 $A a B^\prime c S a B^\prime c A$ , 就可以分为 $A a \lvert B^\prime \rvert c S a \lvert B^\prime \rvert c A$ .
$f_i$ 表示 $A$ 取 $S_{[1 , i]}$ 时最长的 $B$ . ( $S_{[i + 1 , i + f_i]} = S_{[n - i - f_i , n - i - 1]}$ ) . 由此可知 : $f_{i + 1} \ge f_i - 2$ , 存在单调性 . 初值为 $f_{\lfloor \frac{n}{2} \rfloor}$ , 考虑从 $f_{i + 1}$ 往回计算 $f_i$ . $f_i \le f_{i + 1} + 2$ . 统计最大值即可 . 复杂度 $O(n)$ .