杂题

【YBOJ】 Pair

题目描述

给出二维平面上的 \(n\) 个点，第 \(i\) 个点的坐标为 \(x_i,y_i\) 。
定义点 \(i\) 与点 \(j\) 之间的距离为 \(\frac{|x_i-x_j|+|y_i-y_j|}{\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}}\) ，求平面上两点的距离最大为多少。（$ 1 \le n \le 10^5$）

解题思路

首先，我们可以发现两点之间的距离最大为 \(\sqrt{2}\) ，在 \(|x_i-x_j|\) 与 \(|y_i-y_j|\) 接近的时候最大。
这就说明两点的连线在最接近 \(45\) 度的时候距离最大。
我们可以把所有点绕原点转 \(45\) 度，将原点坐标变为 \((\frac{x_i+y_i}{2},\frac{x_i-y_i}{2})\) ，这样我们只需找两点使它们的连线斜率接近 \(0\) 或 \(1\)。
容易发现，满足条件的点它们总有一维排序之后是连续的，那我们可以分别按 \(x\) 坐标排序一次，\(y\) 坐标排序一次，两次排序分别检查前后两点的距离。
时间复杂度 \(O(nlogn)\) 。

【YBOJ】 Tree

题目描述

有 \(n\) 个点，下标分别为 \(0,1,...,n-1\) ，给出参数 \(k\) ，每次操作可一将点 \(u\) 与点 \(v\) ，点 \((u+k)\% n\) 与点 \((v+k)\% n\) 连上。
你要构造一棵树，树中包含 \(n\) 个节点，找出一种可行方案并输出或输出 \(-1\) ，\(1 \le n \le 10^6\)。

解题思路

首先 \(n\) 为偶数的时候肯定是不存在方案的，输出 \(-1\) 。
考虑 \(gcd(n,k)=1\) 时候的情况，我们可以按 \((0,k)\) ，\((2k\% n,3k\% n)\) 连的顺序连完，直接这样输出即可。
考虑 \(gcd(n,k)=m\) 的情况。
我们可以构造一个矩阵有 \(m\) 行 \(n/m\) 列，一列里面的数 \(+k\) 可以变成下一列数。
我们可以把每个数与位于它右下角的数给连上，那么我们可以发现形成了一条条往右下角延伸的直线，只需把上下连接在一起即可。