Revethere's Blog

手语的 Gnsi

题面

给定三个正交矩形和一个点 , 问是否存在一个三角形 , 使得该三角形的三个顶点分别在三个正交矩形内且该三角形的重心为给定点 .

解题思路

重心 $G = (\dfrac{x_1 + x_2 + x_3}{3} , \dfrac{y_1 + y_2 + y_3}{3})$ . 加上两个边界 :

• $x_G = \begin{bmatrix} \dfrac{minx_1 + minx_2 + minx_3}{3} + \dfrac{maxx_1 + maxx_2 + maxx_3}{3} \end{bmatrix}$

• $y_G = \begin{bmatrix} \dfrac{miny_1 + miny_2 + miny_3}{3} + \dfrac{maxy_1 + maxy_2 + maxy_3}{3} \end{bmatrix}$

数学 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}$$