2019.5 月赛题解

Xiejiadong edited 4 年，9 月前

花絮

• Codeforces Polygon 不知道怎么就不能下载 Linux 包了。这比赛差点就直接夭折了。
• 好像一不小心变成 Div 1 了，还是难度乱序的。
• Weaver_zhu ：我这题还能加难度，加吗？
• Xiejiadong ：加！
• Kilo_5723 ：我这题可以卡掉 log 的，卡吗？
• Xiejiadong ：卡！
• 于是，历史最难月赛。惨案。
• 很多人私我，QQ小方是否真有其人。

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

4 年，11 月前

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

回复 0 0

Xiejiadong

4 年，11 月前

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

回复 0 0

__Archer

4 年，11 月前

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

回复 0 0

Weaver_zhu

4 年，11 月前

$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)$

回复 1 0

__Archer

4 年，11 月前

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

回复 0 0