Difference between revisions of "2018 Multi-University, HDU Day 10"

From EOJ Wiki
Jump to navigation Jump to search
Line 1: Line 1:
 +
== Problem A ==
 +
 +
Unsolved.
 +
 +
题意:求烷烃、烷基的同分异构体数量。
 +
 +
题解:仔细论证 / OEIS 可以得到烷基个数有生成函数 $A(x) = 1 + \frac{1}{6}x (A(x)^3 + 3A(x)A(x^2) + 2A(x^3)$。用分治 FFT 可以解 $A(x)$(怎么解?)。烷基个数可以由:
 +
$P(x) = \frac{1}{24} x (A(x^4) + 3A(x^2)^2 + 6A(x)2A(x^2) + 8A(x)A(x^3) + 6A(x^4)$, $Q(x) = \frac{1}{2} ((A(x) − 1)^2 + A(x^2) − 1)$, $B(x)=P(x)-Q(x)+A(x^2)$ 给出。
 +
 +
不会 FFT。
 +
 
== Problem C ==
 
== Problem C ==
  

Revision as of 09:35, 28 August 2018

Problem A

Unsolved.

题意:求烷烃、烷基的同分异构体数量。

题解:仔细论证 / OEIS 可以得到烷基个数有生成函数 $A(x) = 1 + \frac{1}{6}x (A(x)^3 + 3A(x)A(x^2) + 2A(x^3)$。用分治 FFT 可以解 $A(x)$(怎么解?)。烷基个数可以由: $P(x) = \frac{1}{24} x (A(x^4) + 3A(x^2)^2 + 6A(x)2A(x^2) + 8A(x)A(x^3) + 6A(x^4)$, $Q(x) = \frac{1}{2} ((A(x) − 1)^2 + A(x^2) − 1)$, $B(x)=P(x)-Q(x)+A(x^2)$ 给出。

不会 FFT。

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 by kblack. 01:21 (+)

题意:最多 $K$ 个人看电影,每个电影能拿钱,连续看相同类型的电影要罚钱,求最大获益。

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