2019.5 月赛题解

Xiejiadong edited 2 年,5 月前

花絮

# Tag Idea Developer Tester
A DFS LCA 染色 Xiejiadong Xiejiadong zerol
B 数学 Weaver_zhu Weaver_zhu Xiejiadong
C 找规律 数学 Kilo_5723 Kilo_5723 Weaver_zhu
D 乱搞 Xiejiadong Xiejiadong Weaver_zhu
E 计算几何 Kilo_5723 Kilo_5723 NULL

Problem A

First Solved:UoA_ZQC

对于一组需要联通的点对 $(a,b)$ ,设 $LCA(a,b)=c$ ,如果要保证 $a$ 到 $b$ 联通或者 $b$ 到 $a$ 联通,显然应该满足 $a$ 到 $c$ 的所有边同向, $b$ 到 $c$ 的所有边同向,而且 $a$ 到 $c$ 的边的方向和 $b$ 到 $c$ 的边的方向相反。

于是我们考虑把 $a$ 到 $c$ 的所有边标记为 $0$ , $b$ 到 $c$ 的所有边标记为 $0$ ,同时加一条边,从 $a$ 直接连到 $b$ ,标记为 $1$ 。

这样以来就变成了染色问题,要求边为 $1$ 的两个点颜色要不同,边为 $0$ 的点颜色要相同。

染色部分可以直接用 dfs 解决,也可以并查集维护每个同色链上的最高点(合并的时候往上面合并)。

对于互相相关的一堆点,显然确定了一个点的颜色以后就能推出其他所有点的颜色了。对于每个互相相关的块判断是否可行即可。

Problem B

First Solved:gyz_gyz

平凡的情况:$a=c,b=d$ 或 $a=c=1$ 。

其他的情况:$a\not = c$,表示为 $x^{kk(b’)}=x^{k(d’)}, kk \le k \le 32$ 其中 $a=x^{kk}, c=x^k$ 。

显然 $k\le 32$ ( $2^{32}>10^9$ ),然后 $gcd(kk, k)=1$ 才能保证不重复计数。分别针对 $a_{max}, c_{max}$ 二分出所有不等于 $1$ 的 $x$ 再根据 $b_{max}, d_{max}$ 求出满足的 $b’, d’$ ,把两类情况合起来就是答案。

Problem C

First Solved:dreamoon

可以发现求k重前缀和有一个和杨辉三角很像的模式:$f[i][j] = f[i][j-1]+f[i-1][j]$。如果考虑每个数在答案贡献的次数,那么初值就也符合组合数的形式了(初值是 $1$ )。(当然你也可以打表找出规律)。

答案的式子是$\sum\limits_{i=1}^{n} C_{k+n-i-1}^{k-1} \times a_i$ 。

然后就是求组合数了。模数很小,预处理阶乘发现乘上$p$的倍数就无意义了。这里的其中一个方法是预处理阶乘,把 $p$ 单独拎出来,分子分母约掉再考虑。

PS : 据说出题人有 $O(p^2+n)$ 的做法,并且卡掉了裸的 lucas 定理。

Problem D

First Solved:gyz_gyz

显然,如果位置 $i$ 上的数为 $a_i$ ,而 $i\neq a_i$ ,如果我们要让数 $a_i$ 回到位置 $a_i$ 翻转的对称轴是固定的。

于是我们对于每一个 $i\neq a_i$ 可以得到他们翻转时候的对称轴和翻转子数列的长度。

枚举对称轴。一个最优解恰好包含了一个 $i\neq a_i$ ,于是只需要枚举对称轴为当前的翻转区间。

一个翻转操作不仅会让对称轴为当前的所有 $i\neq a_i$ 变成满足要求的 ,同时也会使得被包含在翻转区间内本来满足要求的 $i=a_i$ 变成不满足要求的。所以翻转一个子数列会同时改变这两个值。

对于被包含在翻转区间内本来满足要求的 $i=a_i$ 可以通过前缀和的处理 $O(1)$ 得到。而对于对称轴为当前的所有 $i\neq a_i$ ,按照翻转子数列的长度枚举即可。

因为每一个 $i\neq a_i$ 都会产生针对一个对称轴的翻转,显然 $i\neq a_i$ 最多有 $n$ 个 ,所以枚举的总翻转区间数量是 $n$ 个。

Problem E

First Solved:404 Not Found .

这题的灵感来自于中山大学校赛读错的题面。

我们只关心两个多边形被 $y=y_0$ 直线截取的长度 $len(y_0)$,因此把两个多边形都按照节点 $y$ 坐标排序,统计有向边的斜率和,特判有向边与 $y=y_0$ 平行的情况。

我们发现,$len(y_0)$ 是一个分段函数,且每一段都是一次函数。

现在,我们要求 $len1(y_0) \cdot len2(y_0)$ 的积分,可以从左到右枚举两个函数的每一段,然后求两个一次函数的积分,加到答案里。

注意在统计斜率和时,要删除已经不在答案中的有向边。

Comments

Kilo_5723 :最后只有昨天尝试拉来的验题人做了 E 。

恭喜 gyz_gyz dreamoon UoA_ZQC 冠亚季军。

Comments

TeacherKun

各位D题是怎么空间换时间的?那位dalao给个AC代码,实在是想不出来

Xiejiadong

D 题没有空间换时间的操作呀。

__Archer

B题没懂呜呜,可以将做法解释的详细一些吗,个人觉得B题题解写得太简略了。

Weaver_zhu

$a=c, b=d$ 或者 $a=b=1$ 是很容易统计的,无论如何都符合等式。

首先 $a^b,c^d$ 从素因数分解看,每个素因子系数都要是相同的才能相等。得出如果 $a\not =b \ \ a,b > 1 \Rightarrow a=x^{kk}, b=x^{k}, (1 \le kk, k \le 32)$ 即底数的素因子结构必须是相同的。然后就是 $gcd(kk,k)=1$ 否则会产生重复计数的情况。这里枚举 $kk, k$ 就行了,这样枚举的情况就是 $a=x^{kk}, b=b’, c=x^k, d=d’, x^{kkb’}=x^{kd’}$ 。剩下的就是根据输入的四个数确定 $x(x^{kk}\le a_{max}, x^{k} \le b_{max}), b’,d’(b’\cdot kk = d’ \cdot k)$ 复杂度应该是 $O(32^2logn)$

__Archer

谢谢您的回复,我再试一试