2018 Multi-University Training Contest 10

From EOJ Wiki
Revision as of 07:13, 25 October 2018 by Oxx1108 (talk | contribs) (→‎Problem L)
Jump to navigation Jump to search

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 by ultmaster. 00:08 (+)

题意:求 $2^n$。

题解:高精度。或

printf("%.0f\n", pow(2, n));

Problem I

Solved by kblack. 00:51 (+)

题意:$\sum_{i=1}^{n}{\sum_{j=1}{i-1}{[gcd(i+j, i-j) = 1]}}$。

题解:若 $i$ 与 $j$ 奇偶性相同,肯定凉了,否则 $gcd(i+j, i-j) = gcd(i+j, 2j) = gcd(i+j, j) = gcd(i, j)$,即 $i$, $j$ 互质即可。若 $i$ 是偶数 $phi(i)$ 即可,若 $i$ 是奇数,那么 $\frac{phi(i)}{2}$ 就可以了,线性筛一下求个前缀和就好。

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$ 个人看电影,每个电影能拿钱,连续看相同类型的电影要罚钱,求最大获益。

题解:两排点表示在看那种电影,对于每个电影在两边对应时间连边,再连上发钱切换的边,费用流一下就好了。