Difference between revisions of "2018 Multi-University, Nowcoder Day 3"

From EOJ Wiki
Jump to navigation Jump to search
Line 45: Line 45:
 
题意:求树上的染色数,使得相同颜色结点的最短距离恰好为 d。
 
题意:求树上的染色数,使得相同颜色结点的最短距离恰好为 d。
  
题解:首先将问题转化为 f(d): 染色数使得相同颜色结点的距离至少为 d 的方案数。那么答案就是 f(d)-f(d+1)。关键是按照什么顺序统计使得距离 u 不超过 d 的点中不存在两个距离大于 d 的都染过了,如果能做到这个,只要按顺序求每个结点的剩下可用颜色乘起来就好了。这部分可以暴力,也可以动态点分治做到 $O(n\log^2 n)$。答案告诉我们要按照 bfs 顺序染色,也就是按照深度顺序染,至于为什么
+
题解:首先将问题转化为 f(d): 染色数使得相同颜色结点的距离至少为 d 的方案数。那么答案就是 f(d)-f(d+1)。关键是按照什么顺序统计使得距离 u 不超过 d 的点中不存在两个距离大于 d 的都染过了,如果能做到这个,只要按顺序求每个结点的剩下可用颜色乘起来就好了。这部分可以暴力,也可以动态点分治做到 $O(n\log^2 n)$。答案告诉我们要按照 bfs 顺序染色,也就是按照深度顺序染,至于为什么(证:当前访问到 u,x 和 y 已经访问过,设 dep(lca(u,x)) <= dep(lca(u, y)),那么 x 到 y 只需要 将 x 到 u 的路径上 d(lca(u, y), u) 那段替换为 d(lca(u, y), y) 就行了,这样距离一定不超过 d。)
  
 
== Problem H ==
 
== Problem H ==

Revision as of 12:19, 26 July 2018

Problem A

Solved by kblack. 01:16 (+1)

题意:容量是四元组,求限制内最大价值和。

题解:将物品分为两半,每半用 $2^{18}$ 枚举,然后耗费 $36^4$ 更新一遍,处理没有用完限制的部分。

Problem B

Unsolved. (-2)

Problem C

Solved by zerol. 00:45 (+)

题意:每次把数列中一个区间的数剪切到数列的开头,最后打印这个数列。

题解:模板题。treap / splay / rope(pb_ds)

Problem D

Unsolved. (-6)

Problem E

Solved by ultmaster. 00:49 (+)

题意:把字符串循环起来,然后对本质不同的循环字符串进行分组。

题解:只要找到最小循环节就可以了(hash,KMP)。一开始题都没看清楚就上了 SA,一通操作以后跟 kblack 重新确认了题意。发现就是个签到题。

Problem F

Upsolved by zerol.

题意:询问一列数(每个数都是一个一位十六进制数)的某一段的所有非空子序列形成的数字的重复SOD小于16的结果的分布,同时支持修改一个位置上的数。

题解:SOD(sum of digits) 这种运算不改变 模 base-1 的值。线段树维护区间的答案和区间中 0 的个数,合并代价 16^2。( SOD(0) = 0, SOD(v) = (v - 1) % (base - 1) + 1)

Problem G

Upsolved by zerol.

题意:求树上的染色数,使得相同颜色结点的最短距离恰好为 d。

题解:首先将问题转化为 f(d): 染色数使得相同颜色结点的距离至少为 d 的方案数。那么答案就是 f(d)-f(d+1)。关键是按照什么顺序统计使得距离 u 不超过 d 的点中不存在两个距离大于 d 的都染过了,如果能做到这个,只要按顺序求每个结点的剩下可用颜色乘起来就好了。这部分可以暴力,也可以动态点分治做到 $O(n\log^2 n)$。答案告诉我们要按照 bfs 顺序染色,也就是按照深度顺序染,至于为什么(证:当前访问到 u,x 和 y 已经访问过,设 dep(lca(u,x)) <= dep(lca(u, y)),那么 x 到 y 只需要 将 x 到 u 的路径上 d(lca(u, y), u) 那段替换为 d(lca(u, y), y) 就行了,这样距离一定不超过 d。)

Problem H

Solved by kblack. 00:19 (+)

温暖的枚举签到。

Problem I

Solved by ultmaster. 04:24 (+)

题意:给一个三角形,求三角形内任意找 $m$ 个点组成的凸包的点数的期望。

题解:注意到凸包的形状与三角形形状无关,所以答案只跟 $m$ 有关。又因为 $m$ 不超过 10,于是就成了愉快地提交答案题。在本地跑了蒙特卡洛之后,发现收敛效果并不理想。最后上了服务器,甚至上了多进程。但是最后这些操作并没有什么卵用,报着试一试的心态把一开始(上多进程之前)跑出来的答案交了一发居然过了。

没想到居然还是正解。

Problem J

Solved by ultmaster. 02:51 (+)

题意:给一个简单多边形,给一个圆心,求最小的半径使得圆覆盖多边形的一定比例。

题解:二分答案求多边形与圆的交。kblack 发现这题以前写过(当然不大一样),很早就上了,写来写去调来调去还是不大行。最后上了 Plan C,去网上随便拉了个板子一发过了。当然这一通操作(我的锅?)最终导致 kblack 彻底掉线,本场 GG。