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

From EOJ Wiki
Jump to navigation Jump to search
Line 18: Line 18:
  
 
Solved by kblack. 03:33 (+)
 
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 ==
 
== Problem J ==
  
 
Solved by zerol | kblack. 00:27 (-1/+) | 01:25 (+)
 
Solved by zerol | kblack. 00:27 (-1/+) | 01:25 (+)

Revision as of 10:11, 20 August 2018

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