2018 Multi-University, Nowcoder Day 3

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 H

Solved by kblack. 00:19 (+)

温暖的枚举签到。

Problem I

Solved by ultmaster. 04:24 (+)

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

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

没想到居然还是正解。

Problem J

Solved by ultmaster. 02:51 (+)