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

From EOJ Wiki
Jump to navigation Jump to search
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
== Problem A ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:求烷烃、烷基的同分异构体数量。
 +
 +
题解:仔细论证 / 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)^2 A(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)$ 给出。(题解中有个错误,应该是 $A(x)^4$ 而不是 $A(x^4)$。)
 +
 +
跟标程反复对照,反复(尝试)理解之后 AC 了。不少细节还是没有搞清楚。难点在于这个分治:CDQ 分治时,利用已经算好的 $[l,mid]$ 计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。一般来说,对于 $mid + 1 \le i \le r$ 来说 $f(i) = \sum_{j=l}^{mid} f(j) a_{t-j}$,此处 $t$ 是一个定值,$a$ 数组也应该是已经算好的东西。但此题的麻烦之处在于 $a$ 数组是一个跟 $f$ 有关的东西,而且并不总是算好了的。举例来说,对于 $A(x) A(x^2)$ 来说,$A(x^2)$ 依赖的数值比较靠前一定计算完成了。但对于 $A(x)^3$,我们写成 $A(x) \cdot A^2(x)$ 的形式,需要的是 $[mid+1,r]$,$A(x)$ 在 $[l,mid]$ 之间,此时 $A^2(x)$ 在 $l=0$ 的时候还没算完,而且差的是靠后面的项。但是由于是 $A^3(x)$,我们可以在后面($l$ 不为 0 的时候)算贡献的时候补回来,具体是乘一个系数 3(为什么是 3?)。
 +
 +
算完 $A(x)$ 以后,$B(x)$ 应该不难算出。细心一点不要抄错。
 +
 
== Problem C ==
 
== Problem C ==
  
Line 7: Line 20:
 
题意:求 $\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \text{gcd}(i,j^2,k^3)$。
 
题意:求 $\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 A / g_3(ig) \rfloor$。可以交换求和符号优化这个过程(预处理一些东西然后每个 case 是线性的),得到 $\sum_{i=1}^n f(i) \lfloor A / i \rfloor \lfloor B / g_2(i) \rfloor \lfloor A / 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)$;否则直接相乘。
+
题解:枚举 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 时限内跑出来的。卡常卡得让人怀疑我是谁我在哪儿我为什么会在这儿。
 
线性的牛逼啊,但这个超小的 log 在本地两秒就能跑出来的,在 HDU 上就是怎么也过不了。优化来优化去甚至加入了 cache 优化还是 TLE。时限这么紧导致线性复杂度也会 TLE。赛后对着这个线性的又是一通优化才过。过的提交就没有一份在 1/2 时限内跑出来的。卡常卡得让人怀疑我是谁我在哪儿我为什么会在这儿。
Line 37: Line 50:
 
Solved by kblack. 00:51 (+)
 
Solved by kblack. 00:51 (+)
  
题意:$\sum_{i=1}^{n}{\sum_{j=1}{i-1}{[gcd(i+j, i-j) = 1]}}。
+
题意:$\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}$ 就可以了,线性筛一下求个前缀和就好。
 
题解:若 $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}$ 就可以了,线性筛一下求个前缀和就好。

Latest revision as of 16:19, 28 August 2018

Problem A

Upsolved by ultmaster.

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

题解:仔细论证 / 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)^2 A(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)$ 给出。(题解中有个错误,应该是 $A(x)^4$ 而不是 $A(x^4)$。)

跟标程反复对照,反复(尝试)理解之后 AC 了。不少细节还是没有搞清楚。难点在于这个分治:CDQ 分治时,利用已经算好的 $[l,mid]$ 计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。一般来说,对于 $mid + 1 \le i \le r$ 来说 $f(i) = \sum_{j=l}^{mid} f(j) a_{t-j}$,此处 $t$ 是一个定值,$a$ 数组也应该是已经算好的东西。但此题的麻烦之处在于 $a$ 数组是一个跟 $f$ 有关的东西,而且并不总是算好了的。举例来说,对于 $A(x) A(x^2)$ 来说,$A(x^2)$ 依赖的数值比较靠前一定计算完成了。但对于 $A(x)^3$,我们写成 $A(x) \cdot A^2(x)$ 的形式,需要的是 $[mid+1,r]$,$A(x)$ 在 $[l,mid]$ 之间,此时 $A^2(x)$ 在 $l=0$ 的时候还没算完,而且差的是靠后面的项。但是由于是 $A^3(x)$,我们可以在后面($l$ 不为 0 的时候)算贡献的时候补回来,具体是乘一个系数 3(为什么是 3?)。

算完 $A(x)$ 以后,$B(x)$ 应该不难算出。细心一点不要抄错。

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

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