oxx1108 edited 2 年前
最小值为 $1$，按顺序排列即可，除了最大数以外相邻的数必有一个大于等于它。
最大值为 $\lceil\frac{n+1}{2}\rceil\lceil\frac{m+1}{2}\rceil$，将最大的这些数排在所有行列均为奇数的格子即可。因为 $2*2$ 方格内至多只有一个 peak number，通过染色可知最大值。
将每一列存在 bitset 或二进制位中，$m^2$ 暴力枚举所有匹配方案，复杂度 $O(nm^2)$。利用 bitset 或者二进制位即可通过此题。
首先，由每一列第一行决定列的正反（保证第一行全变为 $1$）。然后对所有列进行排序，排序之后则可一一匹配。
利用 map 也可以，复杂度$O(nm\log m)$，不用 bitset 也能通过此题。
对于 $GCD=1$ 且 $LCM=n$ 的集合显然只能由 $n$ 的约数构成，假设 假设 $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ 其中 $p_1,p_2\cdots p_k$ 均为质数。
可以考虑用排除法来计数。首先是 $GCD\neq 1$ 的情况，即 $GCD$ 可以被 $n$ 的某一个质因数 $p_i$ 整除；然后是 $LCM\neq n$ 的情况，，显然 $LCM$ 就是满足不被某个 $p_i^{a_i}$ 整除。
所以对于 $n$ 的每一个质因数，我们只需要考虑四种情况，直接 $O(4^k)$ 就能通过这个题了。
当然如果你硬要正着做，容斥也是能做的，就是麻烦点。
原先这个题的设置数据范围要更大，必须要 $O(3^k)$ 才能通过这个题，为了降低难度砍掉了数据范围几个 0。
随机将所有数分为六个数一组，通过比较选择每六个数中最大的两个数即可。注意，三个数中取最大不行，此时的总和大于一半的概率仅为$50\%$。
选出 $[\frac{7n}{4},2n]$ 中任意一个数之后，通过 $3n$ 次比较即可筛选出比其大的数，在其中随机选出 $n$ 个数必定大于一半。可以通过快速选择来找$\frac{15n}{8}$，但是直接快速选择比较次数不能限制在 $3n$ 之内。
因此可以随机选出 $\frac{3n}{logn}$ 个数中通过快速选择来找对应的数。也有其他方法可以找到。
解法一解法二均仅在大数据情况下概率正确，在小数据时无法得到严格保证。还有许多其他解法，可以自行探索。
考虑点分治，对两棵树分别进行质心分解。
假设两个节点 $i$, $j$ 在两棵质心树上的 LCA 分别是 $L_1$ 和 $L_2$，那么可以发现 $$dist(T_1,i,j)+dist(T_2,i,j)=dist(T_1,L_1,i)+dist(T_1,L_1,j)+dist(T_2,L_2,i)+dist(T_2,L_2,j)$$
我们知道在质心树上，每个节点最多有 $\log n$ 个祖先，也就是说，如果我们可以考虑枚举 $i$，那么 LCA 的组合最多有 $\log^2n$ 个，然后去考虑找对应的 $j$ 。
即问题变成了给定节点 $i,L_1,L_2$，找到一个节点 $j=i$ 使得 $dist(T_1,L_1,j)+dist(T_2,L_2,j)$ 最小，而且 $i,j$ 的 LCA 恰好是 $L_1,L_2$ 。
可以发现有 LCA 这个限制其实不好做。但有一个套路是，我们可以直接枚举子树 $T_1$ 和 $T_2$ 中的所有的顶点，即 $dist(T_1,L_1,x)+dist(T_2,L_2,x)$，$x$ 是子树$T_1$ 和 $T_2$ 中的节点。
因为我们枚举了所有的顶点，所以显然有得到的答案一定小于等于正确答案，而且可以注意到如果这个找到的 $x$ 不满足 LCA 的要求，那么 $x$ 和 $i$ 的 LCA 一定是 $T_1$ 和 $T_2$ 孩子，即 $dist$ 肯定大于或者等于正确答案。有了上下的约束，所以找到的答案一定就是正确的。
所以总体时间复杂度 $O(n\log^2n)$ 。