8
11
2016
3

【Cool's Life欢乐赛暨洛谷8月月赛】题解

参赛者
总成绩
A
B
C
D
400 (3038ms)
100
100
100
100
400 (3102ms)
100
100
100
100
400 (10684ms)
100
100
100
100
400 (13208ms)
100
100
100
100
#5
wyxorz
400 (13910ms)
100
100
100
100
350 (8906ms)
100
100
100
50
#7
YYMHL
350 (14935ms)
100
100
100
50
340 (9434ms)
100
100
100
40
320 (15164ms)
100
100
100
20
#10
ahwhGQY
305 (3050ms)
100
45
100
60

 

大家纷纷AK,出题人受到打击;大家来月再战思考难度大战!

T1

一句话题意:给定平面上n个点,两个点之间有连线当且仅当一个点所在的“格子”处在另一个点所在“格子”的左下角。求所有连线(曼哈顿)距离的平均值。

30%:[tex]O(n^2)[/tex]暴力

60%:[tex]O(nlogn)[/tex]数据结构大力维护(加点、二维数点)

100%:发现题中坐标范围是[0,20),这样所有点都分布在20*20=400个格子中。统计出每个方块中的点数和他们到方块左下角的距离总和,这样统计完之后,枚举两个块,用乘法原理计算出这两格中的点连成的所有路径总长。比暴力还好写。

 

T2

一句话题意:
[tex]\sum_{x=L}^R\sum_{d|x}d^k[/tex]

1-5:

用快速幂,对于每个询问用[tex]\sqrt{n}[/tex]的算法处理[tex]\sum_{d|n}d^k[/tex],计算答案前缀和。

6-7:

去掉前缀和。

8-12:

枚举上式的[tex]d[/tex],用调和级数的姿势求贡献[tex]O(nlogn)[/tex]

13-15:

送给不知道在想什么的人

[tex]\sum_{x=L}^R\sum_{d|x}d^k=\sum_{d=1}^nd^k\lfloor\frac{n}{d}\rfloor[/tex]

发现[tex]d^k[/tex]是完全积性函数,可以线性筛,那么对于每个询问分块计算即可。复杂度[tex]O(n+Q\sqrt{n})[/tex]

16-20:

送给完全不知道在想什么的人

易证(脑补、目测、打表、经验表明……)[tex]\sum_{d|x}d^k[/tex]是个积性函数,只要在线性筛里简单维护一些幂次信息就可以做到[tex]O(n+Q)[/tex]了。

 

T3

一句话题意:给出m条树链,求k条树链使得交集非空,最小化(树链最大值-最小值)。

就是NOI2016Day2T1的无脑树上版。

很容易想到的是枚举每个点,记录覆盖这个点的树链的长度,然后滑动窗口式的更新答案

复杂度[tex]O(n^2logn)[/tex],[tex]log[/tex]体现在求lca上。送了70分。

标算树链按长度排序后,用双指针维护一段某点覆盖次数>=k的树链区间,每次更新答案。结合树剖后线段树可以[tex]O(nlog^2n)[/tex]秒过。

 

T4

一句话题意:这还有什么好两句话的。。

按等级排序后[tex]O(n^2)[/tex]的LIS式DP十分简单,送了60分(常数太小233)。

似乎还有20分给[tex]O(nlogn)[/tex]的LIS。

标算就是CDQ分治,处理前一半的操作,计算对后一半的贡献,这里面可以归并,一半按照攻击力排序,一半按照力量排序,用树状数组维护DP贡献。复杂度[tex]O(nlog^2n)[/tex],CDQ常数不会太大。

树套树一定也能做,看常数吧233【写完题解出题人发现CDQ被树套树艹飞,惨啊】

Category: HDU | Tags: | Read Count: 1074
Avatar_small
hzq84621 说:
2016年8月12日 07:04

T4可以建一个树高LOG的KDTREE艹飞树套树

渣渣 说:
2017年4月02日 08:17

请问T4咋用树套树做啊?我太渣了不会啊。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com