2018 Multi-University Training Contest 10
Problem A
Unsolved.
Problem C
Upsolved by ultmaster. (-32)
做自闭了。
题意:求 $\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \text{gcd}(i,j^2,k^3)$。
题解:枚举 gcd,然后类比 $(i,j,k)$ 的做法,考虑求出每个数的 g2, g3,分别定义为对于每个数的质因数上的指数除以 2 和除以 3 取上整得到的数。朴素的做法是 $\sum_{i=1}^n \phi ( g ) \sum_{k=1}^{n/i} \mu(k) \lfloor A / (ig) \rfloor \lfloor B / g_2(ig) \rfloor \lfloor C / g_3(ig) \rfloor$。可以交换求和符号优化这个过程(预处理一些东西然后每个 case 是线性的),得到 $\sum_{i=1}^n f(i) \lfloor A / i \rfloor \lfloor B / g_2(i) \rfloor \lfloor C / g_3(i) \rfloor$,其中 $f(i) = \sum_{d|i} \mu(d) \phi(i/d)$。考虑优化这个 $f(i)$ 的计算过程(去掉 log),由于是积性函数的狄利克雷卷积,所以该函数也是积性的。所以可以使用线性筛。筛的时候在加入相同的因子的时候,如果是质数的幂 $p^x$,则 $f(k = p^{x+1})= \phi(p^{x-1}) + \phi(p^x) - f(p^x)$;否则直接相乘。
线性的牛逼啊,但这个超小的 log 在本地两秒就能跑出来的,在 HDU 上就是怎么也过不了。优化来优化去甚至加入了 cache 优化还是 TLE。时限这么紧导致线性复杂度也会 TLE。赛后对着这个线性的又是一通优化才过。过的提交就没有一份在 1/2 时限内跑出来的。卡常卡得让人怀疑我是谁我在哪儿我为什么会在这儿。
Problem E
Solved by zerol. 01:18 (+2)
题意:对于树上的每个点,求 lca 恰好是这个点的点对中点权 gcd 的最大值。
题解:对于树上每个点,求出一个 bitset 记录了子树中所有数的因数并,然后依次合并儿子以及自己本身,合并前取位与检查最高位的 1。(bitset._Find_first() 可以求出第一个 1 的位置。)
另解:线段树合并 / set 启发式合并。枚举 gcd 在更新在虚树上结点的答案(相邻两项 LCA)(由 CSL 友情提供)。
Problem G
Solved by OEIS. 00:42 (+)
Problem H
Solved.
Problem I
Solved.
Problem J
Solved by zerol. 02:19 (+4)
题意:对于两个点集 S_1, S_2,求 $\max\{dist(x,y)+w_x+w_y | x\in S_1,y\in S_2\}$,距离为曼哈顿距离,最多五维。
题解:K-D Tree 暴力,要多加一些剪枝才能过。
正解:枚举每一维绝对值的正负,记录 $2^5$ 种可能的最大值,将另一个点集带入,取最大值即可。
Problem L
Solved.
题意:最多 $K$ 个人看电影,每个电影能拿钱,连续看相同类型的电影要罚钱,求最大获益。
题解:两排点表示在看那种电影,对于每个电影在两边对应时间连边,再连上发钱切换的边,费用流一下就好了。