2018 Multi-University, Nowcoder Day 10

From EOJ Wiki
Revision as of 11:16, 20 August 2018 by Zerol (talk | contribs) (→‎Problem J)
Jump to navigation Jump to search

Problem A

Solved by kblack. 00:23 (+)

题意:随机修改范围内的 $x$ 为 $x+lowbit(x)$ 或 $x-lowbit(x)$,求区间和期望。

题解:假题。。。修改操作不改变期望。。。

Problem D

Solved by ultmaster. 01:20 (+1)

题意:有三种操作,区间加,对整个序列求前缀和,求区间和。第三种操作不会超过 500 个。

题解:考虑每次区间加对答案的贡献都是独立的,对每次询问,分别计算每个区间加对答案的贡献即可。区间加的贡献可以拆成一个 (l, +w) 的贡献和一个 (r, -w) 的贡献。对于每个 w,只要稍微推导一下很容易看到是一个组合数。

Problem F

Solved by kblack. 03:33 (+)

题意:给一张带权完全图,重建一张图,新图每个点代表原来一条边,每对代表有公共端点的边对的点对之间连一条原始两边权和的边,求新图的点两两最短路之和。

题解:首先拆解新图上的最短路,$(i,j)$ 的最短路可以拆成 $w_i+w_j+2\times min(dis(i_0, j_0), dis(i_0, j_1), dis(i_1, j_0), dis(i_1, j_1))$ 其中 $x_0$ 与 $x_1$ 代表边 $x$ 的两个端点,$dis(a, b)$ 代表原图上两点最短路。第一部分是原始边权和的常数倍,不管他了。第二部分可以先枚举一条 $(A, B)$,然后计算他与其他剩下的边的边权距离和,方法是 Floyd 预处理两点最短路,先计算出剩下所有点与当前边的最短路并排序,设排序后数组是 $C$,其他边相当于连接其他点的边,最短距离则是与当前边距离较小的的点的距离,因为完全图所有向更大方向的点是满的,直接 $\sum_{i=1}^{n} C_i(n-i)$。因为整个过程会计算每个边对两次,所以连两倍都省了。

Problem J

Solved by zerol | kblack. 00:27 (-1/+) | 01:25 (+)

题意:依次合并每个串,b 合入 a 的结果是 s,s 满足它的前缀是 a,且 b 是 s 的子序列,且最短。

题解:每插入一个字母,把所有以这个字母开头的字符串删除第一个字符。


zerol:出题人数据锅了,导致对一个签到调到怀疑人生。后来让 kblack 重写了一个过了,而本质的区别是 cin/scanf。