2021.10.18模拟赛

What else should I engrave on my mind

原题场，不过题还不错

贪心

先排个序

最小值显然，最大值肯定是最小最大反复横跳，喝水更优就喝水，枚举下第一次吃最小还是最大

竟然是数论题

考虑重要性质是答案一定是 $m_k$ 的一个最小的合法约数 $d$ ，因为若存在有数 $c$ 是密码，但是 $c\not{|}\ m_k$ 则 $\gcd(c,d)$ 是密码且 $\gcd(c,d) < d$

且 $\gcd(c,d) | m_k$ 矛盾

先把 $m_k \gets \gcd(m_k,n)$ 这样是通过 $am_k$ 能凑出来的最小值，对他分解因数，对于其他的 $m_i$ 因为它的因子必然不是密码，就和 $m_k$ 取 $\gcd$

并且标记这个因子不合法

找最小合法的因子的时候可以把不合法因子每次删一个质因子向下推而不是分解他，复杂度就变成了 $O(\sqrt{m_k}+k\log(m_k)+d(m_k)\omega(m_k))$

树形dp

设 $f_{x,i}$ 表示 $x$ 中子树向上走到 $x$ 用了 $i$ 个磁铁的结果 , $g_{x,i}$ 表示 $x$ 走到子树里用了 $i$ 个磁铁的结果

转移枚举儿子合并，更新答案用 $g_{x,i}+f_{x,V-i}$ 更新

需要注意起点终点收益不同，需要反过来再跑一遍

记 $C\to 1,T\to -1$ 就是要所有前后缀和都非负

贪心放就是对的，即遇到一个负数就改成 $0$

考虑前缀会加上前缀最小值的相反数，即 $-pre_{\min}$ ，第 $x$ 位后缀和的变化量是 $\min pre_{i<x}-pre_{min}$

要求 $-\min(suf_{x}+pre_{i<x}-pre_{\min})-pre_{\min}=-min(suf_x+\min pre_{i<x})$

就是找到两个点的前后缀和不交且他们的和最小，即总和-最大子段和