2018 Multi-University, Nowcoder Day 3
Jump to navigation
Jump to search
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 (+)
Problem F
Upsolved by zerol.
题意：询问一列数的某一段的所有子序列形成的数字的 SOD 分布，同时支持修改一个位置上的数。
题解：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 (+)
Problem J
Solved by ultmaster. 02:51 (+)