Revethere's Blog

数学 Math

题面

在射线 $ON$ 上有两个定点 $A$ , $B$ . 在射线 $OM$ 上取一点 $P$ , 使得 $\angle APB$ 最大 ( 有且只有一个解 ) . 求点 $P$ 的坐标 .

解题思路

如图 , 构造以点 $P$ , $A$ , $B$ 为外接圆且 $OM$ 与点 $P$ 相切 . 此时 $\angle APB$ 最大 .

证明过程 : 在 $OM$ 上任取一点 $Q$ , 设 $AF$ 与 $\odot QAB$ 交于点 $Q^\prime$ , 则 $\angle AQB < \angle AQ^\prime B$ .

求点 $Q$ 的坐标可以用相似 , ${OE}^2 = OA \times OB$ . 求出 $OQ$ 长即可 .

你所热爱的就是你的生活 ll

题面

给定一个序列 $price$ , 从序列内任取若干个数 , 使得价值和不超过 $m$ . 求方案总数 .

解题思路

折半搜索 , $l$ 和 $r$ 分别统计左右价值 , 去掉不满足条件的即可 .

家人 Family

题面

在一个 $2 \times n$ 的迷宫中有 2 种状态 , 能走和不能走 . 求给定两点 $u$ , $v$ 的最短路 .

解题思路

线段树维护 $[l , r]$ 列的 $2 \times (r - l + 1)$ 的左上到右上 / 下 , 左下到右上 / 下的最短路的值 .

对两个节点的答案合并 , 经过 $(0 , mid)$ 和 $(1 , mid)$ 的 $\min$ .

网格行走 Path

题面

有一个 $n \times m$ 的网格 , 第 $i$ 行第 $j$ 列写有一个数 $a_{i,j}$ ( 从 0 开始 ) , 每个数仅出现一次 .

一条行走路径的价值为所有经过的点的集合的 $\operatorname{mex}$ 的值 .

定义一个集合的 $\operatorname{mex}$ 的值为最小的没有在集合中出现的非负整数 .

解题思路

要想 $\operatorname{mex}$ 的值大于等于 $d$ , 那么需要经过 $0 \ldots d$ 的所有点 .

非法方案是需要两个点即可 : $x_1 < x_2$ , $y_1 > y_2$ . 对于任意一个的点来说 , 在以它为原点的第 1 象限和第 3 象限的点都是非法的 . 数据结构判断 :

• Method 1 : 二分答案 $d$ , 将对应点排序 , 以 $x$ 为第一关键字 , $y$ 为第二关键字 , 相邻点满足 $x$ , $y$ 均不降即可 ( 不需要真正的排序 ) . 复杂度 $O(nm \log nm)$ .
• Method 2 : 动态加点判断 , 复杂度 $O(nm \log n)$ . ( 目前不会 ＞﹏＜

计数练习 Perm

题面

统计有多少 $m$ 阶排列比自己的逆排列的字典序小 .

即 $q(p)_{p_i} = i$ 并且存在一个 $i$ 使得 $\forall 1 \le j < i$ , $p_j = q(p)_j$ 且 $p_i < q(p)_i$ .

解题思路

排列的逆变换是有规律的 , 即 $q(q(p)) = p$ . 从 $p$ 和 $q(p)$ 来看 , 有关字典序的关系是相反的 , 所以只要 $q(p) \not = P$ , $(P , q(P))$ 就会对答案产生贡献 .

统计 $n$ 阶排列的数量 , 发现所有轮换大小不超过 2 的排列的逆排列就是它自己 . 记这样的 $n$ 阶排列的数量为 $f_n$ . 则 :

$$f_n = f_{n - 1} + (n - 1) \times f_{n - 2}$$

$$v_i = \dfrac{(i! - f_i)}{2}$$

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

题面

P3546 POI2012 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)$ .