2018 Multi-University, Nowcoder Day 10

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 (+)