2022 年上海市大学生程序设计竞赛 - 十一月赛 题解

oxx1108 edited 2 月,1 周前

A

最小值为 $1$,按顺序排列即可,除了最大数以外相邻的数必有一个大于等于它。

最大值为 $\lceil\frac{n+1}{2}\rceil\lceil\frac{m+1}{2}\rceil$,将最大的这些数排在所有行列均为奇数的格子即可。因为 $2*2$ 方格内至多只有一个 peak number,通过染色可知最大值。

B

解法一

将每一列存在 bitset 或二进制位中,$m^2$ 暴力枚举所有匹配方案,复杂度 $O(nm^2)$。利用 bitset 或者二进制位即可通过此题。

解法二

首先,由每一列第一行决定列的正反(保证第一行全变为 $1$)。然后对所有列进行排序,排序之后则可一一匹配。

利用 map 也可以,复杂度$O(nm\log m)$,不用 bitset 也能通过此题。

C

对于 $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)$ 就能通过这个题了。

当然如果你硬要正着做,容斥也是能做的,就是麻烦点。

Note

原先这个题的设置数据范围要更大,必须要 $O(3^k)$ 才能通过这个题,为了降低难度砍掉了数据范围几个 0。

D

解法一

随机将所有数分为六个数一组,通过比较选择每六个数中最大的两个数即可。注意,三个数中取最大不行,此时的总和大于一半的概率仅为$50\%$。

解法二

选出 $[\frac{7n}{4},2n]$ 中任意一个数之后,通过 $3n$ 次比较即可筛选出比其大的数,在其中随机选出 $n$ 个数必定大于一半。可以通过快速选择来找$\frac{15n}{8}$,但是直接快速选择比较次数不能限制在 $3n$ 之内。

因此可以随机选出 $\frac{3n}{logn}$ 个数中通过快速选择来找对应的数。也有其他方法可以找到。

Note

解法一解法二均仅在大数据情况下概率正确,在小数据时无法得到严格保证。还有许多其他解法,可以自行探索。

E

考虑点分治,对两棵树分别进行质心分解。

假设两个节点 $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)$ 。

Comments