2021-2022 ACM-ICPC Latin American Regional Programming Contest

发表于 2022-04-07 分类于 XCPC

[cf]

A. Ancient Towers

考虑最大值如何计算，最小值相当于取负号。

排序后，找到同正同负的下标，按照乘积的大小从大到小排序，假设有 $k$ 对这样的数，那么前 $k$ 个的选法一定是按照顺序来的。剩下 $n-k$ 对一正一负，使用FFT计算即可。

时间复杂度 $O(n\log n)$。

删掉 $n$ 个点后，$n-1$ 所在连通块形成的集合即为其中一个集合。

树哈希：$f_u=1+\sum_{v\in son_u}f_v\times prime[siz_v]$。

每棵树，枚举它节点个数的因数 $d$，判断是否能被分解为 $\frac{n}{d}$ 棵同构的树。

若能，那么肯定存在一个大小为 $d$ 的子树，算出其哈希值后，用一个数组标记表示已经算过了，模拟将这个大小为 $d$ 的子树删去，然后继续做即可。

二分图带权匹配模板。

模拟题，找到一个周期即可。

输出 N 当且仅当存在两对点都在边界上，且交叉。

签到题。