ACL Contest 1 题解

Froggy · 2020-10-08 12:07:18 · 个人记录

ACL Contest 1

感觉题目挺好玩的就来补一下题解。

A - Reachable Towns

先把点按 x_i 从小到大排序，然后一个一个扫过去。

有个显然的 \mathcal{O}(n^2) 暴力连边做法，不过由于我们只需要求每个联通块的大小，所以很多边都是无用的。

考虑维护一个单调栈，栈里面每个点都满足它的 y_j 是它所属联通块中所有 y_j 的最小值，且栈里面的点的 y_j （从栈底到栈顶）单调递减。

新加一个点 (x_i,y_i)，那么弹出栈中所有满足 y_j<y_i 的点，然后将所有被弹出的点 j 都和 i 进行连边，最后把这个联通块中 y_j 最小的点在压进栈里即可。

显然这样做边数是 \mathcal{O}(n) 的。

时间复杂度：\mathcal{O}(n\log n)。

code

B - Sum is Multiple

转化一下题意：找到最小的 k，满足：2n\mid k(k+1)。

显然需要把 2n 质因数分解掉。假设 2n=p_1^{q_1}\times\cdots\times p_m^{q_m}，因为 \gcd(k,k+1)=1，所以对于每个 p_i^{q_i} 要么可以整除 k，要么可以整除 k+1。k 和 k+1 分别分配的数可以 2^m 进行枚举。

假设分配的数的积分别是 x 和 y，那么现在的目标就是找到一个最小的 k，满足 x\mid k 且 y\mid (k+1)，转化为同余方程后可以拿 exgcd 直接解决。

或者直接用 Atcoder Library 里面的 excrt 也行。

时间复杂度：\mathcal{O}(2^m\log n)。拿计算器算一算会发现 m 的最大值是 13。

code

C - Moving Pieces

比较裸的一道网络流。

有个显然的建图方法：